0 1 1 3 2 8 3 17 4 34 5 61 6 105 7 170 8 267 9 403 10 594 11 851 12 1197 13 1648 14 2235 15 2981 16 3927 17 5104 18 6565 19 8351 20 10529 21 13152 22 16303 23 20049 24 24492 25 29715 26 35841 27 42972 28 51255 29 60813 30 71820 31 84423 32 98826 33 115203 34 133791 35 154794 36 178486 37 205104 38 234962 39 268334 40 305578 41 347008 42 393030 43 444002 44 500382 45 562576 46 631098 47 706406 48 789075 49 879619 50 978678 51 1086827 52 1204776 53 1333165 54 1472779 55 1624328 56 1788677 57 1966611 58 2159080 59 2366949 60 2591259 61 2832960 62 3093189 63 3372987 64 3673593 65 3996144 66 4341987 67 4712361 68 5108727 69 5532432 70 5985057 71 6468063 72 6983158 73 7531923 74 8116199 75 8737694 76 9398389 77 10100125 78 10845030 79 11635085 80 12472572 81 13359619 82 14298669 83 15292004 84 16342236 85 17451808 86 18623508 87 19859948 88 21164100 89 22538752 90 23987068 91 25512020 92 27116972 93 28805088 94 30579940 95 32444892 96 34403733 97 36460035 98 38617812 99 40880853 100 43253406 101 45739485 102 48343581 103 51069942 104 53923311 105 56908179 106 60029550 107 63292167 108 66701305 109 70261968 110 73979711 111 77859809 112 81908107 113 86130160 114 90532113 115 95119811 116 99899709 117 104877952 118 110061315 119 115456253 120 121069872 121 126908947 122 132980925 123 139292912 124 145852707 125 152667757 126 159746224 127 167095907 128 174725342 129 182642691 130 190856875 131 199376430 132 208210674 133 217368528 134 226859718 135 236693562 136 246880206 137 257429376 138 268351650 139 279657174 140 291356970 141 303461616 142 315982590 143 328930914 144 342318535 145 356156931 146 370458530 147 385235279 148 400500100 149 416265421 150 432544671 151 449350772 152 466697673 153 484598803 154 503068644 155 522121145 156 541771335 157 562033696 158 582923817 159 604456727 160 626648589 161 649514992 162 673072687 163 697337837 164 722327795 165 748059312 166 774550357 167 801818283 168 829881690 169 858758547 170 888468099 171 919028946 172 950460993 173 982783485 174 1016017002 175 1050181449 176 1085298096 177 1121387523 178 1158471705 179 1196571912 180 1235710840 181 1275910464 182 1317194216 183 1359584792 184 1403106376 185 1447782400 186 1493637816 187 1540696808 188 1588985112 189 1638527680 190 1689351048 191 1741480952 192 1794944745 193 1849768963 194 1905981792 195 1963610585 196 2022684378 197 2083231357 198 2145281425 199 2208863618 200 2274008723 201 2340746643 202 2409109066 203 2479126779 204 2550832389 205 2624257584 206 2699435907 207 2776399965 208 2855184255 209 2935822320 210 3018349629 211 3102800679 212 3189211929 213 3277618848 214 3368058903 215 3460568553 216 3555186292 217 3651949587 218 3750897977 219 3852069956 220 3955506127 221 4061246029 222 4169331348 223 4279802687 224 4392702834 225 4508073475 226 4625958519 227 4746400754 228 4869445230 229 4995135856 230 5123518842 231 5254639238 232 5388544434 233 5525280640 234 5664896446 235 5807439242 236 5952958838 237 6101503824 238 6253125250 239 6407872926 240 6565799163 241 6726955011 242 6891394062 243 7059168627 244 7230333600 245 7404942573 246 7583051763 247 7764716064 248 7949993037 249 8138938899 250 8331612576 251 8528071629 252 8728376371 253 8932585728 254 9140761421 255 9352963763 256 9569255905 257 9789699568 258 10014359355 259 10243298417 260 10476582831 261 10714277200 262 10956449097 263 11203164599 264 11454492798 265 11710501267 266 11971260639 267 12236840006 268 12507311565 269 12782745949 270 13063216942 271 13348796741 272 13639560740 273 13935582723 274 14236939717 275 14543707116 276 14855963604 277 15173786208 278 15497255292 279 15826449540 280 16161451020 281 16502340096 282 16849200564 283 17202114492 284 17561167428 285 17926443168 286 18298029036 287 18676010580 288 19060476925 289 19451515395 290 19849216940 291 20253670685 292 20664969430 293 21083204125 294 21508469445 295 21940858190 296 22380466935 297 22827390355 298 23281726950 299 23743573295 300 24213029841 301 24690195088 302 25175171463 303 25668059417 304 26168963379 305 26677985776 306 27195233065 307 27720809675 308 28254824117 309 28797382848 310 29348596459 311 29908573461 312 30477426552 313 31055266323 314 31642207605 315 32238363096 316 32843849787 317 33458782509 318 34083280440 319 34717460571 320 35361444294 321 36015350787 322 36679303683 323 37353424374 324 38037838762 325 38732670480 326 39438047726 327 40154096402 328 40880947030 329 41618727808 330 42367571610 331 43127608958 332 43898975106 333 44681802928 334 45476230086 335 46282391834 336 47100428271 337 47930477059 338 48772680762 339 49627179479 340 50494118268 341 51373639693 342 52265891335 343 53171018252 344 54089170577 345 55020495891 346 55965146908 347 56923273761 348 57895031775 349 58880573664 350 59880057393 351 60893638287 352 61921476981 353 62963731440 354 64020564999 355 65092138293 356 66178617387 357 67280165616 358 68396951805 359 69529142019 360 70676907874 361 71840418195 362 73019847419 363 74215367162 364 75427154713 365 76655384509 366 77900236722 367 79161888641 368 80440523352 369 81736321027 370 83049467697 371 84380146448 372 85728546288 373 87094853248 374 88479259344 375 89881953584 376 91303131024 377 92742983680 378 94201709680 379 95679504080 380 97176568112 381 98693099904 382 100229303824 383 101785381104 384 103361539281 385 104957982723 386 106574922168 387 108212565153 388 109871125650 389 111550814397 390 113251848633 391 114974442330 392 116718816027 393 118485186963 394 120273779010 395 122084812707 396 123918515293 397 125775110640 398 127654829387 399 129557898773 400 131484552871 401 133435022320 402 135409544661 403 137408353967 404 139431691281 405 141479794144 406 143552907135 407 145651271297 408 147775134780 409 149924742163 410 152100345201 411 154302192044 412 156530538087 413 158785635085 414 161067742108 415 163377114551 416 165714015194 417 168078703107 418 170471444815 419 172892503098 420 175342148262 421 177820646832 422 180328272930 423 182865296862 424 185431996602 425 188028646272 426 190655527734 427 193312918962 428 196001105742 429 198720369936 430 201471001290 431 204253285590 432 207067516579 433 209913984003 434 212792985638 435 215704815227 436 218649774616 437 221628161581 438 224640282075 439 227686437944 440 230766939285 441 233882092051 442 237032210520 443 240217604789 444 243438593355 445 246695490496 446 249988618965 447 253318297259 448 256684852425 449 260088607216 450 263529893011 451 267009036857 452 270526374503 453 274082237328 454 277676965489 455 281310894735 456 284984369670 457 288697730451 458 292451326167 459 296245501422 460 300080609829 461 303957000477 462 307875031542 463 311835056637 464 315837438540 465 319882535427 466 323970714717 467 328102339188 468 332277780940 469 336497407392 470 340761595364 471 345070716956 472 349425153748 473 353825282560 474 358271489772 475 362764156964 476 367303675356 477 371890431328 478 376524820980 479 381207235532 480 385938076005 481 390717738499 482 395546628996 483 400425148517 484 405353708046 485 410332713565 486 415362581101 487 420443721638 488 425576556287 489 430761501075 490 435998982238 491 441289420887 492 446633248425 493 452030891088 494 457482785487 495 462989363025 496 468551065563 497 474168329712 498 479841602625 499 485571326163 500 491357952813 501 497201929728 502 503103714771 503 509063760429 504 515082529984 505 521160481299 506 527298083117 507 533495798720 508 539754102355 509 546073462765 510 552454359744 511 558897267539 512 565402671534 513 571971051523 514 578602898523 515 585298697918 516 592058946402 517 598884134992 518 605774766102 519 612731336426 520 619754354142 521 626844321664 522 634001752978 523 641227156262 524 648521051354 525 655883952240 526 663316384654 527 670818868434 528 678391935255 529 686036110851 530 693751932882 531 701539933023 532 709400654964 533 717334636365 534 725342426991 535 733424570532 536 741581622873 537 749814133779 538 758122665300 539 766507773321 540 774970026103 541 783509985696 542 792128226617 543 800825317127 544 809601838045 545 818458363888 546 827395481823 547 836413772669 548 845513829987 549 854696240944 550 863961605541 551 873310517339 552 882743582826 553 892261402003 554 901864587891 555 911553746978 556 921329498865 557 931192456573 558 941143246330 559 951182487737 560 961310813696 561 971528850435 562 981837237577 563 992236608024 564 1002727608168 565 1013310877632 566 1023987069624 567 1034756830536 568 1045620820440 569 1056579692544 570 1067634113832 571 1078784744376 572 1090032258120 573 1101377322048 574 1112820617112 575 1124362817256 576 1136004610489 577 1147746677763 578 1159589714192 579 1171534407785 580 1183581460810 581 1195731568381 582 1207985439969 583 1220343777842 584 1232807298723 585 1245376712083 586 1258052741946 587 1270836105035 588 1283727532725 589 1296727749040 590 1309837492755 591 1323057495245 592 1336388502735 593 1349831254000 594 1363386502765 595 1377054995255 596 1390837492745 597 1404734748960 598 1418747532775 599 1432876605465 600 1447122743556 601 1461486715923 602 1475969306793 603 1490571292692 604 1505293465599 605 1520136609741 606 1535101524900 607 1550189003055 608 1565399851842 609 1580734871043 610 1596194876199 611 1611780674946 612 1627493090782 613 1643332939248 614 1659301051850 615 1675398252086 616 1691625379522 617 1707983265664 618 1724472758190 619 1741094696666 620 1757849936934 621 1774739326672 622 1791763729938 623 1808924002574 624 1826221016907 625 1843655636995 626 1861228743486 627 1878941208707 628 1896793921680 629 1914787763053 630 1932923630275 631 1951202412368 632 1969625015261 633 1988192336403 634 2006905290256 635 2025764782749 636 2044771736931 637 2063927067264 638 2083231705437 639 2102686574499 640 2122292614833 641 2142050758128 642 2161961953515 643 2182027141377 644 2202247279647 645 2222623317456 646 2243156221593 647 2263846949991 648 2284696478350 649 2305705773459 650 2326875819983 651 2348207593622 652 2369702088061 653 2391360287965 654 2413183196094 655 2435171806133 656 2457327129972 657 2479650170371 658 2502141948405 659 2524803475964 660 2547635783364 661 2570639891680 662 2593816840524 663 2617167660212 664 2640693399708 665 2664395098624 666 2688273815332 667 2712330598796 668 2736566516852 669 2760982627872 670 2785580009212 671 2810359728708 672 2835322873293 673 2860470520323 674 2885803766364 675 2911323698349 676 2937031422534 677 2962928035485 678 2989014653205 679 3015292381950 680 3041762347527 681 3068425665939 682 3095283472854 683 3122336894079 684 3149587075201 685 3177035151888 686 3204682279703 687 3232529604233 688 3260578291075 689 3288829495792 690 3317284394073 691 3345944151515 692 3374809953957 693 3403882977088 694 3433164416955 695 3462655459397 696 3492357310728 697 3522271166995 698 3552398244837 699 3582739750568 700 3613296911211 701 3644070943405 702 3675063084616 703 3706274561867 704 3737706623126 705 3769360505859 706 3801237468595 707 3833338759302 708 3865665647130 709 3898219390608 710 3931001269566 711 3964012553154 712 3997254531942 713 4030728485760 714 4064435715978 715 4098377513166 716 4132555189554 717 4166970046512 718 4201623407190 719 4236516583818 720 4271650910527 721 4307027710467 722 4342648328810 723 4378514099687 724 4414626379372 725 4450986513037 726 4487595868119 727 4524455800892 728 4561567690017 729 4598932902931 730 4636552829580 731 4674428848625 732 4712562361359 733 4750954757728 734 4789607450433 735 4828521840767 736 4867699352901 737 4907141399536 738 4946849416375 739 4986824827589 740 5027069080475 741 5067583610736 742 5108369877325 743 5149429327539 744 5190763432050 745 5232373649811 746 5274261463275 747 5316428343114 748 5358875783625 749 5401605267261 750 5444618300226 751 5487916376817 752 5531501015208 753 5575373721603 754 5619536026209 755 5663989447200 756 5708735526880 757 5753775795456 758 5799111807392 759 5844745104992 760 5890677254944 761 5936909811712 762 5983444354272 763 6030282449312 764 6077425688160 765 6124875649792 766 6172633937952 767 6220702143968 768 6269081884065 769 6317774761987 770 6366782406504 771 6416106433841 772 6465748485378 773 6515710189885 774 6565993201417 775 6616599161354 776 6667529736491 777 6718786580883 778 6770371374130 779 6822285783027 780 6874531500045 781 6927110204784 782 6980023602651 783 7033273386117 784 7086861273591 785 7140788970480 786 7195058208261 787 7249670705343 788 7304628206337 789 7359932442720 790 7415585172303 791 7471588139697 792 7527943115980 793 7584651858963 794 7641716153057 795 7699137769340 796 7756918505623 797 7815060146317 798 7873564502700 799 7932433372583 800 7991668580778 801 8051271938563 802 8111245284351 803 8171590442954 804 8232309266454 805 8293403593264 806 8354875289202 807 8416726206350 808 8478958224330 809 8541573208960 810 8604573053734 811 8667959638274 812 8731734870014 813 8795900642448 814 8860458877018 815 8925411481158 816 8990760390387 817 9056507526147 818 9122654838102 819 9189204261771 820 9256157761032 821 9323517285549 822 9391284813483 823 9459462308712 824 9528051763749 825 9597055156755 826 9666474494664 827 9736311769989 828 9806569004155 829 9877248204096 830 9948351405797 831 10019880630683 832 10091837929369 833 10164225337840 834 10237044921411 835 10310298730697 836 10383988845783 837 10458117331984 838 10532686284225 839 10607697782591 840 10683153936918 841 10759056842131 842 10835408623047 843 10912211389502 844 10989467281365 845 11067178423453 846 11145346970758 847 11223975063149 848 11303064870812 849 11382618548739 850 11462638282381 851 11543126241924 852 11624084628156 853 11705515626528 854 11787421453236 855 11869804309068 856 11952666425700 857 12036010019328 858 12119837337180 859 12204150610932 860 12288952103436 861 12374244061920 862 12460028764932 863 12546308475324 864 12633085487413 865 12720362079747 866 12808140562484 867 12896423229941 868 12985212408190 869 13074510407389 870 13164319569597 871 13254642220886 872 13345480719375 873 13436837407123 874 13528714658382 875 13621114831271 876 13714040316249 877 13807493487568 878 13901476751967 879 13995992499905 880 14091043154475 881 14186631122416 882 14282758843249 883 14379428740067 884 14476643268893 885 14574404869248 886 14672716013731 887 14771579158365 888 14870996792400 889 14970971388435 890 15071505452445 891 15172601473680 892 15274261974915 893 15376489462125 894 15479286474960 895 15582655536195 896 15686599202430 897 15791120013315 898 15896220542475 899 16001903346510 900 16108171016146 901 16215026125008 902 16322471280998 903 16430509074842 904 16539142131694 905 16648373059456 906 16758204500610 907 16868639080310 908 16979679458442 909 17091328277488 910 17203588214814 911 17316461930306 912 17429952118887 913 17544061457923 914 17658792659970 915 17774148419951 916 17890131468132 917 18006744517069 918 18123990314815 919 18241871591636 920 18360391113449 921 18479551628307 922 18599355920068 923 18719806754649 924 18840906933927 925 18962659241760 926 19085066498121 927 19208131504887 928 19331857100205 929 19456246104048 930 19581301372815 931 19707025744653 932 19833422094291 933 19960493278128 934 20088242189301 935 20216671702539 936 20345784729466 937 20475584163219 938 20606072933987 939 20737253953394 940 20869130170273 941 21001704514813 942 21134979954570 943 21268959438377 944 21403645952592 945 21539042464771 946 21675151980153 947 21811977485096 948 21949522003800 949 22087788541504 950 22226780141448 951 22366499827832 952 22506950663016 953 22648135690240 954 22790057991064 955 22932720627848 956 23076126701432 957 23220279293376 958 23365181523880 959 23510836493784 960 23657247342729 961 23804417190915 962 23952349197504 963 24101046502137 964 24250512283578 965 24400749700989 966 24551761952817 967 24703552217826 968 24856123714227 969 25009479640467 970 25163623234602 971 25318557714843 972 25474286339173 973 25630812345648 974 25788139012259 975 25946269596989 976 26105207397919 977 26264955693040 978 26425517800605 979 26586897018695 980 26749096685817 981 26912120120224 982 27075970680759 983 27240651705929 984 27406166574996 985 27572518646803 986 27739711321113 987 27907747977188 988 28076632035375 989 28246366895437 990 28416955998388 991 28588402764575 992 28760710655762 993 28933883112963 994 29107923618775 995 29282835634962 996 29458622665038 997 29635288191600 998 29812835739162 999 29991268811238 1000 30170590953426