0 0 1 1 2 9 3 36 4 118 5 315 6 711 7 1414 8 2556 9 4293 10 6805 11 10296 12 14994 13 21151 14 29043 15 38970 16 51256 17 66249 18 84321 19 105868 20 131310 21 161091 22 195679 23 235566 24 281268 25 333325 26 392301 27 458784 28 533386 29 616743 30 709515 31 812386 32 926064 33 1051281 34 1188793 35 1339380 36 1503846 37 1683019 38 1877751 39 2088918 40 2317420 41 2564181 42 2830149 43 3116296 44 3423618 45 3753135 46 4105891 47 4482954 48 4885416 49 5314393 50 5771025 51 6256476 52 6771934 53 7318611 54 7897743 55 8510590 56 9158436 57 9842589 58 10564381 59 11325168 60 12126330 61 12969271 62 13855419 63 14786226 64 15763168 65 16787745 66 17861481 67 18985924 68 20162646 69 21393243 70 22679335 71 24022566 72 25424604 73 26887141 74 28411893 75 30000600 76 31655026 77 33376959 78 35168211 79 37030618 80 38966040 81 40976361 82 43063489 83 45229356 84 47475918 85 49805155 86 52219071 87 54719694 88 57309076 89 59989293 90 62762445 91 65630656 92 68596074 93 71660871 94 74827243 95 78097410 96 81473616 97 84958129 98 88553241 99 92261268 100 96084550 101 100025451 102 104086359 103 108269686 104 112577868 105 117013365 106 121578661 107 126276264 108 131108706 109 136078543 110 141188355 111 146440746 112 151838344 113 157383801 114 163079793 115 168929020 116 174934206 117 181098099 118 187423471 119 193913118 120 200569860 121 207396541 122 214396029 123 221571216 124 228925018 125 236460375 126 244180251 127 252087634 128 260185536 129 268476993 130 276965065 131 285652836 132 294543414 133 303639931 134 312945543 135 322463430 136 332196796 137 342148869 138 352322901 139 362722168 140 373349970 141 384209631 142 395304499 143 406637946 144 418213368 145 430034185 146 442103841 147 454425804 148 467003566 149 479840643 150 492940575 151 506306926 152 519943284 153 533853261 154 548040493 155 562508640 156 577261386 157 592302439 158 607635531 159 623264418 160 639192880 161 655424721 162 671963769 163 688813876 164 705978918 165 723462795 166 741269431 167 759402774 168 777866796 169 796665493 170 815802885 171 835283016 172 855109954 173 875287791 174 895820643 175 916712650 176 937967976 177 959590809 178 981585361 179 1003955868 180 1026706590 181 1049841811 182 1073365839 183 1097283006 184 1121597668 185 1146314205 186 1171437021 187 1196970544 188 1222919226 189 1249287543 190 1276079995 191 1303301106 192 1330955424 193 1359047521 194 1387581993 195 1416563460 196 1445996566 197 1475885979 198 1506236391 199 1537052518 200 1568339100 201 1600100901 202 1632342709 203 1665069336 204 1698285618 205 1731996415 206 1766206611 207 1800921114 208 1836144856 209 1871882793 210 1908139905 211 1944921196 212 1982231694 213 2020076451 214 2058460543 215 2097389070 216 2136867156 217 2176899949 218 2217492621 219 2258650368 220 2300378410 221 2342681991 222 2385566379 223 2429036866 224 2473098768 225 2517757425 226 2563018201 227 2608886484 228 2655367686 229 2702467243 230 2750190615 231 2798543286 232 2847530764 233 2897158581 234 2947432293 235 2998357480 236 3049939746 237 3102184719 238 3155098051 239 3208685418 240 3262952520 241 3317905081 242 3373548849 243 3429889596 244 3486933118 245 3544685235 246 3603151791 247 3662338654 248 3722251716 249 3782896893 250 3844280125 251 3906407376 252 3969284634 253 4032917911 254 4097313243 255 4162476690 256 4228414336 257 4295132289 258 4362636681 259 4430933668 260 4500029430 261 4569930171 262 4640642119 263 4712171526 264 4784524668 265 4857707845 266 4931727381 267 5006589624 268 5082300946 269 5158867743 270 5236296435 271 5314593466 272 5393765304 273 5473818441 274 5554759393 275 5636594700 276 5719330926 277 5802974659 278 5887532511 279 5973011118 280 6059417140 281 6146757261 282 6235038189 283 6324266656 284 6414449418 285 6505593255 286 6597704971 287 6690791394 288 6784859376 289 6879915793 290 6975967545 291 7073021556 292 7171084774 293 7270164171 294 7370266743 295 7471399510 296 7573569516 297 7676783829 298 7781049541 299 7886373768 300 7992763650 301 8100226351 302 8208769059 303 8318398986 304 8429123368 305 8540949465 306 8653884561 307 8767935964 308 8883111006 309 8999417043 310 9116861455 311 9235451646 312 9355195044 313 9476099101 314 9598171293 315 9721419120 316 9845850106 317 9971471799 318 10098291771 319 10226317618 320 10355556960 321 10486017441 322 10617706729 323 10750632516 324 10884802518 325 11020224475 326 11156906151 327 11294855334 328 11434079836 329 11574587493 330 11716386165 331 11859483736 332 12003888114 333 12149607231 334 12296649043 335 12445021530 336 12594732696 337 12745790569 338 12898203201 339 13051978668 340 13207125070 341 13363650531 342 13521563199 343 13680871246 344 13841582868 345 14003706285 346 14167249741 347 14332221504 348 14498629866 349 14666483143 350 14835789675 351 15006557826 352 15178795984 353 15352512561 354 15527715993 355 15704414740 356 15882617286 357 16062332139 358 16243567831 359 16426332918 360 16610635980 361 16796485621 362 16983890469 363 17172859176 364 17363400418 365 17555522895 366 17749235331 367 17944546474 368 18141465096 369 18339999993 370 18540159985 371 18741953916 372 18945390654 373 19150479091 374 19357228143 375 19565646750 376 19775743876 377 19987528509 378 20201009661 379 20416196368 380 20633097690 381 20851722711 382 21072080539 383 21294180306 384 21518031168 385 21743642305 386 21971022921 387 22200182244 388 22431129526 389 22663874043 390 22898425095 391 23134792006 392 23372984124 393 23613010821 394 23854881493 395 24098605560 396 24344192466 397 24591651679 398 24840992691 399 25092225018 400 25345358200 401 25600401801 402 25857365409 403 26116258636 404 26377091118 405 26639872515 406 26904612511 407 27171320814 408 27440007156 409 27710681293 410 27983353005 411 28258032096 412 28534728394 413 28813451751 414 29094212043 415 29377019170 416 29661883056 417 29948813649 418 30237820921 419 30528914868 420 30822105510 421 31117402891 422 31414817079 423 31714358166 424 32016036268 425 32319861525 426 32625844101 427 32933994184 428 33244321986 429 33556837743 430 33871551715 431 34188474186 432 34507615464 433 34828985881 434 35152595793 435 35478455580 436 35806575646 437 36136966419 438 36469638351 439 36804601918 440 37141867620 441 37481445981 442 37823347549 443 38167582896 444 38514162618 445 38863097335 446 39214397691 447 39568074354 448 39924138016 449 40282599393 450 40643469225 451 41006758276 452 41372477334 453 41740637211 454 42111248743 455 42484322790 456 42859870236 457 43237901989 458 43618428981 459 44001462168 460 44387012530 461 44775091071 462 45165708819 463 45558876826 464 45954606168 465 46352907945 466 46753793281 467 47157273324 468 47563359246 469 47972062243 470 48383393535 471 48797364366 472 49213986004 473 49633269741 474 50055226893 475 50479868800 476 50907206826 477 51337252359 478 51770016811 479 52205511618 480 52643748240 481 53084738161 482 53528492889 483 53975023956 484 54424342918 485 54876461355 486 55331390871 487 55789143094 488 56249729676 489 56713162293 490 57179452645 491 57648612456 492 58120653474 493 58595587471 494 59073426243 495 59554181610 496 60037865416 497 60524489529 498 61014065841 499 61506606268 500 62002122750 501 62500627251 502 63002131759 503 63506648286 504 64014188868 505 64524765565 506 65038390461 507 65555075664 508 66074833306 509 66597675543 510 67123614555 511 67652662546 512 68184831744 513 68720134401 514 69258582793 515 69800189220 516 70344966006 517 70892925499 518 71444080071 519 71998442118 520 72556024060 521 73116838341 522 73680897429 523 74248213816 524 74818800018 525 75392668575 526 75969832051 527 76550303034 528 77134094136 529 77721217993 530 78311687265 531 78905514636 532 79502712814 533 80103294531 534 80707272543 535 81314659630 536 81925468596 537 82539712269 538 83157403501 539 83778555168 540 84403180170 541 85031291431 542 85662901899 543 86298024546 544 86936672368 545 87578858385 546 88224595641 547 88873897204 548 89526776166 549 90183245643 550 90843318775 551 91507008726 552 92174328684 553 92845291861 554 93519911493 555 94198200840 556 94880173186 557 95565841839 558 96255220131 559 96948321418 560 97645159080 561 98345746521 562 99050097169 563 99758224476 564 100470141918 565 101185862995 566 101905401231 567 102628770174 568 103355983396 569 104087054493 570 104821997085 571 105560824816 572 106303551354 573 107050190391 574 107800755643 575 108555260850 576 109313719776 577 110076146209 578 110842553961 579 111612956868 580 112387368790 581 113165803611 582 113948275239 583 114734797606 584 115525384668 585 116320050405 586 117118808821 587 117921673944 588 118728659826 589 119539780543 590 120355050195 591 121174482906 592 121998092824 593 122825894121 594 123657900993 595 124494127660 596 125334588366 597 126179297379 598 127028268991 599 127881517518 600 128739057300 601 129600902701 602 130467068109 603 131337567936 604 132212416618 605 133091628615 606 133975218411 607 134863200514 608 135755589456 609 136652399793 610 137553646105 611 138459342996 612 139369505094 613 140284147051 614 141203283543 615 142126929270 616 143055098956 617 143987807349 618 144925069221 619 145866899368 620 146813312610 621 147764323791 622 148719947779 623 149680199466 624 150645093768 625 151614645625 626 152588870001 627 153567781884 628 154551396286 629 155539728243 630 156532792815 631 157530605086 632 158533180164 633 159540533181 634 160552679293 635 161569633680 636 162591411546 637 163618028119 638 164649498651 639 165685838418 640 166727062720 641 167773186881 642 168824226249 643 169880196196 644 170941112118 645 172006989435 646 173077843591 647 174153690054 648 175234544316 649 176320421893 650 177411338325 651 178507309176 652 179608350034 653 180714476511 654 181825704243 655 182942048890 656 184063526136 657 185190151689 658 186321941281 659 187458910668 660 188601075630 661 189748451971 662 190901055519 663 192058902126 664 193222007668 665 194390388045 666 195564059181 667 196743037024 668 197927337546 669 199116976743 670 200311970635 671 201512335266 672 202718086704 673 203929241041 674 205145814393 675 206367822900 676 207595282726 677 208828210059 678 210066621111 679 211310532118 680 212559959340 681 213814919061 682 215075427589 683 216341501256 684 217613156418 685 218890409455 686 220173276771 687 221461774794 688 222755919976 689 224055728793 690 225361217745 691 226672403356 692 227989302174 693 229311930771 694 230640305743 695 231974443710 696 233314361316 697 234660075229 698 236011602141 699 237368958768 700 238732161850 701 240101228151 702 241476174459 703 242857017586 704 244243774368 705 245636461665 706 247035096361 707 248439695364 708 249850275606 709 251266854043 710 252689447655 711 254118073446 712 255552748444 713 256993489701 714 258440314293 715 259893239320 716 261352281906 717 262817459199 718 264288788371 719 265766286618 720 267249971160 721 268739859241 722 270235968129 723 271738315116 724 273246917518 725 274761792675 726 276282957951 727 277810430734 728 279344228436 729 280884368493 730 282430868365 731 283983745536 732 285543017514 733 287108701831 734 288680816043 735 290259377730 736 291844404496 737 293435913969 738 295033923801 739 296638451668 740 298249515270 741 299867132331 742 301491320599 743 303122097846 744 304759481868 745 306403490485 746 308054141541 747 309711452904 748 311375442466 749 313046128143 750 314723527875 751 316407659626 752 318098541384 753 319796191161 754 321500626993 755 323211866940 756 324929929086 757 326654831539 758 328386592431 759 330125229918 760 331870762180 761 333623207421 762 335382583869 763 337148909776 764 338922203418 765 340702483095 766 342489767131 767 344284073874 768 346085421696 769 347893828993 770 349709314185 771 351531895716 772 353361592054 773 355198421691 774 357042403143 775 358893554950 776 360751895676 777 362617443909 778 364490218261 779 366370237368 780 368257519890 781 370152084511 782 372053949939 783 373963134906 784 375879658168 785 377803538505 786 379734794721 787 381673445644 788 383619510126 789 385573007043 790 387533955295 791 389502373806 792 391478281524 793 393461697421 794 395452640493 795 397451129760 796 399457184266 797 401470823079 798 403492065291 799 405520930018 800 407557436400 801 409601603601 802 411653450809 803 413712997236 804 415780262118 805 417855264715 806 419938024311 807 422028560214 808 424126891756 809 426233038293 810 428347019205 811 430468853896 812 432598561794 813 434736162351 814 436881675043 815 439035119370 816 441196514856 817 443365881049 818 445543237521 819 447728603868 820 449921999710 821 452123444691 822 454332958479 823 456550560766 824 458776271268 825 461010109725 826 463252095901 827 465502249584 828 467760590586 829 470027138743 830 472301913915 831 474584935986 832 476876224864 833 479175800481 834 481483682793 835 483799891780 836 486124447446 837 488457369819 838 490798678951 839 493148394918 840 495506537820 841 497873127781 842 500248184949 843 502631729496 844 505023781618 845 507424361535 846 509833489491 847 512251185754 848 514677470616 849 517112364393 850 519555887425 851 522008060076 852 524468902734 853 526938435811 854 529416679743 855 531903654990 856 534399382036 857 536903881389 858 539417173581 859 541939279168 860 544470218730 861 547010012871 862 549558682219 863 552116247426 864 554682729168 865 557258148145 866 559842525081 867 562435880724 868 565038235846 869 567649611243 870 570270027735 871 572899506166 872 575538067404 873 578185732341 874 580842521893 875 583508457000 876 586183558626 877 588867847759 878 591561345411 879 594264072618 880 596976050440 881 599697299961 882 602427842289 883 605167698556 884 607916889918 885 610675437555 886 613443362671 887 616220686494 888 619007430276 889 621803615293 890 624609262845 891 627424394256 892 630249030874 893 633083194071 894 635926905243 895 638780185810 896 641643057216 897 644515540929 898 647397658441 899 650289431268 900 653190880950 901 656102029051 902 659022897159 903 661953506886 904 664893879868 905 667844037765 906 670804002261 907 673773795064 908 676753437906 909 679742952543 910 682742360755 911 685751684346 912 688770945144 913 691800165001 914 694839365793 915 697888569420 916 700947797806 917 704017072899 918 707096416671 919 710185851118 920 713285398260 921 716395080141 922 719514918829 923 722644936416 924 725785155018 925 728935596775 926 732096283851 927 735267238434 928 738448482736 929 741640038993 930 744841929465 931 748054176436 932 751276802214 933 754509829131 934 757753279543 935 761007175830 936 764271540396 937 767546395669 938 770831764101 939 774127668168 940 777434130370 941 780751173231 942 784078819299 943 787417091146 944 790766011368 945 794125602585 946 797495887441 947 800876888604 948 804268628766 949 807671130643 950 811084416975 951 814508510526 952 817943434084 953 821389210461 954 824845862493 955 828313413040 956 831791884986 957 835281301239 958 838781684731 959 842293058418 960 845815445280 961 849348868321 962 852893350569 963 856448915076 964 860015584918 965 863593383195 966 867182333031 967 870782457574 968 874393779996 969 878016323493 970 881650111285 971 885295166616 972 888951512754 973 892619172991 974 896298170643 975 899988529050 976 903690271576 977 907403421609 978 911128002561 979 914864037868 980 918611550990 981 922370565411 982 926141104639 983 929923192206 984 933716851668 985 937522106605 986 941338980621 987 945167497344 988 949007680426 989 952859553543 990 956723140395 991 960598464706 992 964485550224 993 968384420721 994 972295099993 995 976217611860 996 980151980166 997 984098228779 998 988056381591 999 992026462518 1000 996008495500