0 1 1 0 2 1 3 1 4 2 5 2 6 3 7 3 8 5 9 5 10 7 11 8 12 11 13 12 14 16 15 18 16 23 17 26 18 33 19 37 20 46 21 52 22 63 23 72 24 87 25 98 26 117 27 133 28 157 29 178 30 209 31 236 32 276 33 312 34 361 35 408 36 471 37 530 38 609 39 686 40 784 41 881 42 1004 43 1126 44 1279 45 1433 46 1621 47 1814 48 2048 49 2286 50 2574 51 2871 52 3223 53 3590 54 4022 55 4472 56 5000 57 5553 58 6194 59 6871 60 7652 61 8474 62 9420 63 10422 64 11564 65 12778 66 14157 67 15623 68 17284 69 19053 70 21045 71 23174 72 25565 73 28117 74 30977 75 34037 76 37449 77 41106 78 45175 79 49534 80 54376 81 59567 82 65313 83 71483 84 78299 85 85612 86 93679 87 102342 88 111872 89 122111 90 133358 91 145437 92 158688 93 172923 94 188505 95 205253 96 223561 97 243227 98 264703 99 287776 100 312928 101 339953 102 369381 103 400988 104 435371 105 472297 106 512409 107 555491 108 602245 109 652435 110 706857 111 765273 112 828540 113 896441 114 969918 115 1048746 116 1133981 117 1225403 118 1324158 119 1430065 120 1544381 121 1666921 122 1799101 123 1940760 124 2093430 125 2257009 126 2433185 127 2621877 128 2824974 129 3042436 130 3276326 131 3526698 132 3795820 133 4083793 134 4393156 135 4724097 136 5079385 137 5459346 138 5867037 139 6302880 140 6770288 141 7269818 142 7805213 143 8377243 144 8990032 145 9644512 146 10345290 147 11093525 148 11894267 149 12748980 150 13663248 151 14638805 152 15681873 153 16794525 154 17983605 155 19251642 156 20606195 157 22050208 158 23592107 159 25235352 160 26989217 161 28857810 162 30851395 163 32974715 164 35239186 165 37650309 166 40220673 167 42956720 168 45872374 169 48975003 170 52280104 171 55796152 172 59540240 173 63522169 174 67760860 175 72267480 176 77063052 177 82160323 178 87582514 179 93344250 180 99471227 181 105980015 182 112899166 183 120247505 184 128056561 185 136347784 186 145156078 187 154505670 188 164435295 189 174972341 190 186159616 191 198028173 192 210625380 193 223986180 194 238163120 195 253195577 196 269141605 197 286045645 198 303971937 199 322970361 200 343112116 201 364453213 202 387072332 203 411032475 204 436420646 205 463307374 206 491789036 207 521944636 208 553880630 209 587685583 210 623477199 211 661354414 212 701447494 213 743866979 214 788756733 215 836240368 216 886476837 217 939603935 218 995797473 219 1055211091 220 1118038855 221 1184452143 222 1254665288 223 1328869001 224 1407300132 225 1490170896 226 1577742638 227 1670251601 228 1767986218 229 1871208912 230 1980238211 231 2095365633 232 2216942431 233 2345292491 234 2480803255 235 2623833973 236 2774812141 237 2934136175 238 3102277250 239 3279677276 240 3466855603 241 3664301649 242 3872588051 243 4092256795 244 4323938592 245 4568233639 246 4825836684 247 5097411580 248 5383723722 249 5685507211 250 6003604571 251 6338827587 252 6692103643 253 7064329444 254 7456525917 255 7869683410 256 8304924928 257 8763344121 258 9246176265 259 9754627988 260 10290058080 261 10853797513 262 11447339966 263 12072153428 264 12729879673 265 13422136470 266 14150728410 267 14917437957 268 15724247421 269 16573120404 270 17466234249 271 18405750591 272 19394060836 273 20433544049 274 21526825354 275 22676522718 276 23885517404 277 25156688406 278 26493197922 279 27898211277 280 29375197249 281 30927635306 282 32559330014 283 34274104031 284 36076129713 285 37969605724 286 39959105781 287 42049240685 288 44245023261 289 46551514253 290 48974207126 291 51518655195 292 54190876119 293 56996962467 294 59943505026 295 63037184912 296 66285219553 297 69694933675 298 73274228002 299 77031131245 300 80974290498 301 85112502330 302 89455229320 303 94012107098 304 98793486919 305 103809921251 306 109072731455 307 114593469585 308 120384515940 309 126458513818 310 132828997131 311 139509800633 312 146515716465 313 153861877565 314 161564448580 315 169639978673 316 178106126824 317 186980987067 318 196283847237 319 206034483788 320 216253959875 321 226963885825 322 238187256898 323 249947682416 324 262270262016 325 275180780693 326 288706630207 327 302875965450 328 317718671287 329 333265483787 330 349549001599 331 366602768652 332 384462337245 333 403164307543 334 422747442985 335 443251670176 336 464719245463 337 487193711848 338 510721124972 339 535348961557 340 561127405420 341 588108211654 342 616346051826 343 645897329901 344 676821595440 345 709180305729 346 743038308030 347 778462552132 348 815523640671 349 854294488098 350 894851949209 351 937275418042 352 981648535705 353 1028057734236 354 1076594023099 355 1127351473344 356 1180429093663 357 1235929248265 358 1293959624213 359 1354631588054 360 1418062243799 361 1484372723611 362 1553690348875 363 1626146847413 364 1701880619429 365 1781034887327 366 1863760066363 367 1950211841598 368 2040553656795 369 2134954710798 370 2233592567391 371 2336651077221 372 2444323108458 373 2556808388945 374 2674316373026 375 2797063995255 376 2925278676300 377 3059195995494 378 3199062836473 379 3345134972332 380 3497680367868 381 3656976668529 382 3823314663270 383 3996995684872 384 4178335234185 385 4367660285888 386 4565313093250 387 4771648389436 388 4987037377352 389 5211864835439 390 5446533294556 391 5691460041404 392 5947081503460 393 6213850140181 394 6492239041987 395 6782738718756 396 7085861915155 397 7402140289972 398 7732129471809 399 8076405618252 400 8435570718907 401 8810249045637 402 9201092706805 403 9608777981392 404 10034011150843 405 10477524706426 406 10940083467591 407 11422480674583 408 11925544398113 409 12450133510619 410 12997144417566 411 13567506895618 412 14162191155930 413 14782203563679 414 15428594040198 415 16102451656859 416 16804912409576 417 17537154675875 418 18300407374986 419 19095945303740 420 19925097690794 421 20789243405335 422 21689819943886 423 22628318500027 424 23606293399140 425 24625357048083 426 25687189829395 427 26793534924805 428 27946208711863 429 29147095450562 430 30398158201813 431 31701433398031 432 33059042297543 433 34473185434919 434 35946154660631 435 37480327460397 436 39078179602809 437 40742279352900 438 42475300746281 439 44280017693243 440 46159317935016 441 48116197029615 442 50153773018465 443 52275280322481 444 54484085141528 445 56783679260221 446 59177696244199 447 61669905147739 448 64264227540340 449 66964731150481 450 69775647751540 451 72701366742889 452 75746453967616 453 78915645226675 454 82213866069550 455 85646225281023 456 89218035679845 457 92934807584145 458 96802270702101 459 100826367574041 460 105013276604200 461 109369405527330 462 113901415625823 463 118616215230745 464 123520985219982 465 128623172557783 466 133930517133892 467 139451045397186 468 145193098589570 469 151165326491070 470 157376717159847 471 163836590797740 472 170554631067935 473 177540879148545 474 184805766694864 475 192360110105500 476 200215145256866 477 208382522000237 478 216874340755837 479 225703147320088 480 234881971400581 481 244424321769509 482 254344226888560 483 264656230436100 484 275375434126180 485 286517493706135 486 298098664069985 487 310135795774220 488 322646382617856 489 335648558718488 490 349161148685992 491 363203665373090 492 377796362764096 493 392960234465724 494 408717069512491 495 425089451655415 496 442100818235816 497 459775460410970 498 478138585245493 499 497216316958533 500 517035762467311 501 537625013735889 502 559013216954980 503 581230576158132 504 604308426217985 505 628279237841732 506 653176694659370 507 679035699703232 508 705892456808868 509 733784478780229 510 762750673323659 511 792831353040264 512 824068326214949 513 856504908775258 514 890186020202398 515 925158197698106 516 961469697483621 517 999170511356845 518 1038312473759026 519 1078949280900028 520 1121136603913059 521 1164932110841409 522 1210395586205100 523 1257588956077441 524 1306576414509080 525 1357424451924342 526 1410201988789416 527 1464980407680755 528 1521833694588189 529 1580838474944174 530 1642074163088980 531 1705623002549925 532 1771570224132565 533 1840004090877783 534 1911016065253049 535 1984700859146239 536 2061156610777643 537 2140484940097090 538 2222791135976531 539 2308184217524824 540 2396777132132458 541 2488686823152458 542 2584034439533011 543 2682945410321053 544 2785549666554083 545 2891981723210566 546 3002380914052525 547 3116891481575772 548 3235662825672827 549 3358849602154041 550 3486611986039897 551 3619115779403916 552 3756532690126958 553 3899040449747300 554 4046823108709251 555 4200071164926155 556 4358981876493317 557 4523759401873362 558 4694615131079181 559 4871767838321973 560 5055444032887476 561 5245878125120846 562 5443312798163400 563 5647999188369260 564 5860197279111759 565 6080176096666241 566 6308214127540336 567 6544599530896064 568 6789630580803471 569 7043615896525751 570 7306874911154230 571 7579738121018915 572 7862547582430767 573 8155657181537884 574 8459433160856648 575 8774254411166962 576 9100513029583363 577 9438614635034035 578 9788978959926345 579 10152040190821716 580 10528247595711075 581 10918065891808922 582 11321975910545848 583 11740474994360640 584 12174077701851119 585 12623316235536110 586 13088741189583487 587 13570922010855242 588 14070447791741528 589 14587927766776768 590 15123992153487695 591 15679292686978212 592 16254503511688263 593 16850321756735801 594 17467468481624309 595 18106689295115775 596 18768755358345311 597 19454464050143522 598 20164640031031571 599 20900135958343158 600 21661833614742009 601 22450644676508293 602 23267511910699029 603 24113410000135724 604 24989346813363877 605 25896364290374041 606 26835539789728897 607 27807987039084874 608 28814857564390586 609 29857341709496324 610 30936670152401813 611 32054114998793124 612 33210991390570755 613 34408658678232090 614 35648522127522035 615 36932034175841252 616 38260696242971006 617 39636060077321932 618 41059729676999742 619 42533362731823320 620 44058672661685750 621 45637430160600152 622 47271465359475834 623 48962669479163716 624 50712997125142701 625 52524468056713746 626 54399169621880404 627 56339258650232235 628 58346964036525287 629 60424588765618102 630 62574512653719409 631 64799194513974789 632 67101175065241386 633 69483079247409884 634 71947619307869522 635 74497597276580798 636 77135908240944023 637 79865542990963576 638 82689591494261304 639 85611245722251512 640 88633803337429939 641 91760670712555248 642 94995366843013932 643 98341526571419711 644 101802904739024809 645 105383379628858920 646 109086957370665226 647 112917775616925601 648 116880108216597935 649 120978369138920104 650 125217117432577112 651 129601061413020859 652 134135063924330509 653 138824146807207107 654 143673496481756423 655 148688468713998469 656 153874594539349420 657 159237585346513565 658 164783339162246869 659 170517946073126018 660 176447694893325496 661 182579078945626100 662 188918803135729370 663 195473790115089912 664 202251187786283716 665 209258375872141407 666 216502973878071023 667 223992848093035490 668 231736120036792189 669 239741173919735293 670 248016665604250171 671 256571530552618245 672 265414993333328228 673 274556576087573428 674 284006108613755971 675 293773737384861319 676 303869936245898390 677 314305516016972590 678 325091635840377469 679 336239813405808917 680 347761936986588898 681 359670276325574756 682 371977495401845690 683 384696664018791789 684 397841271344934335 685 411425238247676301 686 425462931655145997 687 439969177681594630 688 454959276859393034 689 470449018105482612 690 486454694875452862 691 502993120022865724 692 520081642931069575 693 537738165320218447 694 555981159415202687 695 574829684759149582 696 594303407479167377 697 614422618168055000 698 635208252313904884 699 656681909315305582 700 678865874144127755 701 701783137564138472 702 725457419100246496 703 749913188533983889 704 775175690257537814 705 801270966123801961 706 828225881267482132 707 856068148392805955 708 884826355148669374 709 914529989941370113 710 945209470956662149 711 976896173589905229 712 1009622461212636748 713 1043421714318833693 714 1078328363139173994 715 1114377918607226809 716 1151607006931443805 717 1190053402491078110 718 1229756064481642673 719 1270755171857699458 720 1313092162174101244 721 1356809768698947394 722 1401952061580955055 723 1448564487262955175 724 1496693912112535898 725 1546388664275050612 726 1597698579912480258 727 1650675047642264483 728 1705371057538694555 729 1761841248312282846 730 1820141959236125120 731 1880331280230553567 732 1942469106886124787 733 2006617193627084764 734 2072839212013595738 735 2141200807167468568 736 2211769659545908917 737 2284615544824723215 738 2359810399346779028 739 2437428383668333180 740 2517545951898194729 741 2600241919124587283 742 2685597534872517863 743 2773696554642310884 744 2864625317725563619 745 2958472823098936502 746 3055330811854052300 747 3155293847704005180 748 3258459404296223610 749 3364927950605244951 750 3474803043412782535 751 3588191417875074264 752 3705203085471894419 753 3825951430053199698 754 3950553311575050789 755 4079129167949080603 756 4211803124901229742 757 4348703103965098717 758 4489960938819894448 759 4635712489788072831 760 4786097767028099498 761 4941261051918823064 762 5101351027503821470 763 5266520907165700330 764 5436928572742755192 765 5612736710919229963 766 5794112959457774134 767 5981230051757462448 768 6174265971670450525 769 6373404106704146035 770 6578833411918523033 771 6790748572275723773 772 7009350176141365327 773 7234844887315045899 774 7467445628688345810 775 7707371764518753729 776 7954849294829876540 777 8210111048522997032 778 8473396889136767845 779 8744953919425929553 780 9025036699132306352 781 9313907461694541911 782 9611836344720631826 783 9919101619529811767 784 10235989935054314602 785 10562796560955919874 786 10899825645725272197 787 11247390474156072425 788 11605813740455227555 789 11975427820901542623 790 12356575062824148380 791 12749608073320948532 792 13154890025010529489 793 13572794961733361123 794 14003708122034988880 795 14448026262824536030 796 14906158001598989098 797 15378524159090221204 798 15865558121296314732 799 16367706202204523161 800 16885428026757083583 801 17419196914798133721 802 17969500286162704056 803 18536840067061887030 804 19121733118549582829 805 19724711666626392473 806 20346323755410662896 807 20987133702312694425 808 21647722577308625744 809 22328688684614123885 810 23030648069536995060 811 23754235028157306505 812 24500102643318752085 813 25268923323905657362 814 26061389371617762170 815 26878213551525262852 816 27720129691362367427 817 28587893285132966992 818 29482282126756732590 819 30404096948595908020 820 31354162091387082298 821 32333326179665701919 822 33342462830023001551 823 34382471365512167897 824 35454277564384924904 825 36558834415678091606 826 37697122910700960014 827 38870152842124992830 828 40078963640617716578 829 41324625219884299729 830 42608238860978129643 831 43930938105877488732 832 45293889692139753717 833 46698294497741364382 834 48145388528888517936 835 49636443918996336510 836 51172769972625982019 837 52755714221636454827 838 54386663528378396245 839 56067045202221299088 840 57798328165305059274 841 59582024132818537534 842 61419688844793397686 843 63312923313694296589 844 65263375125927335590 845 67272739760500016367 846 69342761964116492123 847 71475237144868190056 848 73672012825002264074 849 75934990113819488778 850 78266125242422197545 851 80667431120227046860 852 83140978956232409375 853 85688899903791007440 854 88313386773186827981 855 91016695769564803849 856 93801148301864553510 857 96669132819073985945 858 99623106720840356022 859 102665598297492347623 860 105799208747940759223 861 109026614229208411523 862 112350567987533625175 863 115773902523461970562 864 119299531842384833838 865 122930453741571756872 866 126669752186716866815 867 130520599727634876280 868 134486260007739738335 869 138570090315494511407 870 142775544234119323954 871 147106174336264735225 872 151565634981643123514 873 156157685162797286622 874 160886191458760115879 875 165755131040218256945 876 170768594787739953656 877 175930790465076815844 878 181246046010962625174 879 186718812889765510591 880 192353669566340042850 881 198155325043741204240 882 204128622531119693803 883 210278543178726438971 884 216610209949380468295 885 223128891561540205436 886 229840006575432915800 887 236749127555550555778 888 243861985383121724024 889 251184473649993561266 890 258722653209755628584 891 266482756815607701472 892 274471193923097729985 893 282694555585252870745 894 291159619520583735054 895 299873355279460018293 896 308842929591765132929 897 318075711819241887370 898 327579279597942637960 899 337361424592059337222 900 347430158447118337449 901 357793718861629846809 902 368460575867828615263 903 379439438238344666734 904 390739260112177882143 905 402369247754510238352 906 414338866546538765112 907 426657848117505680927 908 439336197718005791018 909 452384201744320433576 910 465812435515848329080 911 479631771212897812065 912 493853386079980316330 913 508488770799328967471 914 523549738142947493827 915 539048431805298299931 916 554997335528202122301 917 571409282417381735105 918 588297464565576372571 919 605675442878923418378 920 623557157224993109726 921 641956936796357852211 922 660889510811652167909 923 680370019445124566705 924 700414025110303427176 925 721037523985834597760 926 742256957912893429548 927 764089226549201425469 928 786551699912952422657 929 809662231198581614137 930 833439170001689830673 931 857901375831892273559 932 883068232055037062131 933 908959660140309759522 934 935596134357935014945 935 962998696799664904348 936 991188972872146831947 937 1020189187131962841320 938 1050022179616952151796 939 1080711422539116912026 940 1112281037498387330157 941 1144755813078976582453 942 1178161222992393571400 943 1212523444625199098469 944 1247869378160515823072 945 1284226666127633429153 946 1321623713553820689026 947 1360089708568859650851 948 1399654643641655543646 949 1440349337295532194375 950 1482205456486973179176 951 1525255539490408374008 952 1569533019479386993394 953 1615072248642640399390 954 1661908523031111442850 955 1710078107970273926203 956 1759618264239735330293 957 1810567274850156745534 958 1862964472625590346502 959 1916850268416888171414 960 1972266180160560507495 961 2029254862604270283025 962 2087860137919817908012 963 2148127027020220282398 964 2210101781808423868141 965 2273831918169578325098 966 2339366249941284290864 967 2406754923668973575564 968 2476049454387926714225 969 2547302762234197482119 970 2620569210133270228651 971 2695904642363732463795 972 2773366424252317304630 973 2853013482792516579054 974 2934906348450886976057 975 3019107197948042918537 976 3105679898286478449518 977 3194690051806902676650 978 3286205042553480341095 979 3380294083724255199778 980 3477028266495659966297 981 3576480609991853540393 982 3678726112696578346002 983 3783841805072636278202 984 3891906803695718682063 985 4003002366661946285641 986 4117211950585186212924 987 4234621268937624994700 988 4355318352059300964014 989 4479393608584090121760 990 4606939888617765282517 991 4738052548409535209696 992 4872829516862918392880 993 5011371363621132774211 994 5153781369083425901763 995 5300165596081191585507 996 5450632963581177384660 997 5605295322138190006955 998 5764267531475833494804 999 5927667539911107243723 1000 6095616466012998288248