0 1 1 0 2 0 3 0 4 0 5 1 6 1 7 2 8 3 9 5 10 7 11 10 12 13 13 18 14 23 15 31 16 39 17 51 18 64 19 81 20 102 21 128 22 159 23 198 24 245 25 304 26 374 27 460 28 563 29 689 30 841 31 1023 32 1242 33 1505 34 1819 35 2195 36 2642 37 3173 38 3804 39 4551 40 5435 41 6477 42 7707 43 9151 44 10850 45 12843 46 15175 47 17902 48 21089 49 24802 50 29132 51 34164 52 40012 53 46796 54 54663 55 63766 56 74296 57 86458 58 100493 59 116670 60 135306 61 156736 62 181375 63 209663 64 242116 65 279314 66 321915 67 370650 68 426373 69 490020 70 562666 71 645509 72 739920 73 847411 74 969726 75 1108792 76 1266786 77 1446162 78 1649677 79 1880399 80 2141817 81 2437793 82 2772683 83 3151361 84 3579287 85 4062545 86 4607973 87 5223188 88 5916698 89 6698022 90 7577774 91 8567757 92 9681196 93 10932776 94 12338861 95 13917698 96 15689558 97 17676989 98 19905098 99 22401751 100 25197899 101 28327942 102 31830042 103 35746515 104 40124346 105 45015586 106 50477879 107 56575166 108 63378175 109 70965196 110 79422906 111 88847116 112 99343746 113 111029940 114 124035042 115 138501917 116 154588321 117 172468357 118 192334037 119 214397263 120 238891551 121 266074278 122 296229097 123 329668386 124 366736032 125 407810728 126 453309011 127 503689159 128 559455171 129 621161106 130 689415801 131 764888359 132 848313562 133 940498270 134 1042328265 135 1154775597 136 1278906558 137 1415890938 138 1567011152 139 1733673041 140 1917417312 141 2119931882 142 2343065411 143 2588842447 144 2859479028 145 3157400526 146 3485260681 147 3845962312 148 4242679688 149 4678883604 150 5158367443 151 5685276505 152 6264139642 153 6899903284 154 7597968560 155 8364232279 156 9205130052 157 10127684449 158 11139556684 159 12249102577 160 13465433320 161 14798482126 162 16259075158 163 17859009582 164 19611137942 165 21529459161 166 23629217321 167 25927009679 168 28440901783 169 31190553800 170 34197356886 171 37484580209 172 41077530636 173 45003726193 174 49293082062 175 53978113379 176 59094154236 177 64679593941 178 70776132783 179 77429059612 180 84687549767 181 92604988765 182 101239322093 183 110653431734 184 120915543929 185 132099670342 186 144286082152 187 157561824047 188 172021268725 189 187766714131 190 204909029024 191 223568350262 192 243874832857 193 265969460724 194 290004921410 195 316146547291 196 344573331766 197 375479025687 198 409073316117 199 445583098998 200 485253850705 201 528351103046 202 575162034400 203 625997183584 204 681192292860 205 741110294399 206 806143449332 207 876715647296 208 953284883443 209 1036345924595 210 1126433174591 211 1224123758954 212 1330040844127 213 1444857202776 214 1569299051167 215 1704150175081 216 1850256361763 217 2008530166517 218 2179956036387 219 2365595811420 220 2566594639275 221 2784187329132 222 3019705173448 223 3274583276661 224 3550368427436 225 3848727545255 226 4171456753290 227 4520491117868 228 4897915097338 229 5305973758727 230 5747084815804 231 6223851537550 232 6739076602242 233 7295776956781 234 7897199749287 235 8546839417585 236 9248456014888 237 10006094849017 238 10824107541536 239 11707174599692 240 12660329602045 241 13688985118782 242 14798960488485 243 15996511566006 244 17288362597460 245 18681740360065 246 20184410718880 247 21804717777610 248 23551625801547 249 25434764089295 250 27464475016154 251 29651865456248 252 32008861810433 253 34548268896013 254 37283832963967 255 40230309106331 256 43403533376785 257 46820499933316 258 50499443536210 259 54459927777949 260 58722939432516 261 63310989316742 262 68248220131305 263 73560521735615 264 79275654350598 265 85423380234850 266 92035604402353 267 99146524964071 268 106792793765954 269 115013687995787 270 123851293479667 271 133350700462073 272 143560212699295 273 154531570720214 274 166320190229281 275 178985416633418 276 192590796746183 277 207204368821625 278 222898972120964 279 239752577266908 280 257848638787688 281 277276471284114 282 298131650752514 283 320516442727144 284 344540258990762 285 370320144678313 286 397981297793873 287 427657623224030 288 459492323465273 289 493638528470916 290 530259967141009 291 569531683104908 292 611640797701405 293 656787323166806 294 705185029239354 295 757062366638019 296 812663451054063 297 872249111486353 298 936098007083288 299 1004507816837728 300 1077796506750034 301 1156303679425428 302 1240392011335612 303 1330448783256689 304 1426887509848766 305 1530149674618599 306 1640706576892385 307 1759061297911040 308 1885750793537789 309 2021348121494505 310 2166464811643071 311 2321753388254684 312 2487910053754322 313 2665677544092624 314 2855848166455655 315 3059267030631064 316 3276835486170481 317 3509514778122317 318 3758329934869869 319 4024373902543921 320 4308811941269039 321 4612886299386946 322 4937921182921074 323 5285328038467634 324 5656611168785067 325 6053373701635123 326 6477323933568779 327 6930282071613536 328 7414187397347205 329 7931105879191467 330 8483238260274427 331 9072928650996622 332 9702673657059212 333 10375132075499059 334 11093135193393299 335 11859697725814131 336 12678029431756179 337 13551547449232521 338 14483889393031284 339 15478927261165201 340 16540782198950384 341 17673840172392251 342 18882768605562085 343 20172534040064585 344 21548420877959587 345 23016051273058665 346 24581406239537447 347 26250848050684183 348 28031144004804505 349 29929491640050938 350 31953545484522490 351 34111445432978927 352 36411846847067618 353 38863952481413157 354 41477546343808461 355 44263029604295557 356 47231458674360226 357 50394585584449976 358 53764900795685324 359 57355678589300005 360 61181025185536164 361 65255929752785317 362 69596318476769124 363 74219111869273274 364 79142285506549392 365 84384934398185539 366 89967341198655378 367 95911048486269558 368 102238935346796688 369 108975298512548857 370 116145938322333821 371 123778249782567936 372 131901319025680989 373 140546025479185525 374 149745150076252070 375 159533489857356016 376 169947979332715424 377 181027818995909349 378 192814611400986289 379 205352505239142357 380 218688347875250103 381 232871846830426020 382 247955740724575030 383 263995980221447440 384 281051919549064435 385 299186519201031047 386 318466560457751020 387 338962872402300126 388 360750572143857084 389 383909319001106102 390 408523583439807400 391 434682931603607508 392 462482326323380581 393 492022445539581622 394 523410019124496394 395 556758185145671798 396 592186866669326325 397 629823170264076711 398 669801807428926679 399 712265540237078518 400 757365652558939727 401 805262448302481756 402 856125778188090645 403 910135596659286017 404 967482550618091281 405 1028368601766516522 406 1093007684433932282 407 1161626400872672773 408 1234464756112431572 409 1311776934579207941 410 1393832120804324056 411 1480915366675893070 412 1573328507819473359 413 1671391131834986634 414 1775441601265046697 415 1885838134327040317 416 2002959946605130792 417 2127208457071643648 418 2259008561990575503 419 2398809980447700149 420 2547088675453848546 421 2704348354782184616 422 2871122055923925439 423 3047973819783208893 424 3235500457981498417 425 3434333418903256968 426 3645140757890044500 427 3868629217281692443 428 4105546422307842172 429 4356683199154735913 430 4622876021871634942 431 4905009595136889327 432 5204019580278302495 433 5520895472338384069 434 5856683636389372550 435 6212490511739810484 436 6589485993135373530 437 6988906998539725934 438 7412061233589783734 439 7860331163356825634 440 8335178202607159883 441 8838147136348669598 442 9370870783074282797 443 9935074913768373696 444 10532583440431513492 445 11165323888606166491 446 11835333169147779876 447 12544763665288136015 448 13295889651883181935 449 14091114064624130483 450 14932975637923393645 451 15824156431170061924 452 16767489764080089958 453 17765968582951019587 454 18822754280773227288 455 19941185995347634286 456 21124790410819845564 457 22377292089367790819 458 23702624361171283664 459 25104940802255836580 460 26588627331343666985 461 28158314958460958305 462 29818893219749711191 463 31575524334721099056 464 33433658124062890708 465 35399047728085960598 466 37477766167969829555 467 39676223794143879528 468 42001186668428803449 469 44459795928969792207 470 47059588189517247703 471 49808517027264407197 472 52714975616241469365 473 55787820566192837164 474 59036397029939843897 475 62470565145465337530 476 66100727882348497581 477 69937860365742616246 478 73993540754834900803 479 78279982756657352331 480 82810069860246075257 481 87597391380485282312 482 92656280405523103923 483 98001853746426680458 484 103650053992766701252 485 109617693783089954508 486 115922502404771226637 487 122583174843548511776 488 129619423409141749221 489 137052032069757078091 490 144902913635002358549 491 153195169933791875320 492 161953155141222057174 493 171202542416175509479 494 180970394019565080947 495 191285235091689956706 496 202177131276163790540 497 213677770387300760494 498 225820548327738702964 499 238640659473464792070 500 252175191754300455705 501 266463226669332343134 502 281545944488773625884 503 297466734906320124507 504 314271313419266437208 505 332007843727501139905 506 350727066457025890003 507 370482434528883478566 508 391330255510371737106 509 413329841302186562740 510 436543665532725864879 511 461037529049239711682 512 486880733914857584021 513 514146266340815352796 514 542910989004491215847 515 573255843226173675881 516 605266061500886997470 517 639031390906145680767 518 674646327932238290530 519 712210365308621327516 520 751828251428299077572 521 793610263001721387379 522 837672491602826288849 523 884137144802460130218 524 933132862618579249521 525 984795050048461753420 526 1039266226485718754467 527 1096696392864254761618 528 1157243417412587123450 529 1221073440945188214254 530 1288361302662836741155 531 1359290987481468733941 532 1434056095958812570420 533 1512860337940262565454 534 1595918051100121397485 535 1683454745611644559383 536 1775707676239353399995 537 1872926443209991548996 538 1975373623284423532923 539 2083325432521832400193 540 2197072422299930936750 541 2316920210230717521513 542 2443190247690722246516 543 2576220625767887531603 544 2716366921514394044429 545 2864003086486036183910 546 3019522379644385822890 547 3183338346798165219622 548 3355885848865167226021 549 3537622141345953263527 550 3729028007515665981830 551 3930608947960827624725 552 4142896429214232728358 553 4366449194373254298891 554 4601854638725316356933 555 4849730253549252189351 556 5110725141413078410859 557 5385521606447654427349 558 5674836823242121150974 559 5979424588181273110484 560 6300077157227446323140 561 6637627174340501056276 562 6992949694929448785364 563 7366964308938593863828 564 7760637368390192854228 565 8174984324435034741718 566 8611072179202453099954 567 9070022057992614327896 568 9553011907617010588461 569 10061279326968421855492 570 10596124536189792369624 571 11158913491113087510684 572 11751081149954836875933 573 12374134899585397749854 574 13029658149034674148312 575 13719314098258758263147 576 14444849690570491470360 577 15208099757533043725378 578 16010991365530044454467 579 16855548373659431482112 580 17743896213051904172417 581 18678266898189538312789 582 19661004281296735282505 583 20694569561395240340805 584 21781547060158472735907 585 22924650277268983761262 586 24126728238577649195862 587 25390772150985343611439 588 26719922378618617410618 589 28117475755551606198192 590 29586893251038350701099 591 31131808003964342977933 592 32756033744004932727941 593 34463573617792708639429 594 36258629439247769827592 595 38145611384115610281661 596 40129148149688857831731 597 42214097601663210891828 598 44405557931096532824503 599 46708879345505129918728 600 49129676319244891967982 601 51673840429489403054836 602 54347553805334551467781 603 57157303218832000803343 604 60109894848084629309033 605 63212469743928219618717 606 66472520033178045743510 607 69897905892939390917601 608 73496873332070320696303 609 77278072817546354765762 610 81250578785213259539588 611 85423910076229295767238 612 89808051342395460316063 613 94413475465555221696208 614 99251167038317705662165 615 104332646955524270846386 616 109669998168142100028210 617 115275892653634067752542 618 121163619659326318578964 619 127347115277878434752971 620 133840993416660633943427 621 140660578225663315493809 622 147821938051511855475661 623 155341920988239339304393 624 163238192098687829395969 625 171529272383770901356177 626 180234579580342817676573 627 189374470872089541180513 628 198970287601690769755753 629 209044402076507418109208 630 219620266564233094868012 631 230722464579319000402231 632 242376764565547406480117 633 254610176084898098422177 634 267451008627833816805951 635 280928933165334024032483 636 295075046568441039079367 637 309921939026758877174029 638 325503764603273458919218 639 341856315069054313935534 640 359017097167864021164026 641 377025413467454265684681 642 395922446961379147577132 643 415751349592520310004238 644 436557334877208043604830 645 458387774816852039461001 646 481292301292379726113628 647 505322912145534423578623 648 530534082160226064528538 649 556982879166670761362143 650 584729085501019394437495 651 613835325063577990003420 652 644367196229582992890484 653 676393410877832292022668 654 709985939814308806619241 655 745220164880289157778212 656 782175038047327756552090 657 820933247814970060240065 658 861581393241102236953528 659 904210165949513325713526 660 948914540474556841241588 661 995793973318779336021659 662 1044952611116062372308363 663 1096499508310231843204054 664 1150548854777255983396007 665 1207220213838113201415592 666 1266638771129197215140567 667 1328935594817775383259201 668 1394247907671563395623516 669 1462719371513964275373676 670 1534500384619982156445678 671 1609748392632303189889838 672 1688628213602580961878985 673 1771312377789617460362269 674 1857981482873940080685836 675 1948824565277289909720828 676 2044039488305808052308818 677 2143833347867288443584052 678 2248422896545813426497343 679 2358034986851460589011627 680 2472907034498626363763862 681 2593287502603917015463014 682 2719436407733576738440389 683 2851625848771123992597995 684 2990140559618322526943483 685 3135278486786897235982889 686 3287351392984594362948999 687 3446685487847361540361828 688 3613622087019669930898624 689 3788518300837405692406495 690 3971747753922412622667906 691 4163701337054767288099846 692 4364787992748311007654558 693 4575435536016953113420752 694 4796091511883904467582052 695 5027224091253410937628947 696 5269323006834850202533405 697 5522900530882353351233017 698 5788492496589541413790392 699 6066659365058658136548900 700 6357987339846471184861908 701 6663089531175947059228174 702 6982607171993029300859306 703 7317210888142019985046461 704 7667602025031242035275444 705 8034514033263012711693527 706 8418713915808661680455512 707 8821003739420562122855851 708 9242222213089100236482468 709 9683246336473384692950141 710 10144993121360498349855117 711 10628421389339434018431539 712 11134533649012757233257266 713 11664378056211733359074989 714 12219050460829385752933591 715 12799696544040967549546618 716 13407514049842893300515442 717 14043755115009560896247309 718 14709728701742982621573015 719 15406803137473031686728640 720 16136408766456704733929960 721 16900040718023421615139722 722 17699261796520363728305767 723 18535705498227538260643937 724 19411079160737008625984792 725 20327167250524926225104243 726 21285834794689026478763279 727 22289030963078519665766063 728 23338792807308237260914421 729 24437249163424928041907597 730 25586624725281193731408873 731 26789244295972187975345577 732 28047537225002371833050265 733 29364042039174840401410081 734 30741411275534545837455418 735 32182416525049701669493501 736 33689953696083344104425480 737 35267048507090053257814699 738 36916862218371831466390947 739 38642697613142752962635377 740 40448005238584920958025801 741 42336389918029204882394844 742 44311617545863920840369598 743 46377622177263830141736603 744 48538513425341363876559745 745 50798584178852667747222617 746 53162318654143765382885988 747 55634400795597760680529925 748 58219723039443476801094308 749 60923395456410234757191329 750 63750755289363621730521399 751 66707376902734142467277039 752 69799082161255682016555972 753 73031951256264875549196905 754 76412333998576967290381041 755 79946861597749778813446875 756 83642458948376280759060397 757 87506357444909306244578521 758 91546108347420546205552204 759 95769596721631570845497467 760 100185055977528728799927334 761 104801083031887947299089913 762 109626654121091316907483064 763 114671141291716582199328745 764 119944329597525030360359865 765 125456435032664599943588723 766 131218123232145220993381447 767 137240528971934419413918430 768 143535276502365126695416027 769 150114500749946566185439151 770 156990869424125258199319792 771 164177606067058907337511307 772 171688514086043606612575006 773 179538001809876908936994264 774 187741108612148472242696048 775 196313532146228877574130425 776 205271656738578653367936021 777 214632582988926429986388665 778 224414158627870527559264672 779 234635010684545297402906467 780 245314579019165469061976296 781 256473151277522006793580371 782 268131899326855089910452325 783 280312917234977481216065103 784 293039260857068561911907814 785 306334989097209664731433877 786 320225206914489163068234756 787 334736110146375368345214600 788 349895032225041114570272620 789 365730492865430609395510833 790 382272248807091528499710175 791 399551346695158436678189672 792 417600178189372645504792024 793 436452537393663978864290774 794 456143680702607240293649230 795 476710389165006309097301365 796 498191033468957813539428151 797 520625641657010553919197933 798 544055969684472840375192518 799 568525574938534490706061669 800 594079892840670488630630592 801 620766316659786598575549879 802 648634280668761222350989497 803 677735346782440416646830314 804 708123294820762531656886802 805 739854216546533965767334038 806 772986613633456977887076800 807 807581499726333626728624861 808 843702506761946344696479318 809 881415995725955406072040092 810 920791172028267009897307090 811 961900205686723666182530301 812 1004818356516662266811029179 813 1049624104531886295592001365 814 1096399285770919193105082689 815 1145229233771058517525671547 816 1196202926921748299564672695 817 1249413141938143451197246711 818 1304956613705469351476791778 819 1362934201754896445210009772 820 1423451063642169064712143189 821 1486616835511165521431987194 822 1552545820135939227353425808 823 1621357182746615244121196099 824 1693175154956810925987560539 825 1768129247123031613334704697 826 1846354469479781748219381725 827 1927991562407948158757135899 828 2013187236208376200176785513 829 2102094420767492345475509203 830 2194872525517350908431176581 831 2291687710108620936220868710 832 2392713166231805895264675832 833 2498129411039428479247861631 834 2608124592640041540111014811 835 2722894808153770621116331300 836 2842644434838681724390055262 837 2967586474817628715909817295 838 3097942913956398210481999752 839 3233945095465967089805659849 840 3375834108824551390117839674 841 3523861194638888794503353323 842 3678288166088895306725822400 843 3839387847625506137491839436 844 4007444531618189055750537325 845 4182754453676344539572449167 846 4365626287397621594148265401 847 4556381659326123228718871406 848 4755355684934595045988558048 849 4962897526477029616902960948 850 5179370973591725441692342022 851 5405155047569761280593311309 852 5640644630240135289939687662 853 5886251118460526470664228841 854 6142403105241818180715969303 855 6409547088575236722590356768 856 6688148209073261294231180166 857 6978691017579416127621367189 858 7281680273947725007438365882 859 7597641778240058547761736536 860 7927123235638904094317778038 861 8270695156424308002639873895 862 8628951792416954101928264108 863 9002512111344626966080753311 864 9392020810646743658775357043 865 9798149372291305387533955163 866 10221597160240606598826411603 867 10663092562266432322303476705 868 11123394177882367233827112116 869 11603292054230327640921663461 870 12103608971830609706649041331 871 12625201782179726771511507423 872 13168962799258192544391759927 873 13735821247091306187954211330 874 14326744765590025077248496720 875 14942740976986290752471622113 876 15584859115267827313311378143 877 16254191721111587873092324896 878 16951876404912817201442928751 879 17679097680608265855615259246 880 18437088873097576657554477795 881 19227134102176417435110723972 882 20050570346008709235244170077 883 20908789587283457262531765992 884 21803241045324399141617642125 885 22735433497548114542005849998 886 23706937693798571004641546819 887 24719388867223498948083289869 888 25774489345500687252809378804 889 26874011266370469687432323064 890 28019799401584539392805764085 891 29213774093540999091111171498 892 30457934309041452094534393227 893 31754360814778195349163294784 894 33105219479338431121187479551 895 34512764706698117939813964633 896 35979343006370892775381258351 897 37507396705577683524270069466 898 39099467809010472061915760958 899 40758202011979452138815530840 900 42486352872956852713670309809 901 44286786151763276562821072324 902 46162484319883858339685597021 903 48116551249652209828113081111 904 50152217089300339495323999572 905 52272843331142868020684562930 906 54481928080444284021262070472 907 56783111532809081303905396336 908 59180181668236791563433127921 909 61677080170297590301897361159 910 64277908579209740047528081239 911 66986934687938090844143613355 912 69808599190783647160047126348 913 72747522594298313675975515518 914 75808512400736848471421136916 915 78996570574650297991229280416 916 82316901303632299988398474329 917 85774919064652174340290422161 918 89376257007847253685973294868 919 93126775670102033953588646379 920 97032572031214068788745504831 921 101099988925936734257871758113 922 105335624825697717249340297566 923 109746344004320023516548484639 924 114339287102620175519343378682 925 119121882107326818681605774853 926 124101855760352947243228079799 927 129287245415067195696280449510 928 134686411356844946322320680300 929 140308049605839235425397618534 930 146161205220595489810113264539 931 152255286121843912828670962378 932 158600077456539821649041064632 933 165205756522986405048540888502 934 172082908278667251069414691171 935 179242541453238650934197259796 936 186696105289985223331533467920 937 194455506939927965533912681729 938 202533129533692610598865658813 939 210941850957199382284203170807 940 219695063358224165318044322034 941 228806693411907068853541875681 942 238291223374348724060604467091 943 248163712954538841539822805011 944 258439822036007030979150903268 945 269135834280774178205316739464 946 280268681649415363012248190470 947 291855969872324021879876154295 948 303916004908593509522846115129 949 316467820430308150436031549378 950 329531206371463118459748993093 951 343126738582212927343310818251 952 357275809630683915409813877862 953 372000660796178890837726003298 954 387324415299254172522642132267 955 403271112815862792953691628810 956 419865745324534880986597379108 957 437134294337409552594144220787 958 455103769567844430124697223263 959 473802249089311696548335353466 960 493258921042345972782275520754 961 513504126948441979766309691779 962 534569406692011706303264990901 963 556487545233804543595012215720 964 579292621121572567283225785913 965 603020056866229955346449933929 966 627706671254313645315666822613 967 653390733670205093029430690862 968 680112020504323853942427406739 969 707911873726356247838164705290 970 736833261705540298719054192749 971 766920842363095307310373002456 972 798221028745064796074559883878 973 830782057107139291235727332496 974 864654057606444746780781784241 975 899889127698827799132442534714 976 936541408343845054684333375199 977 974667163123475006892945228417 978 1014324860384522877001791582270 979 1055575258518785771234463056212 980 1098481494499293328829162629399 981 1143109175795342970398447666072 982 1189526475793614611664954090617 983 1237804232857383153536135292833 984 1288016053160754275860296484714 985 1340238417439936346805112842875 986 1394550791808835135683575624448 987 1451035742791725240601989295616 988 1509779056731419711420354689871 989 1570869863737234511130053394548 990 1634400766343134721700316189015 991 1700467973052762538549522578952 992 1769171436954591163314939815205 993 1840614999597232037031555457738 994 1914906540321954092023759393569 995 1992158131256761785384875298220 996 2072486198183932873157332548416 997 2156011687500746785353420504212 998 2242860239501250002315540687801 999 2333162368215316300617623091729 1000 2427053648049977785612976687912