0 1 1 1 2 0 3 2 4 2 5 3 6 2 7 4 8 7 9 8 10 8 11 10 12 17 13 17 14 20 15 26 16 39 17 39 18 46 19 56 20 77 21 85 22 96 23 116 24 154 25 172 26 190 27 234 28 289 29 328 30 364 31 440 32 532 33 610 34 670 35 808 36 957 37 1091 38 1204 39 1432 40 1675 41 1905 42 2110 43 2476 44 2867 45 3255 46 3608 47 4184 48 4837 49 5451 50 6050 51 6960 52 7980 53 8961 54 9972 55 11370 56 12980 57 14521 58 16150 59 18296 60 20807 61 23191 62 25774 63 29066 64 32897 65 36570 66 40620 67 45580 68 51366 69 56990 70 63196 71 70654 72 79351 73 87841 74 97232 75 108396 76 121240 77 133998 78 148102 79 164606 80 183523 81 202520 82 223388 83 247686 84 275295 85 303310 86 333982 87 369502 88 409480 89 450493 90 495248 91 546730 92 604268 93 663892 94 728620 95 802776 96 885229 97 971131 98 1064162 99 1170390 100 1287650 101 1410675 102 1543638 103 1694624 104 1860697 105 2035792 106 2224510 107 2437992 108 2672001 109 2919462 110 3185974 111 3486200 112 3814195 113 4162035 114 4536398 115 4956182 116 5413779 117 5900205 118 6423182 119 7007250 120 7643067 121 8319393 122 9046510 123 9855546 124 10734499 125 11670565 126 12676942 127 13792030 128 15002355 129 16292088 130 17678196 131 19208802 132 20868450 133 22637276 134 24538376 135 26630886 136 28897304 137 31313219 138 33909872 139 36758730 140 39841911 141 43128896 142 46660722 143 50525038 144 54703952 145 59158221 146 63943742 147 69166776 148 74809380 149 80823890 150 87284308 151 94318138 152 101911239 153 110004212 154 118693422 155 128134536 156 138317797 157 149169560 158 160816810 159 173448168 160 187059903 161 201563788 162 217124226 163 233969500 164 252106683 165 271431277 166 292151910 167 314548800 168 338643343 169 364310389 170 391817716 171 421508662 172 453420459 173 487411778 174 523820204 175 563065850 176 605211996 177 650098598 178 698147330 179 749879172 180 805387744 181 864495227 182 927729992 183 995737034 184 1068646616 185 1146271356 186 1229267524 187 1318432900 188 1413949731 189 1515626884 190 1624272690 191 1740881870 192 1865701378 193 1998541656 194 2140404004 195 2292527204 196 2455234099 197 2628361506 198 2813141410 199 3011111358 200 3222702702 201 3447794125 202 3687895668 203 3944927002 204 4219451366 205 4511415928 206 4822679604 207 5155630416 208 5510998155 209 5888843781 210 6291450744 211 6721780728 212 7180788087 213 7668696421 214 8188302398 215 8743288206 216 9334894079 217 9963560716 218 10632732970 219 11346974136 220 12107882842 221 12916218191 222 13776214840 223 14693508868 224 15670182417 225 16707408869 226 17810392172 227 18986102280 228 20237232358 229 21565500133 230 22977325634 231 24481299308 232 26080895500 233 27778562066 234 29582215532 235 31502416290 236 33543661527 237 35709340847 238 38009209422 239 40456252628 240 43056272642 241 45813852530 242 48741052164 243 51853802136 244 55159552416 245 58664453466 246 62383398452 247 66335885132 248 70531503121 249 74978375561 250 79694888502 251 84704913650 252 90020736845 253 95652975673 254 101624362468 255 107964069626 256 114687783467 257 121809309867 258 129356730392 259 137365638816 260 145856053618 261 154845788229 262 164369491330 263 174470603066 264 185174577936 265 196504236442 266 208502365212 267 221221915160 268 234695128059 269 248951172759 270 264042810240 271 280034510474 272 296967073345 273 314877576591 274 333831003664 275 353905878222 276 375153635810 277 397621218079 278 421388654300 279 446551496108 280 473174389667 281 501316638258 282 531076664420 283 562570660074 284 595879729415 285 631078548839 286 668287981994 287 707649352776 288 749264116905 289 793225993929 290 839683352578 291 888807977914 292 940726402991 293 995556099853 294 1053478924546 295 1114703564750 296 1179387584794 297 1247677811397 298 1319796853274 299 1395998270268 300 1476477738215 301 1561418352250 302 1651092414606 303 1745807831600 304 1845807033471 305 1951318010328 306 2062673413712 307 2180246953004 308 2304338496678 309 2435231341108 310 2573331333078 311 2719092033592 312 2872883561068 313 3035057187542 314 3206107712248 315 3386585312982 316 3576945854992 317 3777624350685 318 3989223305794 319 4212409709096 320 4447744280640 321 4695764663458 322 4957203694150 323 5232869832048 324 5523451462633 325 5829611910124 326 6152241862752 327 6492320647822 328 6850691970602 329 7228173084857 330 7625845399406 331 8044894498840 332 8486353121957 333 8951226479583 334 9440826184882 335 9956587001702 336 10499771128328 337 11071612857021 338 11673701921426 339 12307773485250 340 12975367908581 341 13677998845354 342 14417591265586 343 15196242202942 344 16015829418478 345 16878206156525 346 17785701239596 347 18740847826830 348 19745931902479 349 20803219076544 350 21915524832190 351 23085906952450 352 24317144937346 353 25612004948662 354 26973887940274 355 28406482355454 356 29913164268656 357 31497306133050 358 33163012713114 359 34914730609826 360 36756555810367 361 38692594074969 362 40727796428828 363 42867519542396 364 45116727210217 365 47480412000915 366 49964540905638 367 52575562147878 368 55319485628956 369 58202374050022 370 61231413384992 371 64414361010864 372 67758485689245 373 71271140234144 374 74960972990972 375 78837309320226 376 82908931699369 377 87184747306612 378 91675156739496 379 96391362024314 380 101343965131134 381 106543743094894 382 112003194566136 383 117735767136564 384 123754246930872 385 130071657842814 386 136703010195380 387 143664435470510 388 150971339320799 389 158639444283856 390 166686764041528 391 175132635539756 392 183995605033613 393 193294631503463 394 203051317595650 395 213288827510816 396 224029468003102 397 235296076085138 398 247114541624334 399 259512593686152 400 272517038343542 401 286155356438901 402 300458554114342 403 315459801513764 404 331191285124357 405 347686040174766 406 364981174140402 407 383116340054038 408 402130151665628 409 422062281523961 410 442957110353846 411 464862008363542 412 487823260724570 413 511888467085338 414 537110670168404 415 563546420630826 416 591251155417833 417 620281931068984 418 650702099496656 419 682579127943926 420 715979359952962 421 750971125248247 422 787630039366572 423 826036539725502 424 866269958149373 425 908412054188144 426 952553019678480 427 998788692585616 428 1047213862855345 429 1097926274124115 430 1151033431630204 431 1206649451167256 432 1264887503844135 433 1325864342479819 434 1389708026597792 435 1456554348264076 436 1526538319016377 437 1599799285456990 438 1676489689207324 439 1756771013143598 440 1840804204800944 441 1928755440998734 442 2020806067671754 443 2117148002189136 444 2217972965105847 445 2323478972017272 446 2433881615753450 447 2549408841884674 448 2670288857916959 449 2796757438433965 450 2929070723325596 451 3067499283144622 452 3212314561101957 453 3363797076606507 454 3522250945068392 455 3687997141695514 456 3861358302843031 457 4042667933835888 458 4232286885061022 459 4430595696104906 460 4637977576905198 461 4854828741377678 462 5081577086067140 463 5318673498421386 464 5566572819772421 465 5825745423044428 466 6096698388097014 467 6379965644506592 468 6676086678776450 469 6985619507388609 470 7309164677161214 471 7647354082011134 472 8000827167638123 473 8370245469193375 474 8756319787965362 475 9159797520920500 476 9581436088577943 477 10022019210669619 478 10482387668193314 479 10963424970639034 480 11466027681201754 481 11991123643686971 482 12539706791810120 483 13112820937118996 484 13711526648491282 485 14336921676666226 486 14990180298288054 487 15672535010638526 488 16385239585790982 489 17129591942444832 490 17906978596767744 491 18718854029120254 492 19566699461591054 493 20452048489777774 494 21376537275111770 495 22341881301215654 496 23349829399130405 497 24402192491924721 498 25500900209589950 499 26647974752548498 500 27845479635333910 501 29095551916031871 502 30400466017275340 503 31762604394453326 504 33184400374817578 505 34668374322520821 506 36217205544095820 507 37833699395108472 508 39520723552651430 509 41281248634202873 510 43118429121465342 511 45035566546031686 512 47036038461581636 513 49123344059628754 514 51301195192982198 515 53573475251866172 516 55944159974703140 517 58417368722679696 518 60997466801329364 519 63689019566173438 520 66496704157777045 521 69425367182712552 522 72480139624390472 523 75666385721676932 524 78989604612441946 525 82455495224305523 526 86070085249324154 527 89839674311416674 528 93770724339178159 529 97869932619795415 530 102144376487934936 531 106601450201975528 532 111248742787728004 533 116094120345182950 534 121145888218278772 535 126412721016280298 536 131903526538591780 537 137627538496510720 538 143594498195863020 539 149814577098347454 540 156298225221021107 541 163056275656163491 542 170100148021682576 543 177441762850600132 544 185093372755084321 545 193067680302462535 546 201378065677353150 547 210038492199992340 548 219063318368281943 549 228467430777084023 550 238266498775784244 551 248476870377967428 552 259115363021419137 553 270199413500733844 554 281747362734558230 555 293778341188999378 556 306312036053056563 557 319368860417654257 558 332970271518704280 559 347138644826176778 560 361897015111897267 561 377269267279078845 562 393280491935195262 563 409956847243646740 564 427325271007281021 565 445413695958941446 566 464251446952616756 567 483869089517439152 568 504298109905583698 569 525571157993713293 570 547722490776618390 571 570787806590769202 572 594803889789469691 573 619808884683163083 574 645842790658903800 575 672947280993392288 576 701165308384624137 577 730541413881980602 578 761122279596102626 579 792956530816404768 580 826094298403972860 581 860587567160068833 582 896490792629774048 583 933860685299465102 584 972755725509753054 585 1013236556084048106 586 1055366670646063052 587 1099212178604531578 588 1144841267706158981 589 1192324646484282213 590 1241736312371812638 591 1293153295958924972 592 1346655066043037060 593 1402324028113266672 594 1460246381359888310 595 1520511840760587924 596 1583212979058118332 597 1648445788070161365 598 1716310634921163456 599 1786911960466819272 600 1860357551990914466 601 1936759175095556629 602 2016233640733785882 603 2098902478210491930 604 2184891132072686408 605 2274329673284646832 606 2367353989771476178 607 2464105432371700552 608 2564729928908160633 609 2669378784133137076 610 2778210008237640264 611 2891387934083436224 612 3009082240672614021 613 3131468852712885426 614 3258731423245819716 615 3391060920222463830 616 3528654551251407664 617 3671716774904522588 618 3820460955300748180 619 3975108916279393330 620 4135889758741542955 621 4303040996995296438 622 4476810405479953982 623 4657455538828664624 624 4845242432242773066 625 5040446877995689608 626 5243356486923658786 627 5454270172388518544 628 5673496723764992541 629 5901356240053840347 630 6138182431097261236 631 6384322063813759738 632 6640133398280392604 633 6905987797048392213 634 7182272294355685106 635 7469389003128231298 636 7767753402145338330 637 8077796142228546982 638 8399965915057127386 639 8734728819257073550 640 9082566486829595914 641 9443978109890107858 642 9819483644083692724 643 10209623132647371218 644 10614954659661132814 645 11036056623467485463 646 11473531314173415984 647 11928004194954237188 648 12400121668649646416 649 12890553627497926541 650 13399997448949512100 651 13929177233450166368 652 14478841370687121284 653 15049765398900146573 654 15642756467925052692 655 16258652533702674902 656 16898319709957434249 657 17562655473813813863 658 18252593651290467096 659 18969103569510016218 660 19713187178551719739 661 20485882645096241233 662 21288269922072784164 663 22121469859937668764 664 22986641083489339857 665 23884984020317707734 666 24817747123037933380 667 25786225942612298776 668 26791759744591393915 669 27835736024278176585 670 28919597458558881224 671 30044840945700769356 672 31213013944632084769 673 32425719535646407312 674 33684624187979778054 675 34991456771526352940 676 36348004603251360262 677 37756119119573647906 678 39217724555169543290 679 40734816934760071962 680 42309459810917748570 681 43943790621594933006 682 45640030387615932240 683 47400482695197061360 684 49227529108946131492 685 51123636297896343105 686 53091366871701183420 687 55133378366775789372 688 57252418319626226757 689 59451332255043768706 690 61733075794284985008 691 64100713662011863398 692 66557414406071346788 693 69106459352293551908 694 71751256134319204044 695 74495337742885992490 696 77342356878611584723 697 80296095991680775390 698 83360482400629431082 699 86539587409555817548 700 89837620283151135437 701 93258939504440534568 702 96808069668255043156 703 100489700698891016602 704 104308681439141826896 705 108270032274715152890 706 112378964010993978306 707 116640877230741543364 708 121061355490848766106 709 125646179481852956718 710 130401348120944701512 711 135333078096462711250 712 140447796671089185508 713 145752157565981941729 714 151253064529060988160 715 156957671123809579912 716 162873373142610718152 717 169007826427553989414 718 175368973204510576018 719 181965042185256294690 720 188804540599352333678 721 195896274191580567410 722 203249376646515539176 723 210873310084739171922 724 218777856730304751176 725 226973141355124938805 726 235469664155100182258 727 244278301738032910712 728 253410298452813604435 729 262877291583362316448 730 272691348081385876512 731 282864966161556702652 732 293411066327669961950 733 304343019658606073199 734 315674688850234836070 735 327420430552555868434 736 339595086142600958802 737 352214013487979811715 738 365293132801863571660 739 378848929882400183976 740 392898446697673822526 741 407459317059135096991 742 422549817854534047074 743 438188873377963810642 744 454396045808562654647 745 471191575282430638149 746 488596437135097168468 747 506632347540484047110 748 525321753988587205807 749 544687880306271624786 750 564754790612816506332 751 585547396525163079990 752 607091447765624955127 753 629413582748732318853 754 652541400038802561166 755 676503467421525138248 756 701329312800413247999 757 727049481047113313546 758 753695613843011205118 759 781300460963769666976 760 809897871660902257882 761 839522858560644379972 762 870211686873355295702 763 902001888296167390332 764 934932253117549333890 765 969042902045898102336 766 1004375385889433524472 767 1040972702546968548474 768 1078879290118774571590 769 1118141107659453064195 770 1158805746562078573174 771 1200922451177899561726 772 1244542113275769232073 773 1289717362839110427559 774 1336502692530921334168 775 1384954482570901349492 776 1435130996951422097945 777 1487092485535259646121 778 1540901323145186025800 779 1596622039423960023956 780 1654321317287237050066 781 1714068107739996486744 782 1775933785317963494910 783 1839992183763083847750 784 1906319597285157609247 785 1974994909692472666489 786 2046099768114343987194 787 2119718625454398751282 788 2195938745134794819425 789 2274850346332402318416 790 2356546798145453730076 791 2441124669931603782720 792 2528683740322177168898 793 2619327160583176419610 794 2713161671647726031024 795 2810297663605766083706 796 2910849189915457317796 797 3014934151161109462367 798 3122674537657411875836 799 3234196499549281767074 800 3349630367304458502415 801 3469110858418833016832 802 3592777348627244219804 803 3720773954285485739956 804 3853249560403088516267 805 3990358053169995465504 806 4132258623171882214044 807 4279115861963995575326 808 4431099799115002115381 809 4588386163787000823020 810 4751156723755234368564 811 4919599398364260892906 812 5093908306291742969861 813 5274284059810621854036 814 5460934143874057578036 815 5654073047958820252714 816 5853922326524591487018 817 6060710930044174322485 818 6274675628926563815288 819 6496061167102321815942 820 6725120337471980162010 821 6962114354298653720079 822 7207313327308059342334 823 7460996440281525567984 824 7723452044145229851972 825 7994978075882598977073 826 8275882588798906740614 827 8566483959847024453844 828 8867111003410852808615 829 9178103442542371459195 830 9499812502098093034944 831 9832601149036232899656 832 10176844230421920452199 833 10532929003513253722864 834 10901255799275937206518 835 11282238300487993451350 836 11676303708028170887424 837 12083893337135419466043 838 12505463359718753399646 839 12941485125775671023138 840 13392445362625177076891 841 13858846845579569182816 842 14341209228480465887000 843 14840069414685836990408 844 15355981794610588196739 845 15889519000069228340285 846 16441272833593784089698 847 17011854696111537373208 848 17601895868946769396202 849 18212048362225952394194 850 18842985954814442215724 851 19495404686778785945516 852 20170023192891664461987 853 20867583656784841847609 854 21588852974766247132212 855 22334623322249392942318 856 23105712546835749240004 857 23902965241341746300324 858 24727254046343479489456 859 25579480301008584745420 860 26460574504992713278471 861 27371497525072936229582 862 28313242053065455131196 863 29286833352901682159334 864 30293329801882877892178 865 31333824247477840927187 866 32409445639263699744228 867 33521359885662732782958 868 34670770486608425685001 869 35858920059103562001490 870 37087092164063726243334 871 38356612287938003043088 872 39668848580539738409269 873 41025213570231716047722 874 42427166209078625606016 875 43876212996601303163866 876 45373908838436622579306 877 46921858974594465330547 878 48521721269140007347358 879 50175207495603511136248 880 51884084334330169186063 881 53650175540130109540413 882 55475364505848087203660 883 57361595731546119640246 884 59310875980876110260047 885 61325276717654651266094 886 63406936976221071703682 887 65558065039423955561772 888 67780939777129131077753 889 70077913384884602490726 890 72451414597921563962880 891 74903950606241371886582 892 77438108601551762367743 893 80056558855247509158531 894 82762058317312653089362 895 85557452800525352404644 896 88445678765694106472924 897 91429766780709379449213 898 94512845550576610811214 899 97698144406930663809702 900 100988995365465787558157 901 104388837012935216712218 902 107901219020087695983426 903 111529804977364938036462 904 115278374763005879418852 905 119150828910591251176059 906 123151193662838728698550 907 127283624199673884325886 908 131552407360646921727270 909 135961966552007837015143 910 140516867406278092849812 911 145221821454852826342156 912 150081689254163481445953 913 155101485898475911153867 914 160286387357928035102236 915 165641734654509830853658 916 171173037447993358808312 917 176885980228701355850554 918 182786429415364093571708 919 188880438100906173005072 920 195174250161570726481674 921 201674307212899148484722 922 208387256558511529060860 923 215319956580633037617490 924 222479481444154212179441 925 229873128909198612204790 926 237508429232809115147458 927 245393151288680685188408 928 253535307947329338574276 929 261943164849947987506760 930 270625250377117494981774 931 279590362592994497755362 932 288847575393353634119948 933 298406248358082147675021 934 308276037914669999948218 935 318466905214193404226946 936 328989123150884451396157 937 339853287424847181243944 938 351070329043301272049736 939 362651523249250562569444 940 374608497529686988439461 941 386953244036017033323239 942 399698133583007520410262 943 412855925766327707665744 944 426439778091596619669047 945 440463259917771129188452 946 454940368132801496551180 947 469885538613381777103308 948 485313656623990755166648 949 501240072468460684976532 950 517680619042614325766144 951 534651624808768808530306 952 552169925633054215239223 953 570252882352687406939214 954 588918400429587195857076 955 608184944633829089308836 956 628071552508989495660781 957 648597854087564336903094 958 669784093896161919590848 959 691651147566366682723504 960 714220537141924022269483 961 737514453202712374888794 962 761555779501802667680630 963 786368111749354028478974 964 811975775002587083154657 965 838403848489965800256447 966 865678193193524379280196 967 893825473081997556536798 968 922873174854951541254823 969 952849635793719902241068 970 983784074639507130637732 971 1015706615586196604168700 972 1048648310684096485408603 973 1082641171083310174389400 974 1117718201599520826237402 975 1153913427815249387895948 976 1191261921487048711194731 977 1229799835590690875442496 978 1269564443012713389988950 979 1310594167151983393022042 980 1352928610717170081462898 981 1396608595031926516817657 982 1441676203341971351939910 983 1488174815357039998795390 984 1536149139873620923704371 985 1585645258852983434243671 986 1636710675891238452947136 987 1689394355195707416944544 988 1743746758522043678111943 989 1799819894599005834666258 990 1857667373373246763307124 991 1917344449974709139440048 992 1978908066517873690711357 993 2042416907515310017774270 994 2107931460580893549533002 995 2175514066006598895894816 996 2245228964045467229510096 997 2317142357032256088250911 998 2391322477309019129304130 999 2467839643111447452851734 1000 2546766312027335887366583