0 1 1 0 2 0 3 0 4 1 5 0 6 0 7 0 8 1 9 1 10 0 11 1 12 1 13 1 14 1 15 1 16 5 17 1 18 2 19 2 20 6 21 11 22 3 23 3 24 7 25 16 26 23 27 8 28 9 29 18 30 38 31 44 32 24 33 21 34 44 35 79 36 86 37 59 38 52 39 96 40 157 41 163 42 141 43 118 44 199 45 295 46 318 47 304 48 259 49 387 50 549 51 613 52 632 53 534 54 736 55 1006 56 1179 57 1240 58 1070 59 1364 60 1842 61 2217 62 2366 63 2074 64 2508 65 3333 66 4104 67 4374 68 3935 69 4547 70 5997 71 7436 72 7942 73 7298 74 8189 75 10658 76 13255 77 14133 78 13312 79 14587 80 18762 81 23217 82 24830 83 23858 84 25765 85 32608 86 40119 87 43019 88 42152 89 44994 90 56082 91 68411 92 73749 93 73385 94 77805 95 95346 96 115403 97 125018 98 126146 99 133050 100 160523 101 192649 102 209925 103 214127 104 225244 105 267566 106 318748 107 349051 108 359428 109 377356 110 442118 111 522840 112 575304 113 596789 114 626195 115 724277 116 850994 117 939849 118 981208 119 1029321 120 1177356 121 1374652 122 1522946 123 1598092 124 1677282 125 1899384 126 2205043 127 2448108 128 2580399 129 2710001 130 3042813 131 3512867 132 3906053 133 4132227 134 4344165 135 4841324 136 5560313 137 6187253 138 6566866 139 6910910 140 7653388 141 8745659 142 9734386 143 10359991 144 10916045 145 12022925 146 13673341 147 15215077 148 16232758 149 17124306 150 18774248 151 21252652 152 23635106 153 25268977 154 26689825 155 29145775 156 32848723 157 36497333 158 39093563 159 41340052 160 44993815 161 50496350 162 56042657 163 60125349 164 63653841 165 69081018 166 77220589 167 85590173 168 91954455 169 97454857 170 105507075 171 117491424 172 130042980 173 139877302 174 148395315 175 160319267 176 177894510 177 196603145 178 211683068 179 224782077 180 242409441 181 268081651 182 295818810 183 318766977 184 338784315 185 364783949 186 402154573 187 443062891 188 477745879 189 508139457 190 546405681 191 600620890 192 660671716 193 712739261 194 758617129 195 814794535 196 893210500 197 980957677 198 1058644046 199 1127489270 200 1209758896 201 1322842685 202 1450521716 203 1565741395 204 1668490846 205 1788644434 206 1951284559 207 2136306856 208 2306250660 209 2458780258 210 2633796648 211 2867089171 212 3134187188 213 3383510938 214 3608802730 215 3863013448 216 4196824378 217 4580976357 218 4944939317 219 5276071175 220 5644287949 221 6120756568 222 6671333687 223 7200105019 224 7684544894 225 8216365128 226 8894873722 227 9681299527 228 10446056811 229 11151585342 230 11917529877 231 12881505793 232 14001201280 233 15102490140 234 16125601281 235 17225563427 236 18592037185 237 20181258930 238 21760712110 239 23238177243 240 24813339367 241 26746021716 242 28994950883 243 31251320686 244 33376421620 245 35625632688 246 38353143604 247 41526443253 248 44737885163 249 47782697796 250 50985366134 251 54826137627 252 59291370658 253 63845850773 254 68192251393 255 72739727349 256 78136476555 257 84402747667 258 90839998773 259 97022085857 260 103461188228 261 111027908736 262 119798955011 263 128867557157 264 137630232566 265 146722732393 266 157309343627 267 169555554617 268 182291195394 269 194670021355 270 207474580414 271 222254819234 272 239311645812 273 257143251786 274 274573996763 275 292557757474 276 313149426462 277 336850522765 278 361744949293 279 386212355724 280 411403718790 281 440031678239 282 472889930533 283 507547532347 284 541788185658 285 576984115580 286 616702150515 287 662153897837 288 710273796288 289 758050581884 290 807098858080 291 862089458738 292 924825049534 293 991462479774 294 1057936853004 295 1126117636406 296 1202098147458 297 1288506552762 298 1380555314249 299 1472789034414 300 1567331743827 301 1672101347869 302 1790869419585 303 1917709623183 304 2045341984552 305 2176121443135 306 2320298977515 307 2483215019913 308 2657583858435 309 2833741062163 310 3014216087345 311 3212230402888 312 3435262963846 313 3674419966633 314 3916937060020 315 4165409934041 316 4436830261136 317 4741570279614 318 5068857526724 319 5401913279631 320 5743220421111 321 6114536164244 322 6530125817886 323 6977049024929 324 7433353572706 325 7901126024107 326 8408128242366 327 8973831544032 328 9582836101292 329 10206547621503 330 10846233003968 331 11537189913056 332 12305818618654 333 13133980647480 334 13984592949629 335 14857481708821 336 15797371903747 337 16839837351745 338 17963769939653 339 19121278031480 340 20309865149014 341 21586003912154 342 22997362780332 343 24519719173564 344 26091479040306 345 27706583207851 346 29436096235906 347 31343559102265 348 33401647867974 349 35531461429233 350 37721670861165 351 40061395835883 352 42634929486112 353 45412099409464 354 48292237214291 355 51256410108021 356 54416004748221 357 57882335113892 358 61623009118839 359 65510082583496 360 69513875177162 361 73773129390914 362 78434221500733 363 83463705548307 364 88699602279291 365 94097271833557 366 99828951363002 367 106086345951311 368 112836906682376 369 119876344616975 370 127139481630572 371 134839406687485 372 143226240556423 373 152271367358661 374 161718123884858 375 171473436912296 376 181800046863449 377 193023101644803 378 205122478304796 379 217776932673632 380 230855883784639 381 244682178805186 382 259677044074500 383 275835470451780 384 292756925773993 385 310260809443220 386 328742466861791 387 348745779198415 388 370290290828967 389 392878524117949 390 416263697668882 391 440928240318041 392 467572184750990 393 496252821436220 394 526354676298149 395 557543985964345 396 590407377105899 397 625843107616735 398 663964442600301 399 704012923999848 400 745541208847852 401 789260056247067 402 836318709638929 403 886911260647545 404 940106838271643 405 995310623974808 406 1053380639838655 407 1115783068838034 408 1182826440578891 409 1253373003597065 410 1326637517431657 411 1403651888485558 412 1486281552636943 413 1574994495773241 414 1668406085659255 415 1765486421761664 416 1867471785034055 417 1976729300112658 418 2093946339451730 419 2217445311716171 420 2345883517839622 421 2480736210021062 422 2624999476786428 423 2779659264638591 424 2942692548738189 425 3112358501422595 426 3290410353600042 427 3480630878587766 428 3684408719669407 429 3899316284481750 430 4123108279888353 431 4357859403120606 432 4608334260432120 433 4876460285112532 434 5159339714658343 435 5454090695874343 436 5763157454870844 437 6092527302177893 438 6444843618642414 439 6816666867276888 440 7204315306250399 441 7610655043094959 442 8043192957909554 443 8505517856140491 444 8993572143429609 445 9502672895377313 446 10036164404622583 447 10603438179753011 448 11209324663724345 449 11849069264861054 450 12516740916031100 451 13216221415620894 452 13959235179848877 453 14752235054853858 454 15589691423229490 455 16464123108849070 456 17380010631806799 457 18351960656354884 458 19388536394745276 459 20483361115970698 460 21627035983040118 461 22824701321175735 462 24094518321349055 463 25447783661304391 464 26877215087785406 465 28371050319991674 466 29935148017840184 467 31592045080724576 468 33356565160844188 469 35220486275501393 470 37169144550436772 471 39209169196084856 472 41368474620461791 473 43666418811708080 474 46093845206417966 475 48632541207603396 476 51289948030912553 477 54100577644089728 478 57089598114793612 479 60246982975602075 480 63550196562832715 481 67007516428951283 482 70661536220316626 483 74544845246579318 484 78646699277611488 485 82939317043264521 486 87431812206579827 487 92176662641492834 488 97215909200421584 489 102538366143104043 490 108109913432440836 491 113940465983980456 492 120094572885984333 493 126626278707469420 494 133524406012252178 495 140747207164090006 496 148305317245342482 497 156278006319435226 498 164734524450711684 499 173664390042437102 500 183016717699941890 501 192802720288575228 502 203119596300136930 503 214055809144308888 504 225602583301597132 505 237698136806905719 506 250354039615236401 507 263689296500466675 508 277816591915695967 509 292730298660301504 510 308355704919576507 511 324704417429036864 512 341921931859940799 513 360151398222242473 514 379392354637460727 515 399554826782607487 516 420650014835350570 517 442855558807582269 518 466352848056066256 519 491149360084656695 520 517137207060450789 521 544326588018685496 522 572934105484536541 523 603189048305436041 524 635110599975881356 525 668569977259243163 526 703575602439082016 527 740391256593031128 528 779306113915174589 529 820356121927600347 530 863388291103331306 531 908408276167171651 532 955736932378784563 533 1005738166483211515 534 1058471422177835514 535 1113755882722206634 536 1171593195678266782 537 1232373201562224046 538 1296552905519203274 539 1364224136812603592 540 1435174369338373441 541 1509399719574360301 542 1587373345770658423 543 1669668036213910833 544 1756419666430385858 545 1847379942780408532 546 1942537612796053050 547 2042466391340903050 548 2147882833178563698 549 2258982063762163409 550 2375475929664562511 551 2497343632736019500 552 2625280176446118337 553 2760180355279860966 554 2902318265968464546 555 3051361981056543144 556 3207278633380292872 557 3370909442840563440 558 3543369862273180707 559 3725038418573929882 560 3915535988491976606 561 4114814777249742320 562 4323892196030983309 563 4544156487976396199 564 4776123339252330592 565 5019363943356727286 566 5273812434677834715 567 5540698459971098664 568 5821747054088571369 569 6117652972871527180 570 6427936793455628353 571 6752511249505567292 572 7092861577616169145 573 7451128091750403981 574 7828238099282244112 575 8223663024531519052 576 8637290862084908495 577 9070914597316313259 578 9527185982894255580 579 10007332901411847426 580 10510782628922865405 581 11037395352003196149 582 11589334585656751344 583 12169881216516585282 584 12780649967962687788 585 13421034034617259891 586 14090863426666777142 587 14792747788137200085 588 15530741069095895199 589 16306953925632325993 590 17120762622778795013 591 17971965950583682670 592 18863710776584328554 593 19800999971447693685 594 20786577732620265684 595 21819830280491598518 596 22900526369700458285 597 24032459926794922465 598 25221797444580218461 599 26472089818571154429 600 27782773309384896042 601 29153591307459779870 602 30589117339009370308 603 32096943441720806698 604 33681644613880707636 605 35342764927653651145 606 37080032319223538076 607 38898959982944208811 608 40808884812910719211 609 42815678286335744477 610 44919073549607836249 611 47118800612128632383 612 49421505835742897868 613 51838659980216381301 614 54377771580076526344 615 57038875054101950569 616 59821730859981162842 617 62734352660157735009 618 65790818716872350243 619 69000699673830285555 620 72364483898247142455 621 75882005827179250090 622 79562930025641853533 623 83424518591482201746 624 87478933827825927495 625 91727323350550485141 626 96169660008218389939 627 100817603148837235483 628 105692299639444571913 629 110809162066912960100 630 116170270672425655016 631 121775829610758334635 632 127639910455877021186 633 133788396882371683496 634 140240769635469521301 635 147000402581348065424 636 154067862483723969362 637 161460140438865567100 638 169208892189280852803 639 177338680727256165183 640 185854646876362779950 641 194757902672330258998 642 204068975935504028315 643 213826551817005485693 644 224061531152919984265 645 234781438480359227921 646 245988181982672447373 647 257706577949868124958 648 269983867436752409694 649 282858841613765167765 650 296342208003336514682 651 310437011782208915051 652 325173274364813581603 653 340608645311984469701 654 356791723253807985530 655 373737429446176744620 656 391450404934611457036 657 409966995189390853684 658 429357505968502586415 659 449682707824075428261 660 470963059243404975608 661 493205410009302011735 662 516453796951894263029 663 540793908266854234165 664 566301599207863785576 665 593004558172188708958 666 620912656579352999397 667 650079295084529807404 668 680608850188085445174 669 712595846044684452119 670 746077358082087067109 671 781067350924033469628 672 817630636771737641079 673 855894288226381021105 674 895975904040909906065 675 937924686634055208522 676 981760098659107926484 677 1027560873256597171347 678 1075481636964738120350 679 1125668473041853486155 680 1178186180732553365738 681 1233061553287309687798 682 1290390322544233642517 683 1350360556087674953953 684 1413153458235136329269 685 1478853806921089554814 686 1547498105834609398489 687 1619202863218621184323 688 1694196721139435036148 689 1772704138645614803957 690 1854835391735017859117 691 1940639772332865282956 692 2030259205196135748325 693 2123971549330063835276 694 2222054478159913915053 695 2324650701151780093013 696 2431826263928936656638 697 2543754210634101837698 698 2660772086823409726874 699 2783222965335359411324 700 2911290684305126427918 701 3045063134296601001285 702 3184751491764004746010 703 3330765670657221797725 704 3483529038722805551723 705 3643277441264462083458 706 3810127129310957531818 707 3984336039528601153992 708 4166401814691051623791 709 4356846311935996764963 710 4555970966859989834670 711 4763928703975892006363 712 4981034839184930791311 713 5207893347650359711917 714 5445146783337942731186 715 5693179100576683309402 716 5952190473931899951833 717 6222566672264682820164 718 6505040533556044725498 719 6800402394403293475061 720 7109139788404396124198 721 7431513560940696471021 722 7767996033719925344632 723 8119476192586803638214 724 8486925169763684610498 725 8870960235518314899694 726 9271919893563192957833 727 9690382848308440693288 728 10127427275625852897223 729 10584245313706186499001 730 11061616405890467881929 731 11559978165799843391074 732 12080040107204288698737 733 12623109609020244888044 734 13190648761044789696372 735 13783639341676019436431 736 14402645103141721689825 737 15048536458708964157146 738 15722898444133895960351 739 16427522642698048517477 740 17163642824320160013483 741 17931982863810503799102 742 18733611139990144504131 743 19570449019685992435898 744 20444689969157464204602 745 21357881061255260998129 746 22310948937149053500921 747 23305205596620299245327 748 24342979787385796590831 749 25426954817875553823410 750 26559066667118944254451 751 27740498150933468974056 752 28972861117786967025699 753 30258977730848376692573 754 31602127960189537947235 755 33004729800991408162522 756 34468289012637884732774 757 35994786527415278091580 758 37587642102561709255991 759 39250862025182573115075 760 40987460840288162053035 761 42799350577864996852998 762 44688966485834652629899 763 46660452062641075968043 764 48718697206111343258547 765 50867453736157097640778 766 53109143772711206463264 767 55446761774383759116172 768 57885327726606489209938 769 60430805868069099885180 770 63087858009493555531899 771 65859545506456077709721 772 68749551081966656347384 773 71763956156925337513199 774 74910030476462951306816 775 78193557596953950613700 776 81618398515664467121822 777 85189082939559735860305 778 88912977659327877485994 779 92798937972224948892092 780 96854128534371102662442 781 101083408926261314232391 782 105492350967711761433736 783 110089877947522145294827 784 114886769827696290142972 785 119891889705782723467274 786 125111342133715304312236 787 130551980833168305223682 788 136224613845853967971190 789 142142356261322600049472 790 148316157547093582575021 791 154753671963985574392844 792 161463329674416164371754 793 168458220870095361555387 794 175754292388996052839668 795 183365053852983164946848 796 191300085645649221854245 797 199569755987955777335201 798 208189918296262425578750 799 217179951780377732890631 800 226556504350576811939366 801 236331546877255018882958 802 246517829393704411466056 803 257134550871350086189441 804 268205249016786596276501 805 279750414896262266091237 806 291784982036013107279732 807 304324626546159047463194 808 317392597795339770936628 809 331017469505825916484174 810 345224434578080368575183 811 360032093368294815567151 812 375459715249285537847699 813 391535453036649131638979 814 408293976557809825116183 815 425766225769111754609317 816 443975333508318406300767 817 462944979830917345976831 818 482709253315517344284911 819 503310200080892448837694 820 524785778453189611014041 821 547164716741023928914605 822 570476106604326610195612 823 594761221496733833915680 824 620071029269743722892454 825 646452051779810336695344 826 673939916732036693842703 827 702570352305937420002222 828 732393328078796923763295 829 763470598656199542175627 830 795859126065179507919532 831 829603035230419424020860 832 864746189014445070544093 833 901349081263753941854885 834 939486503275910519149036 835 979228134883271757551770 836 1020628554237121570425779 837 1063741590167146100460798 838 1108640471954576609690085 839 1155415740998220936759099 840 1204152557369898623390999 841 1254918344608346914343330 842 1307779134650627451513655 843 1362823566215848465488633 844 1420161202109561270718608 845 1479896030853232611032484 846 1542111244186673580192008 847 1606887808451301727989273 848 1674333004970277477963511 849 1744579360622792811131482 850 1817753747976037024496483 851 1893958694880939589190643 852 1973293434670207429986294 853 2055887799808652963202699 854 2141902031589095658684863 855 2231490795988437231252561 856 2324780308479026018349832 857 2421892133156521295404559 858 2522983377694574381528725 859 2628247719520458120722929 860 2737873557273285553866798 861 2852016096657367207557499 862 2970824184886666153438883 863 3094487913425896474089925 864 3223241285499518483498664 865 3357313613344545615225619 866 3496895549042745291821278 867 3642169254467415444769599 868 3793364701654567359366032 869 3950764513166010818467182 870 4114647592038774688801743 871 4285247890898768525639460 872 4462788227678900258648183 873 4647546785382371981243594 874 4839864786451416817566838 875 5040081204061769484273255 876 5248482838659859125001168 877 5465342094489334636668712 878 5690995425144694792732711 879 5925854660146020911712810 880 6170331491616222317532630 881 6424777164137983897203988 882 6689524524602484701289818 883 6964980441991860743322019 884 7251641794113046448043973 885 7550008251259683656424678 886 7860509576562851483116595 887 8183552249367669527464534 888 8519628212461620411649807 889 8869336755571836275868313 890 9233283925892533424755525 891 9611995074496046720302658 892 10005966328301159532057556 893 10415792391471249918551577 894 10842195837153123012829359 895 11285911262256722705811090 896 11747580292498882173683162 897 12227808136260084339012922 898 12727313595905720572762883 899 13246967608904472669240035 900 13787660029576623681836684 901 14350173811134244637802560 902 14935246811731804967586942 903 15543747663621237364509218 904 16176725799324660382245736 905 16835258484874216608035212 906 17520300320534705674928959 907 18232750379483440019107668 908 18973658146589226932587670 909 19744287736500874107052772 910 20545942520049603642559273 911 21379785413218073306071077 912 22246911305322658672956040 913 23148587924395714392957846 914 24086337515716449982206746 915 25061736094599524024511164 916 26076199210779766976132954 917 27131059457413936663153136 918 28227847857335067035722445 919 29368396938796092282523814 920 30554611313298954849666551 921 31788212692847588924304388 922 33070822053588644410180482 923 34404287978589150829561785 924 35790815861241256658752099 925 37232706145993802405453177 926 38732051319444023667625255 927 40290822020968227539576431 928 41911249736588209670526778 929 43595987801505621846223882 930 45347813255197879764534127 931 47169267301775519688120090 932 49062744300169280370760634 933 51030937294969936233008762 934 53077037603509227042127103 935 55204395826163997023321079 936 57416095851430064215272438 937 59715045202894150965605068 938 62104493133243893815404045 939 64588276897857771493853994 940 67170437028889969666841396 941 69854713317087315502206190 942 72644634421414670261668875 943 75544119660007212585659261 944 78557781625933349609555708 945 81690490383572249020980023 946 84946777959384579092296977 947 88330924408217678129661071 948 91847656030079967126693786 949 95502515814593630554257913 950 99301370756039424735521812 951 103249709191511191836402738 952 107352719636667211615614099 953 111616099962048490804468604 954 116046509307213052829323753 955 120651012244395436138171987 956 125436250772169548131823888 957 130408511148322448173753889 958 135574660598496862561335910 959 140942696872774283599247774 960 146521122527790461512299996 961 152317970468793582557641810 962 158340852677829054492752128 963 164598043327404519774195957 964 171099145123584804955612705 965 177854386536429698580138192 966 184873476428467299082037278 967 192165626954452919717746403 968 199740804542705614348744598 969 207610535651328707642824134 970 215787119375023430912664111 971 224282282841463634167218137 972 233107168588075864982389292 973 242273777785179158438083819 974 251795942108709114087449239 975 261688443810651975364907725 976 271965439136689500989682026 977 282640398099146417538359296 978 293727767583280416078011186 979 305244140806331983098313518 980 317207276688060250527988683 981 329634253464258890519125295 982 342541345895205552000016008 983 355945939555965783299111920 984 369867934917873923572628892 985 384328657731070027815967534 986 399348699190202073002567093 987 414947712152670599832990683 988 431146612004916997704686556 989 447969258895097673573562013 990 465441250886235487889805398 991 483587400372431488127638889 992 502431426723758356502840633 993 521998483684686376391244538 994 542317170851437710226879471 995 563418201627789676141867875 996 585331457980141677154664152 997 608085551950505088898328643 998 631710724624441779980903853 999 656241246750425925784017530 1000 681713954098733208823277233