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

#define rd(v) long v=0;{int _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;}

char mbd[]=
"         0"
"         0"
"         0"
"         4"
"        10"
"        32"
"       122"
"       544"
"      2770"
"     15872"
"    101042"
"    707584"
"   5405530"
"  44736512"
" 398721962"
" 807514603"
" 783024024"
" 730683019"
" 759317219"
" 769818425"
" 371289856"
"  36927220"
" 815391573"
" 797770398"
" 910697047"
" 515268771"
" 233055153"
" 504205189"
" 874007202"
" 319292739"
" 892343420"
" 557596862"
" 679780238"
" 557662589"
" 191777039"
" 501497370"
" 624060592"
" 434298721"
" 520775362"
" 211811809"
" 178869480"
" 648185399"
" 963651725"
" 998576867"
" 721054419"
" 629912407"
" 607612769"
" 136560884"
" 972463528"
" 504067527"
" 752426958"
" 401368882"
" 539442550"
" 606072450"
" 868988524"
" 554122882"
" 451524595"
" 351509782"
" 394828940"
" 961583356"
" 866605286"
" 358952394"
" 801013419"
" 177236908"
" 268784107"
" 381492219"
" 405771025"
" 825036877"
" 456293768"
"  79761944"
" 139574341"
" 548320831"
"  44013438"
" 467404574"
" 669799489"
" 483147728"
" 857830260"
" 344934779"
" 432455786"
" 229713280"
" 798895662"
" 122283458"
" 558986660"
" 635550901"
"  17670049"
" 116131049"
" 642069816"
" 768582240"
" 555583718"
" 900631574"
" 246060227"
" 211296870"
" 130440616"
" 911369911"
" 767819922"
" 833493683"
" 886629332"
"  72825116"
" 518841716"
" 717557091"
"  53487067"
" 140911064"
" 580260576"
"  28049487"
" 146491605"
" 380681338"
" 344549361"
" 430316529"
" 715903421"
" 949160324"
" 469264544"
" 439771364"
" 799913890"
" 174774507"
" 151747064"
" 678274752"
" 811249908"
" 597170852"
" 415361716"
" 212829524"
" 353436788"
" 619525519"
" 155963428"
" 477726854"
" 112980177"
" 642261623"
" 823756906"
" 818039909"
" 234136141"
" 835823635"
"  97772784"
" 617632623"
" 632130220"
" 215407540"
" 246616082"
" 589982577"
" 277985101"
" 640029901"
" 112054432"
"  77884540"
" 859191272"
" 473155487"
" 468821558"
" 639199426"
" 933566506"
" 983185417"
" 863187117"
" 196228720"
" 418519941"
" 686937155"
"   3357815"
" 878369623"
" 442984860"
" 343757926"
" 787436276"
" 473895557"
" 756412625"
" 629149946"
" 173674937"
" 950862155"
"  50600333"
" 200732351"
" 955537225"
" 541142908"
" 631218044"
" 999391051"
" 136494375"
" 101295256"
" 626288881"
" 661215274"
" 449886615"
" 359050757"
" 530178944"
"    122115"
" 925866424"
" 303198650"
"   3149520"
" 556146009"
" 344778780"
" 204820437"
"   3865651"
" 127629217"
" 463441868"
" 730019414"
" 491515472"
" 149254115"
" 508686407"
" 895304916"
" 429867274"
" 907874248"
" 703949759"
" 124643885"
" 130341136"
" 147897473"
"  39850206"
" 314012990"
" 985393032"
"  76825376"
" 748290682"
" 118167558"
" 112828968"
" 361234870"
" 131677985"
"  92689018"
" 414230170"
" 644723421"
" 267466534"
" 390442845"
" 302079334"
"  21563845"
" 464101570"
" 944661069"
" 131989690"
" 451316963"
" 234035266"
" 548927780"
" 874196636"
" 886459383"
" 612096544"
" 591250812"
" 515062849"
" 993530304"
" 296943088"
"  96731353"
" 251598855"
" 367497571"
" 540977045"
" 302175768"
" 368966690"
"  98920396"
" 804495291"
" 983254450"
" 229798685"
" 104722682"
" 648718512"
" 979323706"
" 577897188"
" 566702386"
" 634610977"
" 663421989"
" 630024096"
" 252373816"
"  99885574"
" 930285332"
" 628267329"
" 486643616"
" 557762989"
"  53332343"
" 269866415"
" 375427602"
" 298336424"
" 646013548"
" 729509817"
" 367453205"
" 948306269"
" 894056100"
"  50391246"
" 679490865"
" 939010521"
" 162375567"
" 860236469"
" 372739837"
" 890994594"
" 455311200"
" 190073506"
" 247309612"
" 855322013"
" 581039885"
" 290221739"
" 713979083"
" 459110361"
" 203327956"
" 351939730"
" 167479199"
" 693945968"
" 718000028"
" 147544466"
" 961739778"
" 444949463"
" 844665667"
" 898237835"
" 261903139"
" 372627223"
" 667364363"
" 822906599"
" 698827423"
" 520545336"
" 116326339"
" 264373529"
" 742889267"
" 191976039"
" 553500537"
" 241732418"
"  80161996"
" 374634127"
" 558601906"
" 251345140"
" 258087806"
"   3464849"
" 493735662"
" 692892583"
" 818871830"
" 615441363"
" 761768913"
" 857090673"
" 932400921"
" 443441532"
" 667403458"
" 344361245"
" 374845571"
" 340185031"
" 755762158"
" 353381303"
" 287630357"
" 298121268"
" 149793984"
" 870341503"
" 947689223"
" 893084075"
" 870902442"
" 662649595"
" 746501782"
" 965662116"
" 377361628"
" 480127996"
" 796434578"
" 848144426"
" 942351407"
" 880740199"
" 593137382"
" 418748410"
" 647542137"
" 711092020"
"   7940312"
" 663113374"
" 554676586"
" 554073015"
" 712473186"
" 522566452"
" 998284045"
" 978460523"
" 318683906"
" 374806931"
" 414208471"
" 282095826"
" 803921612"
" 779369974"
" 791506448"
" 208426697"
"   8509337"
" 205414185"
" 822042603"
" 128407531"
" 350963829"
" 778020821"
" 132989458"
" 264676356"
" 738459086"
" 869551655"
" 187361402"
" 413387550"
" 769775902"
" 592417626"
" 588824782"
" 721198747"
" 908569329"
" 903326536"
" 576093462"
" 594982233"
" 884335359"
" 517855425"
" 391012731"
" 234468253"
" 487941950"
" 172825410"
" 498518286"
"  82102860"
" 414834504"
" 740747160"
"  29583378"
" 514104741"
" 865651904"
" 387581886"
" 880290145"
" 246090266"
" 871407825"
" 860583928"
" 154214594"
" 462615141"
" 632784358"
" 323255473"
" 453187019"
" 643706538"
" 310507016"
" 340085833"
" 183839453"
" 575524174"
" 564027370"
" 628330099"
" 173635200"
" 919161559"
" 779906805"
" 572442716"
"  64284890"
" 693852918"
" 557128258"
" 374649130"
" 448737477"
" 446775424"
" 661555290"
"  51428632"
"  38017932"
" 590393232"
" 713285903"
" 246032305"
" 958006461"
" 124470203"
" 471576771"
" 552384328"
" 612607669"
" 198240658"
" 935105082"
" 267633528"
" 792179773"
" 142226950"
" 888890464"
" 634129185"
"  26381424"
" 847455825"
" 380056587"
" 868652708"
" 535632069"
" 741196638"
" 249784686"
"  51389309"
" 178407321"
" 788779065"
" 145392910"
" 235405569"
" 492793711"
" 214625118"
" 151540930"
" 439142413"
" 859658747"
" 437524669"
" 214292948"
" 537005072"
" 588286542"
" 885334589"
" 815410900"
" 316804080"
" 131766876"
" 112686982"
" 461909567"
" 457223906"
" 122476865"
" 778845987"
" 323627801"
" 785520242"
" 113198561"
" 127570757"
" 781886800"
" 370361748"
" 377726394"
" 933142146"
" 860322215"
" 381585008"
"  36309900"
" 197615948"
" 745394556"
" 124947636"
" 701547860"
" 813879507"
" 200723274"
" 177189428"
" 126928945"
" 106374526"
" 857007175"
" 108139991"
" 366964263"
" 884596820"
" 974766391"
" 821775413"
" 420867310"
" 634180366"
" 794277884"
" 859930276"
" 340212096"
" 454087758"
" 892819521"
" 233141233"
" 290135732"
" 240091004"
" 886871421"
" 552317110"
" 676147429"
" 460679447"
" 712913046"
" 843034359"
" 688374322"
" 131603300"
" 600963909"
" 467769062"
" 831901803"
"  77940649"
" 654834918"
" 551351770"
" 332867340"
"  63861494"
" 221325644"
" 684354042"
" 518797277"
"  70834124"
" 574090485"
" 754291463"
" 571783003"
" 966274836"
" 687471134"
" 453169848"
" 618947028"
" 996699034"
" 226448682"
" 218699669"
"  57317017"
" 617395963"
" 817175269"
" 415809681"
" 391351717"
" 114087870"
" 934140775"
" 389799736"
" 610020102"
" 995707080"
"  32508992"
" 557272663"
" 197635502"
"  19116214"
" 705324212"
"  85831369"
" 441424295"
" 533450491"
" 455244969"
" 934708586"
" 961159129"
" 933081479"
" 162013294"
" 506398826"
" 686563839"
" 888738701"
" 460892456"
" 736336998"
" 884778801"
" 719401071"
" 229522378"
" 643459688"
" 526730472"
" 589208196"
" 475127357"
" 757847084"
" 795571278"
" 794720171"
" 349638514"
"  66750335"
" 386410184"
" 443260467"
" 416968610"
" 545301048"
" 622309388"
" 816348688"
" 537429050"
" 626206472"
" 644985737"
" 793003541"
" 748077342"
" 749083813"
" 823822792"
" 534780423"
" 800263405"
" 911661985"
" 520205774"
" 326453565"
" 659204273"
" 743199842"
" 583226143"
" 203127399"
" 641947121"
" 560227074"
"  81471376"
" 910335865"
" 438579104"
" 336125152"
" 616666001"
" 389451759"
" 491716073"
" 327962943"
" 193588518"
"  92386098"
" 490707258"
" 208443155"
" 522530908"
" 812607338"
" 985560135"
" 979448274"
" 382462163"
" 880439059"
" 872215911"
" 293454675"
" 922081994"
" 417667278"
" 577276616"
" 479497804"
" 828178702"
" 867026680"
" 694874645"
" 802999719"
" 199479598"
" 916690208"
" 796915539"
" 925032021"
" 876186271"
" 133341434"
" 855038914"
" 802356156"
"  15545407"
" 674877366"
" 769023894"
" 953998773"
" 313088634"
"  76621378"
" 868996961"
" 253394330"
" 174774703"
" 782662385"
" 110929419"
" 174336949"
" 135487551"
"  26757797"
" 746930847"
" 216144330"
" 813931942"
"  34112296"
" 955337044"
" 398503161"
" 508954669"
" 819557885"
" 508527194"
"  63148606"
" 506079846"
"  91255281"
" 181686910"
" 947117341"
"  16462081"
" 591213619"
" 243229959"
"   2156358"
" 578936767"
" 829734544"
" 362387936"
" 336446376"
" 635491036"
" 633877582"
" 880531592"
" 981636776"
" 681929043"
" 430590656"
" 796221084"
"   3105935"
" 816309823"
" 900694640"
" 460771738"
" 379526023"
" 580009106"
" 717044786"
" 162294318"
" 550201320"
" 563672922"
" 905593096"
" 970702597"
"    521340"
" 857428273"
" 566361844"
"  40949098"
" 895899845"
"  29462465"
" 568499056"
" 245117934"
" 768515824"
" 109612689"
" 298957873"
" 419403794"
" 440372361"
"  45074648"
" 445101206"
"  89838673"
" 531795093"
" 538400128"
" 120516226"
" 568609887"
" 147870016"
" 646019860"
" 258355116"
" 920234398"
" 248531844"
" 936017112"
" 332188042"
" 264738505"
" 432379525"
" 897647313"
" 313099967"
" 551208091"
" 777905574"
" 344606222"
" 643796983"
"   9471126"
" 307356258"
" 135706085"
" 170661297"
" 708861865"
" 485226210"
" 166546899"
" 445741468"
" 288947673"
" 996056195"
" 663270092"
" 146007891"
" 657441911"
" 104979740"
" 718895404"
" 301108765"
" 219977834"
" 341306207"
" 701315533"
" 489634345"
" 529492314"
" 914277013"
"  42406602"
" 424135018"
" 778227452"
" 223664605"
" 884457247"
" 565839047"
" 561083974"
" 210401609"
" 253902012"
"  81561526"
" 981511477"
" 920690956"
" 819897840"
" 263435204"
" 432310865"
" 231990840"
"  59987136"
" 424683294"
" 176305871"
"  27312532"
" 963092356"
" 708712970"
" 719376529"
"  94355957"
" 712821990"
" 148842428"
" 420591514"
"  55647087"
" 775342027"
" 967887423"
" 338768512"
" 533851201"
" 422527824"
" 757358774"
" 579509747"
" 991220568"
"  71097616"
"  36524994"
" 826930566"
" 694390215"
" 703031903"
" 366728060"
" 967213344"
" 915243061"
" 978743022"
" 320622353"
"  62446623"
"  95997301"
" 790462725"
" 534307123"
" 773961690"
"  33036268"
" 995294087"
" 999111671"
" 121197923"
" 949453194"
" 545953337"
" 801628974"
" 720025575"
" 228313576"
" 101577221"
" 917052123"
" 432757508"
" 338858700"
"  69007361"
" 657205638"
" 481301691"
" 112621872"
" 429211202"
" 670640587"
" 653425480"
" 998413199"
" 363226889"
" 549323244"
" 558185323"
" 242813600"
" 518324443"
" 567862047"
" 408655559"
" 951154831"
" 804667676"
" 215725637"
" 241181232"
" 548898097"
" 256635286"
" 433325628"
" 370113256"
" 846776087"
" 359033376"
" 100504646"
" 605123473"
"  27192490"
" 523489986"
" 845229462"
" 282269853"
" 645236197"
"  64104804"
" 177757671"
" 327931341"
" 753291852"
" 467901797"
" 717031149"
" 532911426"
" 415364984"
"  68790306"
" 369610219"
" 884576753"
" 193894478"
" 862018274"
" 357926564"
" 997192357"
"  77410855"
" 791720824"
" 686292812"
" 128598503"
" 140361449"
" 750907915"
" 909824832"
" 241974472"
" 981225810"
" 940595302"
"  25995736"
" 381108085"
" 742866320"
" 483762034"
" 625109114"
"   5363118"
" 186267313"
"  59624838"
" 305941917"
" 259771392"
" 642670819"
" 887320011"
" 578851071"
"  84032828"
" 458740697"
" 691251621"
" 968348328"
" 823101964"
" 155462073"
" 112018885"
" 741558019"
" 859637200"
" 918829512"
" 339655867"
" 745538637"
" 106215917"
" 412111765"
" 741271779"
"  36964032"
" 824315803"
"  39285549"
" 438039843"
" 428944752"
" 785552398"
" 210905696"
" 350032427"
" 558941476"
" 238407268"
" 849455458"
" 398148614"
" 965998893"
" 940164930"
" 902175228"
" 134917099"
" 219840105"
" 498660930"
" 871805842"
" 405883719"
" 350332711"
" 798116658"
" 582289064"
" 183752307"
" 512553427"
" 707724462"
" 847259114"
" 622282016"
" 776623083"
" 541140499"
" 419130319"
"  10753369"
"   7655571"
" 924441940"
" 366825652"
"  29196795"
" 512217244"
" 551692995"
" 210696061"
" 824200198"
" 891685086"
" 158649678"
" 722618992"
" 588025654"
" 241474848"
" 998216833"
" 492775081"
" 953380197"
" 667963685"
" 228096252"
" 623251909"
" 122371402"
" 860758641"
" 648801131"
" 353733370"
" 994733419"
"  91665394"
"  83168284"
" 201446826"
" 279923772"
" 286188114"
" 566876690"
" 656631153"
" 629729667"
"   2180851"
" 856827909"
" 952096782"
" 213079425"
" 846152623"
" 689164996"
" 412428536"
" 454226533"
" 255267273"
"  53168734"
" 894631779"
" 113196328"
" 209859561"
" 886958459"
"  31840107"
" 579298732"
" 547318921"
" 713239439"
" 913085989"
" 904900919"
" 287466716"
" 761135938"
" 667015721"
" 368415842"
" 567265722"
" 880973199"
" 390153549"
" 350917050"
" 189237840"
" 546559763"
" 742366934"
" 769661951"
" 708561249"
" 438161618"
" 866335967"
" 485424032"
" 821921354"
" 188197756"
" 545567127"
" 752908321"
" 874244944"
"  75596438"
" 866106052"
" 902306385"
" 565656486"
" 379184467"
" 342617819"
" 399967889"
" 301593662"
" 574903041"
" 416701187"
" 467604135"
" 238541541"
" 343942697"
" 609569164"
" 429136595"
" 837734770"
" 985932857"
" 608826339"
" 272323853"
" 372533887"
" 346849040"
" 700733080"
" 364335810"
" 766614006"
" 509321647"
" 332791394"
" 847496051"
" 535784123"
" 630273781"
"  90361972"
" 573333083"
"  86914121"
" 296727861"
"  82326677"
" 727640584"
" 504364737"
" 260244398"
" 809802217"
" 891246340"
" 743959683"
" 361572720"
" 579682934"
" 872948614"
" 205146119"
" 141651139"
" 946645817"
" 142497755"
" 621852506"
" 348990960"
" 492354675"
" 823785462"
" 460225043"
" 365683064"
" 477917879"
"  40537929"
" 573302739"
" 964952310"
" 664117262"
" 447934956"
" 758479868"
"  94016824"
" 679394647"
" 241103560"
" 702861010"
" 652383012"
" 455549664"
" 169746995"
"  67226326"
" 487140463"
" 165624815"
"  50581883"
" 308564110"
" 127636367"
"  72478115"
" 972514697"
" 139265829"
" 346636359"
" 107803740"
"  68274798"
" 142710476"
" 915048323"
" 441025108"
" 233640114"
" 684157282"
" 941925731"
" 679729808"
" 172180556"
" 986792271"
" 713303013"
" 778414308"
" 563879303"
" 571564875"
" 566014503"
" 763447049"
" 993754291"
" 888971216"
" 718586331"
" 261257842"
" 407710790"
" 131763003"
" 650543083"
" 404470830"
" 176149581"
" 996191364"
"  46985102"
" 656694609"
" 775781077"
" 874441030"
" 883022645"
" 142423300"
" 499907125"
" 941618838"
" 264581829"
" 406587220"
" 173687323"
"   4788644"
" 163028636"
" 302531561"
" 479922486"
" 351223397"
" 433129719"
" 505114814"
" 753138565"
"  20038476"
" 545162237"
"   6070798"
" 620590587"
" 498924301"
" 460168911"
" 271473790"
" 975007746"
" 386578129"
" 288769215"
" 433619244"
" 842103631"
" 562702582"
" 700206862"
" 499816598"
" 160507566"
" 257863333"
" 916216922"
" 147307927"
" 859564947"
" 673047465"
" 847776423"
" 603288874"
" 254538730"
" 583934725"
" 125988313"
"  61663649"
" 601846955"
" 619766708"
" 189151673"
" 630945777"
" 685767452"
"  45644148"
" 370977611"
"  47664296"
"   2244538"
" 556063876"
" 954296337"
" 972764017"
" 173155597"
"  55466158"
" 371229555"
" 869713346"
" 368273407"
" 421796274"
" 162938589"
" 342713671"
" 873037128"
"  30733161"
" 792567613"
" 769030934"
" 707723285"
" 464430592"
" 658326895"
" 754201017"
" 701133942"
" 301226056"
" 742353504"
" 521551938"
" 769191713"
" 801703997"
" 636674631"
" 742314557"
" 109796675"
"   2204186"
" 688950495"
" 820661600"
" 991438838"
" 990156517"
" 205304924"
" 213579050"
" 871473534"
" 471572367"
" 231531027"
" 170644710"
" 564297532"
" 346710610"
" 390450620"
" 724531281"
" 722408922"
" 475699918"
" 666351730"
" 999836727"
" 115504962"
" 215663786"
" 199161492"
" 402553313"
" 314105790"
" 802737945"
" 274635886"
" 271739261"
" 781592234"
" 667177197"
" 272284609"
" 131192766"
" 882585108"
" 504297866"
" 230633642"
" 129645418"
" 652233859"
"  88402855"
" 265346434"
" 809047130"
" 715337773"
"  32803319"
" 142392796"
" 731778672"
" 205985534"
" 944619036"
" 680803402"
" 704826760"
" 375366198"
"   4430260"
" 104717441"
" 963421535"
"  90671772"
" 370570279"
" 127035358"
" 251648514"
" 149850908"
" 159314269"
" 556020893"
" 773508795"
" 341159208"
" 960663074"
" 792803982"
" 859536831"
" 122326358"
" 975689743"
" 216359080"
" 239616269"
"  90676294"
" 467773846"
" 576059816"
" 694748461"
" 165809158"
"  94478346"
" 346250200"
" 319345677"
" 384491254"
" 415058999"
" 347223530"
" 778240935"
" 659602085"
" 382284800"
" 673413443"
" 248284005"
"  45317362"
" 190513031"
" 134871900"
" 813762936"
" 191634240"
" 979823958"
" 830183839"
" 603787233"
" 637509955"
" 361247523"
" 881253731"
" 758600679"
" 106314106"
" 708572830"
"  71290669"
" 709304052"
" 861216626"
" 574283540"
" 691671754"
" 453143605"
" 942115537"
" 573584426"
" 877378156"
" 378716703"
" 837772053"
" 227610215"
"  27583754"
" 645140368"
" 791636618"
" 447801421"
" 773069696"
" 730878326"
" 969798286"
" 719499665"
" 260451104"
" 715576907"
" 618976265"
" 250548939"
" 922571505"
" 123700065"
" 923820439"
" 319600663"
" 961079771"
" 321600337"
" 285617104"
" 180844072"
"  77263986"
" 365041874"
" 390525279"
" 611873070"
" 498218215"
" 385384728"
"   3834581"
" 763252289"
" 726489844"
" 289302496"
" 523106797"
" 301328786"
" 845599828"
"  48379801"
" 272268296"
" 651056337"
" 147454816"
" 167227805"
" 922241260"
" 785154518"
" 325655101"
" 174733820"
" 957664274"
" 233496021"
" 667297590"
" 994004339"
" 624163512"
" 752780685"
" 324085477"
" 816829964"
" 576163616"
" 517985262"
" 126442208"
" 319492773"
"  37239317"
" 137096945"
" 897169801"
" 478955224"
" 752088539"
"  73489545"
" 858009386"
" 638492967"
" 425397701"
" 927038745"
" 944585919"
" 139668113"
"  64471505"
" 521755089"
" 533591621"
" 462457318"
" 290959117"
" 419543568"
" 332330081"
" 644344129"
" 151614199"
" 770980324"
" 430522370"
" 195142682"
" 568597845"
" 804150500"
" 743554297"
" 817967806"
" 888887972"
"  64417296"
" 255295256"
" 944220028"
" 355829158"
" 823013613"
" 590427231"
" 273797437"
"  88851659"
" 733288348"
"  87389261"
" 789435031"
" 456569743"
" 523450486"
" 520744051"
" 330896067"
" 443579657"
" 451558116"
" 819833128"
" 494490667"
" 750942831"
" 323187268"
" 887256264"
"  98888846"
" 521524249"
" 542758496"
" 210416731"
" 798951790"
" 749455304"
" 739456721"
" 451505499"
" 940776907"
"  93088088"
" 176690041"
" 682302170"
" 874807888"
" 645850563"
"  81090099"
" 278002936"
" 275653542"
"  53751368"
" 292194054"
" 627051482"
"  11558655"
" 697566221"
" 426652071"
" 834849194"
"  32050588"
"  35627408"
" 646736093"
" 650767139"
" 527777244"
" 215956909"
" 650796834"
" 975789037"
" 124453966"
"  36887374"
" 435329291"
" 937967403"
" 799606062"
" 792345064"
" 793583615"
" 770034297"
" 325264155"
" 256709098"
" 788553353"
" 947413795"
"  27505763"
" 688749699"
" 879308818"
"  75206954"
" 260366622"
" 681623703"
" 235206163"
" 521485999"
" 255582151"
" 584422236"
" 633132237"
" 752436045"
" 143819076"
" 512716944"
" 312533296"
" 269160688"
" 848001787"
" 645752163"
" 105813934"
" 613861904"
" 605963129"
" 941606157"
"  93949505"
" 201261621"
" 420642165"
" 176242708"
" 708280317"
"  33668077"
" 368910062"
" 289862642"
" 647800687"
"  68146695"
" 337948515"
" 828153691"
" 868034204"
" 332769134"
"  34076068"
" 997772229"
" 440518519"
" 567201350"
" 949088586"
" 465395625"
" 233166139"
" 184488833"
" 333647155"
" 475646466"
" 388311666"
" 897970633"
" 469756762"
" 311063714"
" 562754966"
" 581911022"
"  55348982"
" 275947586"
"  36502676"
" 930727846"
" 519874951"
" 661857613"
" 570570458"
" 624942073"
" 154174082"
" 595482491"
" 914786709"
" 345709947"
" 680798530"
" 723875375"
" 264767722"
" 318400755"
" 506125564"
"  20908890"
" 356087556"
" 627202025"
" 612322161"
" 624727806"
" 986717590"
" 759048560"
" 944462740"
" 416942968"
" 818542084"
" 743253305"
" 846167135"
" 654025095"
" 704133007"
"  74406045"
" 416082889"
" 468274477"
" 600581563"
" 781334731"
" 823576976"
" 705309363"
" 423264272"
" 700113171"
" 234850949"
" 432929582"
" 419515856"
" 133815056"
" 872148013"
" 448663309"
" 942647840"
" 973172806"
" 117281922"
" 522867631"
"  19005911"
" 135584406"
" 752727043"
" 173853664"
" 980658379"
" 975715580"
"   6289784"
" 418991632"
" 126337562"
" 426968385"
" 966237849"
" 803649608"
" 705630724"
" 619235196"
" 421858602"
" 313911263"
" 669074630"
" 538873152"
" 172886129"
" 263417173"
" 942032858"
" 785180879"
"  94986894"
" 734771654"
" 639039012"
" 891891209"
" 881156605"
" 909719211"
" 549545426"
" 457131849"
"  88271051"
" 527514054"
" 415780959"
" 608820934"
"  90679001"
" 877525097"
" 219754225"
"  38094972"
" 793161988"
" 215868895"
" 563577239"
" 160763584"
" 897814371"
" 842930154"
" 849402330"
" 920413595"
" 610980834"
" 190059016"
" 588106569"
" 710346322"
" 205573094"
" 931954533"
" 353964064"
" 731429934"
" 289706897"
" 642120931"
" 571421088"
" 320532218"
" 664790954"
" 444760013"
" 727068849"
" 257646548"
"  24324574"
" 884244759"
" 937677478"
" 782607115"
" 560954996"
" 156964995"
" 953549567"
" 213514558"
" 542211439"
" 231620659"
" 750834654"
" 846130201"
" 157894020"
" 585945272"
" 200905333"
" 255701814"
" 535625949"
"  88346480"
" 140624090"
" 139811540"
" 372380792"
"  35580874"
" 239691669"
" 199529237"
" 144055189"
" 764931283"
" 649105871"
" 567819603"
" 511113543"
"  55129240"
" 515113719"
" 742874470"
" 357546566"
" 470754294"
" 323821231"
" 637349533"
" 331701350"
" 395674452"
" 689259657"
" 240464265"
" 823737949"
" 713610547"
" 509804875"
" 917152821"
" 850996099"
" 803802891"
"  41233631"
" 110597937"
" 633669612"
" 943481019"
" 577913352"
"   6212629"
" 455747622"
" 873442624"
" 170010571"
" 907456796"
" 735997038"
" 131020744"
" 863049479"
" 213221277"
"   3861745"
" 264375272"
" 777517013"
"  56566958"
" 105680662"
" 131130289"
" 404905310"
" 788998631"
" 714520648"
" 291948254"
" 264969750"
" 564793621"
" 350016236"
" 512506062"
" 622454423"
" 336799069"
" 244082425"
" 530403084"
" 651949523"
" 964511942"
" 198435762"
" 303694569"
" 827607710"
" 950741328"
" 832389951"
" 660088120"
" 726031350"
" 725132508"
"  86197844"
"   8797023"
" 872942438"
" 227597472"
" 291888837"
" 858003203"
" 849404167"
" 524864171"
" 151191337"
" 813091927"
" 412941946"
" 795542364"
" 167241763"
"  26872716"
" 301952535"
" 744909089"
" 870354194"
" 605524573"
" 957407091"
" 705969752"
" 187234246"
" 644014463"
" 941953272"
" 165178175"
" 190917339"
" 801271449"
" 902966849"
" 443767848"
" 619254507"
"  38418081"
" 510330986"
" 529503501"
" 212764085"
" 958853085"
" 645774954"
" 494381200"
" 152675641"
" 673850549"
" 887819174"
" 469558704"
" 806700034"
" 227569109"
" 154853214"
" 442888459"
" 232948517"
"  35927991"
" 750830190"
" 959716299"
" 867390289"
" 568890229"
" 752489383"
" 768402709"
" 439500002"
"  19540581"
" 889068031"
"  14743078"
" 919740721"
" 618741577"
" 415289461"
" 482376721"
" 505042175"
" 224742347"
" 247492875"
" 488606952"
" 345940326"
" 533513078"
" 137604140"
" 693229935"
" 219947669"
" 385158788"
" 954995681"
" 184709562"
" 714494301"
" 919816822"
" 189459702"
" 458585062"
" 819560942"
" 470304610"
" 331318392"
" 901158986"
" 385934988"
" 702458396"
" 597533515"
" 800400113"
" 941800199"
" 667249296"
" 610144405"
" 237171935"
" 560331832"
" 139875518"
" 792006771"
" 372715912"
" 322829291"
" 583676130"
" 408236814"
" 662109255"
"  57063450"
" 772959596"
" 129398059"
" 987434452"
" 314145527"
"  60022629"
" 902884913"
"  45462842"
" 620186760"
" 297337398"
" 708842564"
" 640570034"
" 532942407"
"  88034185"
" 983190009"
" 320048834"
" 891482718"
" 245971576"
" 249387562"
" 420169177"
" 781316498"
" 158196122"
" 644482471"
"  65203348"
" 934201350"
" 480977989"
" 847507916"
" 586569794"
" 839817185"
" 515305149"
" 929289513"
" 372811683"
" 170828127"
" 194281832"
" 795056386"
" 201770924"
" 835306627"
" 836372791"
" 183624469"
" 340986490"
" 326627284"
" 272620964"
" 886451865"
"  31125402"
" 118502929"
" 659637238"
" 150537310"
" 811786756"
" 858675192"
" 387400558"
" 600565529"
" 117979019"
" 381036870"
" 634612852"
" 270485693"
"  27802040"
" 388459578"
" 508198359"
" 220693802"
"  77711094"
" 445595441"
" 187460642"
" 209566583"
" 822304678"
" 225249162"
" 118282336"
" 324350609"
"  34554995"
" 597004162"
" 968032242"
" 427201027"
" 518334744"
" 825181375"
" 587513218"
" 822087608"
" 563639179"
" 634382746"
" 893419598"
" 197208282"
" 973120916"
" 563568705"
" 741596548"
" 711127475"
" 721685785"
" 476031577"
" 698894674"
" 713954962"
" 472467014"
" 157035772"
" 361674310"
"  44277000"
" 761862716"
" 153773052"
" 295621316"
"  56069918"
" 682304522"
" 384215125"
" 877777024"
" 265572240"
" 419761091"
"  34673995"
"  29993139"
" 288281584"
" 218269296"
" 476490926"
" 837732205"
" 656376147"
" 696777897"
" 328149670"
" 704127613"
" 268806653"
" 995376280"
" 590815733"
" 785485816"
" 187337222"
" 267914928"
" 672111218"
" 384364277"
" 138337861"
"  21256848"
" 655467144"
" 332713762"
" 117104179"
" 346089257"
"  35152408"
" 563400781"
" 650513644"
" 666064767"
" 542443625"
" 314905788"
" 851583972"
" 698883508"
"  23170528"
" 589662571"
"  60149827"
" 351779418"
" 162290118"
" 200627484"
" 218850613"
"  54189885"
" 680627870"
" 593364046"
" 616526276"
" 393586047"
" 740900561"
" 281768266"
" 218317153"
" 182846198"
" 964302768"
"  45923774"
" 682388088"
" 968712175"
" 114228944"
"   2702607"
" 726949502"
" 830440019"
" 243473059"
" 107987078"
" 709669173"
" 381733842"
" 647218042"
" 516589188"
" 598782970"
"  95066915"
" 458986576"
" 329398215"
" 486863825"
" 679899334"
"  49466112"
" 995084401"
" 762839101"
" 162569933"
" 877078677"
"  53304078"
" 489566896"
" 327384088"
" 146934751"
" 651857825"
" 417145078"
" 954005945"
" 400929532"
" 280866797"
" 240218330"
" 707711464"
" 184538634"
" 679138585"
" 225463020"
" 920736625"
" 732465059"
" 694483371"
" 435039219"
" 832473841"
" 146148984"
" 900391670"
"  40384242"
" 739436154"
" 119401736"
" 328617020"
" 362040005"
" 796469065"
" 162221431"
" 154273180"
" 236003560"
" 674391458"
" 201499955"
" 243567037"
" 575393338"
" 789507271"
"  65063193"
"   9550730"
" 664587431"
" 660484589"
" 214839159"
" 720610543"
" 366880169"
" 748609904"
" 354459243"
" 219950902"
" 184508073"
"  31092039"
" 283539038"
" 272093743"
" 571695724"
"  62223446"
" 314483893"
" 693432785"
" 207705292"
" 518859827"
"  20322827"
" 194497546"
" 518769944"
" 365859604"
" 773676193"
" 422667322"
" 254936125"
;

main(){
	char rbuf[64];
	read(0,rbuf,sizeof rbuf);
	char*rp=rbuf;
	rd(n);
	write(1,mbd+n*10,10);
	_exit(0);
}