#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

char const mbd[]=
"        1"
"        0"
"        0"
"        1"
"        1"
"        1"
"        2"
"        2"
"        3"
"        4"
"        5"
"        6"
"        9"
"       10"
"       13"
"       17"
"       21"
"       25"
"       33"
"       39"
"       49"
"       60"
"       73"
"       88"
"      110"
"      130"
"      158"
"      191"
"      230"
"      273"
"      331"
"      391"
"      468"
"      556"
"      660"
"      779"
"      927"
"     1087"
"     1284"
"     1510"
"     1775"
"     2075"
"     2438"
"     2842"
"     3323"
"     3872"
"     4510"
"     5237"
"     6095"
"     7056"
"     8182"
"     9465"
"    10945"
"    12625"
"    14578"
"    16779"
"    19323"
"    22210"
"    25519"
"    29269"
"    33581"
"    38438"
"    44004"
"    50305"
"    57480"
"    65585"
"    74831"
"    85241"
"    97084"
"   110441"
"   125577"
"   142627"
"   161955"
"   183669"
"   208233"
"   235858"
"   267016"
"   302008"
"   341474"
"   385714"
"   435525"
"   491365"
"   554102"
"   624363"
"   703263"
"   791483"
"   890414"
"  1001014"
"  1124831"
"  1263105"
"  1417812"
"  1590370"
"  1783200"
"  1998184"
"  2238095"
"  2505329"
"  2803342"
"  3134927"
"  3504321"
"  3915113"
"  4372211"
"  4880095"
"  5444836"
"  6071737"
"  6768162"
"  7540773"
"  8398212"
"  9348709"
" 10402828"
" 11570343"
" 12864051"
" 14296061"
" 15881447"
" 17635015"
" 19575084"
" 21719314"
" 24089760"
" 26708042"
" 29600270"
" 32792694"
" 36316828"
" 40203969"
" 44491966"
" 49218838"
" 54429398"
" 60169523"
" 66493081"
" 73454751"
" 81118965"
" 89551667"
" 98829225"
"109030834"
"120247855"
"132574519"
"146119798"
"160996758"
"177334421"
"195267955"
"214951211"
"236544728"
"260231425"
"286203009"
"314675872"
"345878364"
"380067576"
"417514127"
"458522902"
"503415815"
"552552929"
"606316324"
"665132594"
"729453566"
"799783726"
"876658634"
"960673117"
" 52460907"
"152724699"
"262212186"
"381752364"
"512228736"
"654616871"
"809959201"
"979405292"
"164182318"
"365643141"
"585233653"
"824542945"
" 85272542"
"369290304"
"678594820"
" 15379338"
"381992526"
"781005522"
"215175329"
"687517255"
"201262756"
"759944563"
"367350776"
" 27614944"
"745173504"
"524863293"
"371873310"
"291858649"
"290888275"
"375566270"
"552984605"
"830855028"
"217455869"
"721785141"
"353504019"
"123101011"
" 41842337"
"121951061"
"376552351"
"819880455"
"467221791"
"335137990"
"441419538"
"805330256"
"447557166"
"390491745"
"658180454"
"276629760"
"273772183"
"679801603"
"527139350"
"850818691"
"688456069"
" 80670195"
" 71077060"
"706752549"
" 38233320"
"120045588"
" 10719606"
"773369047"
"475741204"
"190858310"
"997084676"
"978858086"
"226783438"
"838437736"
"918518139"
"579736017"
"942998838"
"138427507"
"305586348"
"594607469"
"166502662"
"194415210"
"863993370"
"374813121"
"940831853"
"791966202"
"174669872"
"353694622"
"612771774"
"256610725"
"611711331"
" 28587465"
"882764989"
"577268201"
"543786913"
"245495777"
"178427307"
"874616549"
"903752252"
"876699535"
"447417489"
"316949520"
"235660850"
"  7699582"
"493646816"
"615520476"
"359838683"
"783283972"
" 16254206"
"269205439"
"836814483"
"105101699"
"556222278"
"776523270"
"462070924"
"427686061"
"613371347"
" 94465425"
" 89017719"
"969267494"
"270116709"
"702015745"
"160757027"
"741965448"
"752302462"
"725836831"
"436875941"
"918356581"
"476603972"
"712019456"
"535925102"
"193922515"
"285128454"
"788428408"
" 84516507"
"985434142"
"759668233"
"165482772"
"479512596"
"534236033"
"750629372"
"180328278"
"542743060"
"272605811"
"562163299"
"414635521"
"692269883"
"176482256"
"622378624"
"826535005"
"688863552"
"288815164"
"955671508"
"354252800"
"564544427"
"178230357"
"388891119"
"100510804"
" 29751451"
"827955564"
"196829920"
" 25767445"
"522689722"
"368357282"
"864458141"
"107039350"
"153786061"
"219101197"
"863034860"
"210412733"
"164322905"
"652283727"
"867086722"
"543504184"
"229950252"
"599162031"
"754717578"
"579871738"
" 82942594"
"789156897"
"129755060"
"881724096"
"606241704"
"142139844"
" 99387784"
"413013909"
"898421671"
"872668835"
"779420909"
"885732284"
"984706717"
"177106512"
"661200748"
"608911826"
" 53692047"
"872546827"
"783296578"
"445386778"
"579753674"
"202038321"
"880080133"
"115286567"
"753688194"
"533327581"
"667247657"
"575922558"
"662991713"
"254580032"
"590033586"
"992807947"
"101704397"
"299825166"
"215078258"
"437437811"
"319718796"
" 17201554"
"623974011"
"571713123"
"141319996"
"262639672"
"444418910"
" 21893087"
"553847828"
"569031605"
"485063262"
"911282138"
"149083014"
"115777042"
"493610110"
"345019175"
"985667375"
"370399715"
"772549935"
" 29298195"
"119816251"
"367020476"
" 18021971"
"511220852"
"172366056"
"668653785"
"947520602"
" 11088185"
"239577001"
"635503959"
"687393285"
"250309811"
"124142812"
"753397832"
"714260465"
"438148596"
"821004450"
"198332413"
"315147380"
"802895900"
"775449053"
" 87330990"
"847755090"
"770930504"
"933767105"
"560340921"
"385260869"
"253390169"
"487545061"
"726884553"
"742797091"
"982357517"
"325355410"
"851684428"
" 82704685"
"548462549"
"117355021"
"997888673"
"826744814"
"810269116"
"309664807"
"904233608"
"294037509"
"147026907"
"228581164"
"989329380"
"924301368"
"961588900"
"163447991"
" 84774599"
" 48225379"
"768488416"
"560100455"
"662379012"
"885592318"
"218760205"
"580675983"
"463074002"
"624177510"
"706105525"
"905630963"
"703702830"
"763795005"
"139458515"
"881593933"
"339788280"
"223513364"
"881072715"
"848731017"
"296199193"
"408440670"
"521039416"
" 32056434"
"110976785"
"224569137"
"710790810"
"419916980"
"891890824"
" 84889981"
"377921073"
"875551351"
"  1721125"
"428514818"
"624068681"
" 81499457"
"830807530"
"333237564"
"692492685"
"327700678"
"415154406"
"290019210"
"514301219"
"875796803"
"443890204"
" 32617390"
"665630706"
"484051790"
"195024305"
"627007043"
" 20749142"
"765276887"
"799359344"
"541598579"
"205775907"
"562445410"
"677449404"
"912647033"
"468303471"
"995306237"
"363181787"
"411329720"
"627140613"
"915360365"
"352774064"
"459195780"
"904192415"
"619754032"
"332139744"
"975075739"
"207154916"
" 32575079"
" 54760172"
"992657212"
"387276463"
"831962715"
"197041099"
"951758147"
"723255172"
" 86269902"
"513494748"
"471064307"
"561970895"
"786507567"
"958726207"
"589991882"
"575070693"
"369802949"
"522862845"
"760047109"
"222655585"
"772261684"
"913653562"
"145637333"
"534058815"
"395837757"
"405767061"
"359786773"
"701700625"
"638420222"
"117303424"
"330381156"
"542222867"
" 91886169"
"253198157"
"318673236"
"952060419"
" 26344409"
"815144127"
" 56003296"
" 53660178"
" 81503170"
"153395974"
"616746722"
"142424721"
"341052617"
"708157675"
"486896301"
" 50233795"
"356467195"
"755825115"
"429608572"
"229160852"
"690777400"
"472475806"
"289839757"
" 81431550"
"773888004"
"921689787"
"894948103"
"703015411"
"499283501"
"969978749"
"313624810"
"508196512"
"561452353"
"562971946"
"633119357"
"394290578"
"134555216"
"887731861"
"414666012"
"998256235"
"708334149"
"916822366"
"565294162"
"158866621"
"109943617"
"283700421"
"926018529"
"520924633"
"136562212"
"516223821"
"821335022"
"442223972"
"318975200"
"986164163"
"975496846"
"491361961"
" 53555110"
"156710546"
"861973523"
"202204842"
"272360458"
"766241510"
"817878425"
"486382155"
"149699869"
"782507539"
"916245857"
"415845325"
"934838160"
"663712623"
"343896695"
"452614328"
"558957680"
"465892415"
"632409943"
"605283643"
"593659179"
" 90017339"
"532733183"
"944518288"
"362193726"
"100781222"
"335133048"
" 98185496"
" 34676567"
" 50999634"
"219694865"
"625666113"
"856932537"
" 24202957"
"351917181"
"422111189"
"737547429"
"775996318"
"618252457"
"810010828"
"838030609"
"512793396"
"507572562"
"490165644"
"493906871"
"583138273"
"  1263460"
"206981885"
"880350474"
"351967393"
"309774179"
"535510334"
"464231032"
"775970633"
"788040960"
"195867171"
"201838643"
"109051337"
"118629186"
"867304558"
"291624857"
"425438247"
"907321526"
"760653125"
"959480473"
"986218099"
"983374000"
"926723712"
"251064093"
"664350186"
"708048777"
"350098772"
"787201959"
"955832070"
"946176958"
"777803874"
"420267007"
" 98849371"
" 92058433"
"621822482"
"841745522"
"151498697"
"557895288"
" 70070971"
"697214755"
"731254225"
"162447330"
"178832652"
"493313184"
"135924975"
" 47515000"
"115741547"
"700546042"
"485573688"
"183931049"
"695914067"
"218732630"
" 38929986"
"351652599"
"330278933"
"542092992"
"629202910"
"345837410"
"515432088"
"641241098"
"523966193"
"479600454"
"954628690"
"397595971"
"259099802"
"410438207"
"358420399"
"702524085"
"818844104"
"696226927"
"463369343"
"136425284"
"775555898"
"686037775"
"328726748"
"155847635"
"105015403"
"986923067"
"865236035"
"622145250"
"642240113"
"521049139"
"306593321"
"449553728"
"322345873"
"823743137"
"671369229"
" 84146776"
"614491094"
"858288490"
"233737533"
"596329199"
"407624600"
"914507058"
"542168099"
"712520407"
"799033655"
"647952790"
"676238955"
" 73593845"
" 29433057"
"623875730"
"605657986"
"181997463"
"392929417"
"413591636"
"961617392"
"615521992"
"482724033"
"241385274"
"916674765"
"427580284"
"492603810"
"964587113"
"409672489"
"736886930"
"608744626"
"286101397"
"423085234"
"825911584"
"179161653"
"760952816"
"427110646"
"464081876"
"   826571"
"393363465"
"383761177"
"213759910"
"432686483"
"930823905"
" 23028047"
"357951214"
"  7425980"
"614662240"
"422892489"
"374338778"
"555637904"
"126540821"
"739675508"
"472404576"
" 39232745"
"942650037"
"596069844"
"604527723"
"835247491"
" 97071151"
"613899603"
"801925155"
"760216861"
"526836113"
"934824051"
" 72795402"
"990738615"
"128421208"
"722801110"
"983761305"
"302445739"
"272592299"
"467876550"
"878542300"
"386285575"
"984174632"
"529942935"
"878009511"
"432085217"
"786402773"
"109912653"
"174042848"
"743754005"
" 21205425"
"993026827"
"660075864"
"548656940"
"305987964"
"733407460"
" 75438371"
"692457131"
"918606837"
"639777849"
"685792409"
" 40196887"
"  6149391"
"162175826"
"669949789"
"409589304"
"334403958"
"655109436"
"128615550"
"984780287"
"181974307"
"505169248"
"246249655"
"791416671"
"943476228"
"651960875"
"898509739"
"207393737"
"751326876"
"729170771"
"824157789"
"513348459"
"467348100"
"130825010"
"374859031"
"157323738"
" 64448961"
"162881115"
"656399406"
"556859018"
"718237451"
"353164452"
"357749841"
"415700891"
"489958821"
" 14627120"
"420992619"
"203796566"
"611286591"
"860924083"
"835553331"
"893338274"
"292945157"
"756170056"
"651068604"
"254949815"
"564078426"
"137803885"
"381519658"
"471438609"
"784795510"
"652100137"
"748248798"
"228313944"
"134537878"
"495643352"
"301112191"
"752315559"
"304674433"
"826855215"
"332619172"
"680591699"
" 44434891"
"696837358"
"472402241"
"607276375"
"646713589"
"500073824"
"521903663"
"960753812"
"170174087"
" 63316901"
"107727434"
"660775316"
"554053116"
"928417862"
" 46413265"
"653063188"
"208684003"
"577828261"
"766363633"
"360133976"
"226188323"
"847033187"
"159744143"
"483096082"
"471095906"
"184217642"
"689353443"
"621894346"
"716119332"
"804158721"
"424381774"
"884421250"
"694132034"
" 39423539"
"903930484"
"719253212"
"361404462"
"283034577"
"474960818"
" 37250462"
"602364212"
"782836459"
"951228665"
"494300834"
"514468303"
"246042789"
"790393267"
"204276490"
"643470107"
"597716739"
"876970842"
"979100122"
"556122987"
"676352264"
"473795366"
"983118259"
"784360979"
"107664010"
"765135107"
"908519176"
"118790594"
"486987018"
"366975387"
"380488920"
"530549710"
"166944058"
" 24752628"
"302276999"
" 55534623"
"297631589"
"124274532"
" 95855828"
"275590738"
"347009924"
"330039357"
"360250555"
"713728117"
"333420406"
"933638630"
"741917500"
" 63383970"
"216707616"
"231134867"
"130977901"
"918159822"
"975224874"
"679475034"
"732085567"
"108387904"
"105191466"
"910443524"
"948963403"
"415949249"
" 57881355"
"828407654"
"495417359"
"513917335"
"360987663"
"244355951"
"372257089"
"481767090"
"138906751"
"321008092"
"582948099"
"560799026"
"185614120"
"458152345"
"452945061"
"715158924"
"499731105"
"179464695"
"227350391"
"585316093"
"452236392"
"864420565"
"617543735"
"117421089"
"287738180"
"143321254"
"817926794"
"408405928"
"174390144"
"299937210"
"786426941"
" 16988638"
" 17077484"
;

int main(){
	long n=0;
	char rbuf[64];
	read(0,rbuf,sizeof rbuf);
	char*rp=rbuf;
	long c;
	while(c=*rp++-48,c>=0){
		n=n*10+c;
	}
	write(1,mbd+n*9,9);
	_exit(0);
}