10 1 11 0 12 1 13 1 14 2 15 2 16 4 17 4 18 7 19 8 20 12 21 14 22 21 23 24 24 34 25 41 26 55 27 66 28 88 29 105 30 137 31 165 32 209 33 253 34 318 35 383 36 474 37 573 38 701 39 844 40 1027 41 1231 42 1487 43 1780 44 2134 45 2547 46 3041 47 3614 48 4294 49 5092 50 6022 51 7117 52 8389 53 9882 54 11607 55 13638 56 15963 57 18702 58 21834 59 25504 60 29694 61 34600 62 40178 63 46696 64 54104 65 62722 66 72509 67 83871 68 96747 69 111656 70 128550 71 148035 72 170104 73 195501 74 224225 75 257199 76 294481 77 337146 78 385363 79 440421 80 502579 81 573396 82 653311 83 744132 84 846557 85 962739 86 1093638 87 1241842 88 1408716 89 1597269 90 1809422 91 2048751 92 2317778 93 2620793 94 2961151 95 3343893 96 3773448 97 4255840 98 4796718 99 5403335 100 6082935 101 6844119 102 7696144 103 8649363 104 9715328 105 10906571 106 12237564 107 13723334 108 15381950 109 17231593 110 19294517 111 21592821 112 24153938 113 27004538 114 30178370 115 33707843 116 37634060 117 41996488 118 46845249 119 52228151 120 58206197 121 64837509 122 72195860 123 80352004 124 89395157 125 99411073 126 110507536 127 122788690 128 136384135 129 151420325 130 168053141 131 186435602 132 206755003 133 229196619 134 253984765 135 281343658 136 311541929 137 344850094 138 381589661 139 422086976 140 466725883 141 515899694 142 570066663 143 629699642 144 695345339 145 767571900 146 847030416 147 934402813 148 1030464328 149 1136031644 150 1252027329 151 1379428715 152 1519332108 153 1672905770 154 1841452102 155 2026365037 156 2229190909 157 2451591437 158 2695400460 159 2962596770 160 3255354304 161 3576025647 162 3927186435 163 4311631198 164 4732408315 165 5192833824 166 5696513975 167 6247378233 168 6849690187 169 7508102094 170 8227650047 171 9013836756 172 9872607587 173 10810463339 174 11834418353 175 12952146165 176 14171915077 177 15502774807 178 16954466153 179 18537650526 180 20263795879 181 22145452405 182 24196110349 183 26430531120 184 28864574029 185 31515584927 186 34402195743 187 37544774080 188 40965191952 189 44687346692 190 48736897499 191 53141859344 192 57932314074 193 63141080673 194 68803399197 195 74957688820 196 81645205652 197 88910889783 198 96803008120 199 105374093335 200 114680573427 201 124783814852 202 135749744143 203 147649995658 204 160561542645 205 174567952182 206 189759032449 207 206232208409 208 224092196934 209 243452502827 210 264435148114 211 287172290751 212 311806022532 213 338490125825 214 367389960526 215 398684358641 216 432565638437 217 469241639949 218 508935891300 219 551889803967 220 598363024241 221 648635789259 222 703009517551 223 761809331972 224 825384928780 225 894113292604 226 968399893198 227 1048681598418 228 1135428273471 229 1229145904378 230 1330378658533 231 1439712255165 232 1557776558595 233 1685249211316 234 1822858861504 235 1971389084870 236 2131682331099 237 2304644189875 238 2491248156524 239 2692540276723 240 2909644868885 241 3143769596279 242 3396212265181 243 3668366411554 244 3961729314404 245 4277908163179 246 4618629470205 247 4985745906745 248 5381247280586 249 5807268176503 250 6266100691030 251 6760202995577 252 7292214075688 253 7864963365307 254 8481487720017 255 9145042334625 256 9859120215055 257 10627464577475 258 11454091151461 259 12343302303576 260 13299712491243 261 14328264434844 262 15434258087669 263 16623369177295 264 17901682143688 265 19275711432591 266 20752438846252 267 22339338079768 268 24044416993502 269 25876245892148 270 27844005338182 271 29957518762881 272 32227306446157 273 34664623189470 274 37281519175087 275 40090883463919 276 43106512592582 277 46343160782067 278 49816617156806 279 53543763738368 280 57542662296105 281 61832621263659 282 66434293421369 283 71369753048043 284 76662605695865 285 82338077138130 286 88423136672628 287 94946599539860 288 101939265449204 289 109434036382055 290 117466072146343 291 126072925813226 292 135294718356468 293 145174294152824 294 155757417110852 295 167092949002154 296 179233069675680 297 192233481432193 298 206153656275609 299 221057069827023 300 237011479043837 301 254089189634258 302 272367367980833 303 291928346619985 304 312859974614272 305 335255966086741 306 359216293943338 307 384847587099658 308 412263572933423 309 441585529654707 310 472942783588042 311 506473223768767 312 542323861064419 313 580651412976564 314 621622932332781 315 665416471383072 316 712221788815572 317 762241103154159 318 815689888109579 319 872797726532600 320 933809205187662 321 998984882026817 322 1068602292913669 323 1142957046311870 324 1222363956233180 325 1307158280165442 326 1397696994089706 327 1494360191543445 328 1597552518582811 329 1707704753776593 330 1825275423408544 331 1950752584605402 332 2084655643347865 333 2227537365776245 334 2379985924425580 335 2542627165461149 336 2716126911905502 337 2901193517898784 338 3098580460940053 339 3309089218174749 340 3533572183656762 341 3772935905500103 342 4028144368805182 343 4300222637157340 344 4590260546484849 345 4899416799767083 346 5228923122644060 347 5580088865606770 348 5954305678589417 349 6353052681360519 350 6777901720853692 351 7230523177893455 352 7712691878739330 353 8226293613880320 354 8773331784114385 355 9355934716086711 356 9976363132382297 357 10637018358703820 358 11340450718156790 359 12089368735600845 360 12886648568502594 361 13735344326378215 362 14638698663374301 363 15600154344805328 364 16623366141421877 365 17712213789890618 366 18870815345493403 367 20103541700524362 368 21415031569945586 369 22810207751075146 370 24294293937147128 371 25872832922307112 372 27551705461088518 373 29337150646385737 374 31235787057502204 375 33254635565460894 376 35401143040396597 377 37683207867190311 378 40109206514630994 379 42688022076961080 380 45429074041277825 381 48342350207256667 382 51438440027901555 383 54728570299292196 384 58224642493161586 385 61939272653374801 386 65885833185716392 387 70078497448135009 388 74532286516118484 389 79263119008320755 390 84287863405249017 391 89624393713488679 392 95291647979876848 393 101309690466501527 394 107699777075095722 395 114484424780051183 396 121687484758847940 397 129334219914756495 398 137451386597483589 399 146067321141552336 400 155212031160512862 401 164917292129981053 402 175216749349388954 403 186146025714149572 404 197742835559799090 405 210047104896554197 406 223101098486013204 407 236949553952319985 408 251639823592296239 409 267222023935100109 410 283749193951694914 411 301277461810443697 412 319866221336134267 413 339578317901434262 414 360480245190709358 415 382642352382095232 416 406139063496202297 417 431049108262452234 418 457455766583433417 419 485447125741400123 420 515116352787513095 421 546561981036585683 422 579888213496259603 423 615205241922561954 424 652629584744400892 425 692284442309097460 426 734300073135281484 427 778814189374179145 428 825972375639134721 429 875928529148440526 430 928845325841071148 431 984894710150713829 432 1044258413628776718 433 1107128499836723808 434 1173707941260008912 435 1244211225401422456 436 1318864996393991348 437 1397908729033391898 438 1481595442189479933 439 1570192448242762574 440 1663982146155278902 441 1763262854581039933 442 1868349693300695238 443 1979575509161741422 444 2097291855515168042 445 2221870021122844382 446 2353702118262161156 447 2493202225823944895 448 2640807597889356852 449 2796979933437126989 450 2962206718455757437 451 3137002636002077155 452 3321911056297543199 453 3517505602342889268 454 3724391803980533990 455 3943208835880403026 456 4174631353244769886 457 4419371420761157715 458 4678180549491239618 459 4951851837353897638 460 5241222228801792728 461 5547174889563219768 462 5870641712987079019 463 6212605954164970995 464 6574105009332016688 465 6956233337132095971 466 7360145540230832538 467 7787059604394332682 468 8238260314526381158 469 8715102845441158752 470 9219016547900109177 471 9751508928500490451 472 10314169844999722688 473 10908675916639016684 474 11536795172137476712 475 12200391936069993955 476 12901431977419182958 477 13641987922367566977 478 14424244956265281814 479 15250506818412782670 480 16123202115780344706 481 17044890961108698412 482 18018271962743372013 483 19046189573717791020 484 20131641828708830608 485 21277788478737722006 486 22487959553571752329 487 23765664364359106367 488 25114600977851250957 489 26538666177746534053 490 28041965945975064346 491 29628826482827621993 492 31303805800307965226 493 33071705911366652547 494 34937585651060758921 495 36906774156486547721 496 38984885043305043390 497 41177831310361636140 498 43491841012141545013 499 45933473735704965473 500 48509637923931949183 501 51227609087407885280 502 54095048949046703079 503 57120025570052523247 504 60311034503810423957 505 63677021033189661520 506 67227403540600830996 507 70972098073851597729 508 74921544160173996151 509 79086731939755151302 510 83479230674519733446 511 88111218712547319484 512 92995514967637583055 513 98145612004300567996 514 103575710791877056292 515 109300757228861604589 516 115336480505836172091 517 121699433419832598357 518 128407034713810473176 519 135477613566859335413 520 142930456314724203236 521 150785855540172207976 522 159065161619454993047 523 167790836879475322563 524 176986512459401822121 525 186677048047727992512 526 196888594596926631932 527 207648660204473015155 528 218986179271855926973 529 230931585149599949199 530 243516886390570299604 531 256775746840448212539 532 270743569699603337807 533 285457585807848547347 534 300956946299747097498 535 317282819906397614533 536 334478495066464807293 537 352589487148840567243 538 371663650966619036651 539 391751298913401233705 540 412905324920585652894 541 435181334597608884880 542 458637781775043603961 543 483336111846005976370 544 509340912149529454613 545 536720069827583262317 546 565544937425948763247 547 595890506709790836232 548 627835590993791207707 549 661463016500054362138 550 696859823076698481727 551 734117474836190426223 552 773332081083169078899 553 814604628140399087452 554 858041222483597672911 555 903753345847455587532 556 951858122759148071972 557 1002478601219774342797 558 1055744047040633775038 559 1111790252617680623324 560 1170759860707230574191 561 1232802704054416016395 562 1298076161499689974661 563 1366745531488734030313 564 1438984423680001325348 565 1514975169655276481468 566 1594909253503757411638 567 1678987763371838835090 568 1767421864833381393782 569 1860433297266812080605 570 1958254894186942529159 571 2061131128820005153247 572 2169318685972542282962 573 2283087061593574826364 574 2402719191193938646941 575 2528512108642701694272 576 2660777636629348847983 577 2799843110442520475751 578 2946052136491392922055 579 3099765387362766533901 580 3261361434991062223632 581 3431237623889017399807 582 3609810986182430714670 583 3797519200565015152302 584 3994821597099248682927 585 4202200210162422694927 586 4420160881664138018759 587 4649234417033829631404 588 4889977796324434930574 589 5142975443147861080867 590 5408840554029473520167 591 5688216491133758870686 592 5981778241212572988839 593 6290233943985845965158 594 6614326493095566843996 595 6954835213123776937040 596 7312577616132255487790 597 7688411241520872319014 598 8083235583008965722188 599 8497994106870710400046 600 8933676365608048122920 601 9391320211556401725875 602 9872014115021349800323 603 10376899591838927835217 604 10907173745410765546373 605 11464091928540439467035 606 12048970530617183993984 607 12663189895946625280297 608 13308197379315165999580 609 13985510545104335029413 610 14696720516631667249853 611 15443495482598454892680 612 16227584367964753500404 613 17050820676747703801634 614 17915126514765927164600 615 18822516800498379291365 616 19775103672846359679957 617 20775101104701205695311 618 21824829731941525161466 619 22926721907564079222615 620 24083326991482533226466 621 25297316886573556553348 622 26571491832496491217035 623 27908786468821991201585 624 29312276180076709392069 625 30785183735283200023197 626 32330886235779503454117 627 33952922385037382037755 628 35655000095545852396545 629 37441004447723570155584 630 39315006017322902391029 631 41281269587648060315336 632 43344263264570169881097 633 45508668012145246382427 634 47779387628472443730408 635 50161559181218210860182 636 52660563924244461423346 637 55282038716534323969709 638 58031887966813172147569 639 60916296126988267571242 640 63941740759936768317708 641 67115006206871580366998 642 70443197882134401453799 643 73933757222943674874376 644 77594477324470112609495 645 81433519290275251146979 646 85459429331230176783735 647 89681156645685838524358 648 94108072116997025569437 649 98749987864155802959196 650 103617177684882610181924 651 108720398430185929593367 652 114070912353268432777952 653 119680510475340365101613 654 125561537015056040822069 655 131726914928004749324165 656 138190172607144723084173 657 144965471794831262933773 658 152067636761863967577983 659 159512184808803967872541 660 167315358149917502990224 661 175494157240009807287176 662 184066375609866136696717 663 193050636276026759721795 664 202466429796439115106641 665 212334154043665957172681 666 222675155773525324318027 667 233511774067324843198011 668 244867385732448628497515 669 256766452746521321408635 670 269234571837386840629311 671 282298526291817046110073 672 295986340093315705187302 673 310327334490306632629074 674 325352187103903398964407 675 341092993685665668994570 676 357583332644136023862149 677 374858332460485224954345 678 392954742122486623673597 679 411911004707946704373772 680 431767334258140892412901 681 452565796084132615267940 682 474350390658831806028839 683 497167141250455652417766 684 521064185463617650297150 685 546091870857614921383892 686 572302854822663463640948 687 599752208898777364779730 688 628497527733817424657962 689 658599042881854455327458 690 690119741655508051256055 691 723125491251291274731209 692 757685168380233010513073 693 793870794642252421781000 694 831757677896769458624958 695 871424559889161332131892 696 912953770407499253930676 697 956431388252145849217023 698 1001947409316484015522505 699 1049595922086319359905081 700 1099475290882109757239289 701 1151688347178685839831875 702 1206342589354719427458117 703 1263550391236067837397971 704 1323429219815763755022622 705 1386101862546783645517638 706 1451696664623490301251901 707 1520347776682642842831448 708 1592195413375830873377127 709 1667386123281973613018249 710 1746073070650776937902309 711 1828416329486775782236762 712 1914583190507225831466865 713 2004748481527969916574538 714 2099094901856531036932640 715 2197813371294861077350464 716 2301103394380907226343380 717 2409173440523854161083504 718 2522241340716366291184582 719 2640534701535587820753289 720 2764291337174997938962843 721 2893759720280622751635983 722 3029199452397472586547107 723 3170881754866699540473371 724 3319089981048532835222917 725 3474120150784167359398305 726 3636281508046724575270336 727 3805897102773302376437133 728 3983304397909659262996566 729 4168855902745064759394766 730 4362919833657184281045680 731 4565880803437274586375440 732 4778140540411354591770331 733 5000118638628200536691639 734 5232253340433724309652659 735 5475002352811635483942321 736 5728843698922611907767184 737 5994276606340112022155147 738 6271822433537222948704647 739 6562025636250850464379326 740 6865454775410107438609890 741 7182703568394142646453000 742 7514391985449876761614923 743 7861167393185474721998728 744 8223705747125704770223723 745 8602712835408212606590453 746 8998925575775617861826271 747 9413113368119312596669927 748 9846079504912780488551129 749 10298662641981943245206288 750 10771738332148589580725787 751 11266220624402009883568888 752 11783063731349718591955548 753 12323263767827307984280607 754 12887860563651099003607903 755 13477939553637276958551517 756 14094633748123397674973343 757 14739125787379853479074307 758 15412650083420438982487374 759 16116495052885424554133996 760 16852005444802293038354308 761 17620584767207075428538692 762 18423697816752085906304595 763 19262873315618165396654774 764 20139706660204525704458143 765 21055862786277216651118227 766 22013079155425426220077487 767 23013168867899550691041077 768 24058023907087545899024484 769 25149618521128855073094229 770 26290012747363453716970290 771 27481356085575750263407299 772 28725891326208389157870483 773 30025958540004074547447205 774 31383999235767415575050843 775 32802560693244306240821773 776 34284300478370451155845620 777 35831991148470288256295044 778 37448525155263649847523776 779 39136919953893087093431081 780 40900323326484792010701169 781 42742018929139530944532917 782 44665432071576019037103890 783 46674135739062644268380434 784 48771856866627730232505235 785 50962482875984269971901700 786 53250068485990055270348270 787 55638842807944569414643619 788 58133216737442363115988065 789 60737790655020403204254360 790 63457362448291456745789240 791 66296935868813499030013209 792 69261729237439024721855579 793 72357184512489268911597708 794 75588976735634901691185457 795 78963023871012373004062546 796 82485497053687922862759088 797 86162831264278911161239687 798 90001736447175149122405824 799 94009209090554392574679557 800 98192544287073596452117504 801 102559348294926959755202277 802 107117551619708196299283661 803 111875422638386283245353948 804 116841581787514232286684246 805 122025016338729410742028758 806 127435095785483430308781256 807 133081587865950925017411251 808 138974675248020954865642753 809 145124972903363958126964671 810 151543546198602694903614396 811 158241929732788688117662659 812 165232146951508959009947123 813 172526730569211262966893058 814 180138743832554278540341385 815 188081802658949934348368438 816 196370098685786010378965287 817 205018423267282728170387518 818 214042192457369054510565476 819 223457473018542985399725310 820 233281009498232144141069378 821 243530252415871292275778886 822 254223387605595175390356909 823 265379366761276557483264076 824 277017939232461328206344835 825 289159685121725356581383221 826 301826049735951256379373353 827 315039379446148370065847173 828 328822959012576354817562755 829 343201050434222104043483392 830 358198933383993457730485149 831 373842947293459505263638282 832 390160535153471703759983292 833 407180289099657185938477803 834 424931997854485887724843349 835 443446696100475957839267081 836 462756715862034302324848839 837 482895739976513683522037209 838 503898857738239856508149821 839 525802622802585843083087574 840 548645113440601060434307962 841 572465995238284358690261569 842 597306586338299514109311432 843 623209925325790919086921912 844 650220841863967441779254642 845 678386030189281196892447043 846 707754125580362470284553863 847 738375783919353793935535013 848 770303764468970258445160702 849 803593015993443134879309319 850 838300766356564793319722898 851 874486615735258340499706398 852 912212633592562444082036047 853 951543459559532033457613521 854 992546408381460268399074080 855 1035291579089873804303123347 856 1079851968568129646404350903 857 1126303589684959029755947199 858 1174725594177188062147224833 859 1225200400469889253920491288 860 1277813826629649628592974727 861 1332655228654212329960351589 862 1389817644309769668561447930 863 1449397942735346272351318784 864 1511496980042366866623156613 865 1576219761146299392071244469 866 1643675608076603662430804573 867 1713978335020696930427031642 868 1787246430367723323893797526 869 1863603246028133613493521910 870 1943177194315949891613197007 871 2026101952691605028967878173 872 2112516676674968091714090231 873 2202566221250039862107421403 874 2296401371095442347577810582 875 2394179079987623444904266502 876 2496062719737326229545120072 877 2602222339033665701494788604 878 2712834932584848091340050076 879 2828084720959434538304867004 880 2948163441547888252669253172 881 3073270651080167517433056514 882 3203614040152196361055977408 883 3339409760231314049305473234 884 3480882763629199884385385024 885 3628267156949381572914266537 886 3781806568536257326485709169 887 3941754530472619825465709619 888 4108374875694026890337951650 889 4281942150809979490108159330 890 4462742045244875600278971710 891 4651071837335002145922685027 892 4847240858042611372004671605 893 5051570972973228887571495033 894 5264397083409035375603297580 895 5486067647098211077954325084 896 5716945219568882014990837426 897 5957407016765449796782839977 898 6207845499836047085732294540 899 6468668982931260326517933435 900 6740302264907598763480132750 901 7023187285863017994484417902 902 7317783809467700219797869849 903 7624570132089738314798634177 904 7944043819754013934927155262 905 8276722474011820656682367438 906 8623144527840382443762375610 907 8983870072733709464563285822 908 9359481718191011242459749877 909 9750585484854441080112835673 910 10157811732596141338369327688 911 10581816124903623964632349489 912 11023280630964390798225431357 913 11482914566903541089732722531 914 11961455677683934209137295613 915 12459671261235383764192857294 916 12978359336439426696156606228 917 13518349856657493210987246118 918 14080505970554935985410836923 919 14665725332039365149169639101 920 15274941461201275429960806670 921 15909125158216002139631328970 922 16569285972240857294855169398 923 17256473727417792684710248134 924 17971780108172420714789271340 925 18716340306082576057090597540 926 19491334730676178469613666728 927 20297990786606808046650045879 928 21137584719748530091080833608 929 22011443534846931200078374590 930 22920946987463491650796955593 931 23867529653053127036541170601 932 24852683076122458284666877173 933 25877958002526908222817351418 934 26944966698080575618018298239 935 28055385356771796014980475652 936 29210956602001883562956866219 937 30413492084392557388887696595 938 31664875179841523240387005461 939 32967063791643419648299178529 940 34322093260637385426436403581 941 35732079387490701166657363894 942 37199221571382834883948807221 943 38725806069513656837653494613 944 40314209382026100671569578792 945 41966901767105061110364334120 946 43686450891193329026770400471 947 45475525619449856832328621995 948 47336899951768083507606247212 949 49273457109870486644060915753 950 51288193781202386432173984307 951 53384224525561448244101960929 952 55564786350621677629338861760 953 57833243462740220624665626864 954 60193092199674265792406558172 955 62647966152082155983557290258 956 65201641480939668401614541944 957 67858042438267808083692027965 958 70621247098844498316317218080 959 73495493310857889067371765190 960 76485184873755648074276707994 961 79594897951851364186158376223 962 82829387732567962156057814598 963 86193595338527804360883882876 964 89692655003041682424579632752 965 93331901518903388531570464433 966 97116877970764592497077704335 967 101053343761745770717663876758 968 105147282945334356650855305774 969 109404912874030790903535226041 970 113832693176627974963239618375 971 118437335076449726429888200754 972 123225811063330223765901532603 973 128205364932589356822043436120 974 133383522204749172647182492305 975 138768100940244780698513492629 976 144367222963909725127082207845 977 150189325514561839305947154288 978 156243173335581279300059784327 979 162537871222959046851242431728 980 169082877047901892977921327711 981 175888015271709687423364377318 982 182963490971293886865094407576 983 190319904394382697723720958831 984 197968266064159334395197518474 985 205920012453806923875256849791 986 214187022252186198021915785166 987 222781633242653116813952705365 988 231716659817831724257542327536 989 241005411153996321246030825155 990 250661710069584821669854930244 991 260699912593265932361873587635 992 271134928267914551204518369895 993 281982241217817057391016903798 994 293257932007428554483268290730 995 304978700321042749799884363635 996 317161888493809169810877161911 997 329825505925647562204020296990 998 342988254410762336725150225988 999 356669554416657132530451653059 1000 370889572347787326956496545678