0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 30 10 42 11 56 12 76 13 99 14 131 15 169 16 219 17 278 18 355 19 445 20 560 21 695 22 863 23 1060 24 1303 25 1586 26 1930 27 2331 28 2812 29 3370 30 4035 31 4802 32 5708 33 6751 34 7972 35 9373 36 11004 37 12866 38 15021 39 17475 40 20298 41 23501 42 27169 43 31316 44 36043 45 41373 46 47420 47 54218 48 61903 49 70515 50 80215 51 91058 52 103226 53 116792 54 131970 55 148847 56 167672 57 188556 58 211782 59 237489 60 266006 61 297495 62 332337 63 370733 64 413112 65 459718 66 511045 67 567377 68 629281 69 697097 70 771464 71 852785 72 941790 73 1038944 74 1145078 75 1260740 76 1386861 77 1524081 78 1673457 79 1835721 80 2012069 81 2203348 82 2410895 83 2635689 84 2879236 85 3142647 86 3427615 87 3735414 88 4067930 89 4426616 90 4813587 91 5230481 92 5679662 93 6162991 94 6683091 95 7242069 96 7842848 97 8487789 98 9180146 99 9922579 100 10718685 101 11571451 102 12484869 103 13462270 104 14508075 105 15626011 106 16820948 107 18097047 108 19459689 109 20913488 110 22464381 111 24117499 112 25879361 113 27755663 114 29753578 115 31879397 116 34141000 117 36545347 118 39101065 119 41815841 120 44699133 121 47759392 122 51006974 123 54451188 124 58103334 125 61973647 126 66074473 127 70417024 128 75014774 129 79880017 130 85027416 131 90470433 132 96225037 133 102305924 134 108730467 135 115514722 136 122677540 137 130236438 138 138211888 139 146622950 140 155491832 141 164839281 142 174689336 143 185064559 144 195990980 145 207493074 146 219599002 147 232335324 148 245732448 149 259819164 150 274628317 151 290191050 152 306542807 153 323717285 154 341752667 155 360685378 156 380556557 157 401405504 158 423276511 159 446211984 160 470259534 161 495464875 162 521879190 163 549551684 164 578537336 165 608889106 166 640665969 167 673924880 168 708729103 169 745139797 170 783224779 171 823049720 172 864687223 173 908207751 174 953689028 175 1001206560 176 1050843495 177 1102680731 178 1156807122 179 1213309282 180 1272282150 181 1333818347 182 1398019251 183 1464983897 184 1534820423 185 1607634648 186 1683541906 187 1762655144 188 1845097299 189 1930988902 190 2020460870 191 2113641746 192 2210670920 193 2311685347 194 2416833355 195 2526260833 196 2640125479 197 2758582603 198 2881799840 199 3009942381 200 3143188326 201 3281713335 202 3425706473 203 3575354434 204 3730857880 205 3892415064 206 4060238850 207 4234539718 208 4415543308 209 4603472960 210 4798567807 211 5001064654 212 5211216809 213 5429275296 214 5655508252 215 5890181641 216 6133579232 217 6385982615 218 6647691970 219 6919005360 220 7200240116 221 7491711584 222 7793755151 223 8106704235 224 8430913148 225 8766734325 226 9114541845 227 9474708078 228 9847627884 229 10233694450 230 10633324399 231 11046932797 232 11474958976 233 11917840913 234 12376041781 235 12850023467 236 13340274081 237 13847280602 238 14371557152 239 14913616956 240 15474001405 241 16053251090 242 16651935901 243 17270625121 244 17909918335 245 18570414804 246 19252745210 247 19957540052 248 20685462483 249 21437175703 250 22213376679 251 23014762750 252 23842066249 253 24696020064 254 25577393421 255 26486956385 256 27425516570 257 28393882812 258 29392902842 259 30423425839 260 31486341342 261 32582540670 262 33712956839 263 34878525088 264 36080223811 265 37319033910 266 38595981036 267 39912093745 268 41268446799 269 42666118368 270 44106234428 271 45589924702 272 47118368453 273 48692749154 274 50314301408 275 51984264609 276 53703931011 277 55474598072 278 57297617996 279 59174348721 280 61106204667 281 63094606641 282 65141033825 283 67246972275 284 69413968455 285 71643576320 286 73937412122 287 76297100350 288 78724329840 289 81220798227 290 83788269707 291 86428517974 292 89143385338 293 91934724449 294 94804458794 295 97754522858 296 100786924347 297 103903682767 298 107106893081 299 110398662992 300 113781178067 301 117256637363 302 120827320389 303 124495521052 304 128263616125 305 132133997837 306 136109143886 307 140191548291 308 144383793328 309 148688478610 310 153108294635 311 157645950412 312 162304248649 313 167086011548 314 171994158015 315 177031627599 316 182201459382 317 187506714404 318 192950556281 319 198536171691 320 204266853127 321 210145917422 322 216176790295 323 222362923263 324 228707879998 325 235215251220 326 241888743289 327 248732091045 328 255749148277 329 262943798861 330 270320049156 331 277881937002 332 285633626471 333 293579314708 334 301723328655 335 310070030110 336 318623914458 337 327389513504 338 336371496673 339 345574571567 340 355003587250 341 364663432919 342 374559143321 343 384695795077 344 395078614673 345 405712872418 346 416603992619 347 427757445564 348 439178859923 349 450873912271 350 462848442206 351 475108339372 352 487659660880 353 500508516254 354 513661187188 355 527124009925 356 540903497836 357 555006221205 358 569438932221 359 584208442570 360 599321750887 361 614785917651 362 630608195613 363 646795901962 364 663356551269 365 680297725375 366 697627208904 367 715352856341 368 733482730641 369 752024967452 370 770987916384 371 790380002821 372 810209871890 373 830486247337 374 851218078727 375 872414397347 376 894084466170 377 916237633254 378 938883484531 379 962031694125 380 985692180525 381 1009874953789 382 1034590274631 383 1059848498990 384 1085660240058 385 1112036209656 386 1138987383782 387 1166524840750 388 1194659929768 389 1223404106320 390 1252769103842 391 1282766765750 392 1313409220798 393 1344708711726 394 1376677773785 395 1409329060513 396 1442675525472 397 1476730244552 398 1511506601544 399 1547018106906 400 1583278586653 401 1620301998113 402 1658102622195 403 1696694875513 404 1736093506632 405 1776313404533 406 1817369798310 407 1859278062503 408 1902053920304 409 1945713245107 410 1990272267880 411 2035747374880 412 2082155318637 413 2129513012399 414 2177837744773 415 2227146970244 416 2277458528127 417 2328790429120 418 2381161078019 419 2434589056846 420 2489093351387 421 2544693130225 422 2601407975786 423 2659257659233 424 2718262375415 425 2778442514218 426 2839818899485 427 2902412556122 428 2966244953686 429 3031337769188 430 3097713134771 431 3165393396797 432 3234401367671 433 3304760080514 434 3376493045837 435 3449624001753 436 3524177174883 437 3600177026726 438 3677648518876 439 3756616854793 440 3837107750067 441 3919147169545 442 4002761602024 443 4087977793365 444 4174823025651 445 4263324845555 446 4353511348724 447 4445410903340 448 4539052439091 449 4634465166556 450 4731678870847 451 4830723626041 452 4931630094256 453 5034429235095 454 5139152609486 455 5245832084798 456 5354500143507 457 5465189583203 458 5577933830889 459 5692766637798 460 5809722398652 461 5928835841973 462 6050142354380 463 6173677665586 464 6299478178518 465 6427580648961 466 6558022520816 467 6690841601078 468 6826076400305 469 6963765802089 470 7103949409585 471 7246667209409 472 7391959923512 473 7539868668232 474 7690435311573 475 7843702126567 476 7999712154800 477 8158508854031 478 8320136467260 479 8484639665303 480 8652063921478 481 8822455148275 482 8995860078540 483 9172325896182 484 9351900623083 485 9534632744605 486 9720571602312 487 9909767013378 488 10102269670015 489 10298130752709 490 10497402335612 491 10700136994359 492 10906388217495 493 11116210007982 494 11329657301560 495 11546785561883 496 11767651205029 497 11992311189053 498 12220823444744 499 12453246458635 500 12689639710944 501 12930063251983 502 13174578146497 503 13423246044272 504 13676129630924 505 13933292191772 506 14194798070042 507 14460712223930 508 14731100691409 509 15006030141286 510 15285568344714 511 15569783719261 512 15858745808096 513 16152524817021 514 16451192100486 515 16754819692421 516 17063480799157 517 17377249323071 518 17696200363431 519 18020409732754 520 18349954464729 521 18684912324147 522 19025362321999 523 19371384217964 524 19723059043671 525 20080468597694 526 20443695976118 527 20812825060904 528 21187941057851 529 21569129977277 530 21956479180441 531 22350076852459 532 22750012556288 533 23156376698789 534 23569261092351 535 23988758413040 536 24414962770921 537 24847969160227 538 25287874037493 539 25734774764624 540 26188770194935 541 26649960108043 542 27118445804912 543 27594329534493 544 28077715096818 545 28568707262338 546 29067412383169 547 29573937804012 548 30088392482665 549 30610886392434 550 31141531150986 551 31680439415190 552 32227725518401 553 32783504856620 554 33347894535328 555 33921012746891 556 34502979425970 557 35093915619147 558 35693944149032 559 36303188974923 560 36921775866772 561 37549831756806 562 38187485422377 563 38834866829537 564 39492107824838 565 40159341469704 566 40836702742375 567 41524327862983 568 42222355004637 569 42930923610199 570 43650175112634 571 44380252242274 572 45121299757631 573 45873463743086 574 46636892349126 575 47411735081489 576 48198143550921 577 48996270752561 578 49806271826470 579 50628303327137 580 51462523993737 581 52309094010817 582 53168175788400 583 54039933212604 584 54924532436813 585 55822141122163 586 56732929238724 587 57657068296914 588 58594732158804 589 59546096259170 590 60511338428224 591 61490638102204 592 62484177156435 593 63492139106571 594 64514709952082 595 65552077366851 596 66604431554383 597 67671964427676 598 68754870475065 599 69853345930446 600 70967589649872 601 72097802270814 602 73244187100850 603 74406949265873 604 75586296609708 605 76782438832425 606 77995588401009 607 79225959676418 608 80473769836666 609 81739237992514 610 83022586121839 611 84324038175105 612 85643821021125 613 86982163540959 614 88339297586436 615 89715457062385 616 91110878896735 617 92525802112266 618 93960468808431 619 95415123221191 620 96890012717967 621 98385386845472 622 99901498336610 623 101438602147507 624 102996956476443 625 104576821788678 626 106178461848862 627 107802142733545 628 109448133875851 629 111116707066880 630 112808137512794 631 114522702823644 632 116260684084322 633 118022364830734 634 119808032133361 635 121617975562028 636 123452488282190 637 125311866006827 638 127196408106966 639 129106416550561 640 131042197025994 641 133004057869217 642 134992311200371 643 137007271837688 644 139049258448704 645 141118592450838 646 143215599175928 647 145340606758766 648 147493947315091 649 149675955816530 650 151886971283614 651 154127335647007 652 156397394954227 653 158697498218501 654 161027998639309 655 163389252437306 656 165781620090248 657 168205465153882 658 170661155511948 659 173149062184337 660 175669560591308 661 178223029347335 662 180809851541148 663 183430413515160 664 186085106159940 665 188774323680606 666 191498464905879 667 194257932039815 668 197053131987068 669 199884475089830 670 202752376467952 671 205657254742465 672 208599533390689 673 211579639454716 674 214598004913143 675 217655065374404 676 220751261463716 677 223887037502680 678 227062842911608 679 230279130873681 680 233536359754342 681 236834991749904 682 240175494322597 683 243558338835061 684 246984002001153 685 250452964504650 686 253965712467537 687 257522736052789 688 261124530948696 689 264771596957163 690 268464439494245 691 272203568162225 692 275989498268087 693 279822749379276 694 283703846858618 695 287633320405248 696 291611705606117 697 295639542460338 698 299717376949076 699 303845759543149 700 308025246789806 701 312256399805100 702 316539785877720 703 320875976944351 704 325265551212317 705 329709091617828 706 334207187465925 707 338760432873134 708 343369428424869 709 348034779600661 710 352757098450873 711 357537002004362 712 362375113962950 713 367272063093102 714 372228484938292 715 377245020192854 716 382322316434089 717 387461026478171 718 392661810130450 719 397925332524952 720 403252265893044 721 408643287884662 722 414099083357237 723 419620342678524 724 425207763534149 725 430862049213673 726 436583910436936 727 442374063621437 728 448233232729397 729 454162147516302 730 460161545397089 731 466232169677475 732 472374771439419 733 478590107753327 734 484878943584721 735 491242049987186 736 497680206028587 737 504194196966429 738 510784816193817 739 517452863395220 740 524199146514157 741 531024479889237 742 537929686241911 743 544915594794476 744 551983043278021 745 559132876030425 746 566365946026519 747 573683112955926 748 581085245273742 749 588573218259911 750 596147916090627 751 603810229877202 752 611561059760219 753 619401312927778 754 627331905730655 755 635353761681668 756 643467813592006 757 651675001549666 758 659976275079055 759 668372591098309 760 676864916100418 761 685454224091205 762 694141498792166 763 702927731557020 764 711813923598325 765 720801083882481 766 729890231378355 767 739082392932516 768 748378605540055 769 757779914197909 770 767287374200042 771 776902048968695 772 786625012372111 773 796457346535559 774 806400144181766 775 816454506419564 776 826621545109188 777 836902380628405 778 847298144260873 779 857809975941556 780 868439026668334 781 879186456224528 782 890053435615977 783 901041144770523 784 912150774998649 785 923383526671826 786 934740611706917 787 946223251221153 788 957832678042540 789 969570134341289 790 981436874164368 791 993434161045274 792 1005563270562911 793 1017825487927480 794 1030222110565932 795 1042754445683821 796 1055423812875402 797 1068231541663392 798 1081178974133938 799 1094267462451953 800 1107498371523261 801 1120873076485359 802 1134392965394808 803 1148059436695385 804 1161873901930871 805 1175837783188304 806 1189952515838513 807 1204219545954294 808 1218640333076724 809 1233216347610226 810 1247949073614894 811 1262840006176082 812 1277890654225096 813 1293102537883171 814 1308477191308510 815 1324016160016668 816 1339721003754130 817 1355593293792729 818 1371634615832195 819 1387846567268394 820 1404230760122822 821 1420788818286723 822 1437522380477750 823 1454433097457544 824 1471522635017953 825 1488792671171932 826 1506244899167276 827 1523881024652902 828 1541702768720310 829 1559711865042771 830 1577910062947020 831 1596299124525163 832 1614880827734503 833 1633656963484300 834 1652629338763921 835 1671799773701970 836 1691170104725255 837 1710742181590125 838 1730517870570171 839 1750499051461855 840 1770687620801164 841 1791085488841021 842 1811694582799449 843 1832516843808590 844 1853554230192185 845 1874808714388395 846 1896282286256831 847 1917976949972604 848 1939894727365486 849 1962037654784989 850 1984407786469514 851 2007007191384636 852 2029837956622451 853 2052902184210506 854 2076201994543934 855 2099739523164850 856 2123516924225058 857 2147536367238149 858 2171800040573036 859 2196310148176077 860 2221068913098091 861 2246078574186334 862 2271341389642776 863 2296859633688188 864 2322635600151859 865 2348671599105160 866 2374969960485401 867 2401533030698671 868 2428363176275574 869 2455462780445607 870 2482834246825039 871 2510479995960113 872 2538402469049775 873 2566604124457541 874 2595087441466761 875 2623854916763470 876 2652909068224406 877 2682252431368124 878 2711887563178558 879 2741817038524154 880 2772043454014657 881 2802569424390621 882 2833397586413674 883 2864530595223637 884 2895971128265009 885 2927721881611534 886 2959785573926565 887 2992164942757440 888 3024862748529971 889 3057881770809798 890 3091224812333866 891 3124894695238546 892 3158894265125699 893 3193226387260005 894 3227893950669836 895 3262899864310950 896 3298247061205029 897 3333938494569551 898 3369977141991609 899 3406366001526350 900 3443108095906325 901 3480206468605627 902 3517664188087694 903 3555484343834946 904 3593670050632541 905 3632224444566016 906 3671150687341260 907 3710451962247226 908 3750131478515068 909 3790192467245696 910 3830638185805631 911 3871471913721890 912 3912696957114800 913 3954316644557289 914 3996334331547616 915 4038753396332866 916 4081577244419070 917 4124809304361452 918 4168453032312231 919 4212511907774573 920 4256989438191099 921 4301889154661345 922 4347214616568448 923 4392969407262687 924 4439157138726553 925 4485781447221372 926 4532845997993834 927 4580354480885469 928 4628310615078062 929 4676718144668561 930 4725580843453676 931 4774902510467132 932 4824686974806534 933 4874938091132784 934 4925659744536581 935 4976855846002638 936 5028530337316070 937 5080687186488317 938 5133330392706590 939 5186463981721227 940 5240092010835562 941 5294218564257395 942 5348847758129569 943 5403983735842411 944 5459630673108138 945 5515792773234082 946 5572474272238267 947 5629679434086103 948 5687412555847412 949 5745677962893380 950 5804480014098281 951 5863823096996448 952 5923711633025975 953 5984150072648473 954 6045142900635004 955 6106694631145401 956 6168809813059672 957 6231493025016673 958 6294748880788278 959 6358582024280117 960 6422997134948797 961 6487998922761454 962 6553592133659336 963 6619781544475944 964 6686571968444148 965 6753968250075754 966 6821975270712453 967 6890597943363492 968 6959841218303796 969 7029710077869486 970 7100209542100404 971 7171344663496297 972 7243120532704016 973 7315542273231058 974 7388615047180789 975 7462344049923113 976 7536734515874865 977 7611791713130490 978 7687520949287933 979 7763927566035889 980 7841016945028608 981 7918794502429494 982 7997265694831969 983 8076436013762327 984 8156310991646896 985 8236896196270758 986 8318197236794681 987 8400219758169449 988 8482969447199660 989 8566452026916580 990 8650673262689142 991 8735638956551840 992 8821354953366413 993 8907827135104572 994 8995061427057400 995 9083063792075891 996 9171840236828352 997 9261396805995263 998 9351739588578256 999 9442874712048993 1000 9534808348706751