0 1 1 3 2 9 3 28 4 66 5 126 6 226 7 396 8 651 9 1001 10 1491 11 2184 12 3108 13 4284 14 5796 15 7752 16 10197 17 13167 18 16797 19 21252 20 26598 21 32890 22 40326 23 49140 24 59423 25 71253 26 84903 27 100688 28 118728 29 139128 30 162248 31 188496 32 218025 33 250971 34 287793 35 329004 36 374794 37 425334 38 481194 39 543004 40 610995 41 685377 42 766843 43 856152 44 953580 45 1059380 46 1174380 47 1299480 48 1435005 49 1581255 50 1739205 51 1909908 52 2093742 53 2291058 54 2502990 55 2730756 56 2974791 57 3235501 58 3514191 59 3812256 60 4130192 61 4468464 62 4828560 63 5212064 64 5619537 65 6051507 66 6509657 67 6995772 68 7510482 69 8054382 70 8629362 71 9237420 72 9879259 73 10555545 74 11268387 75 12020008 76 12811188 77 13642668 78 14516788 79 15436008 80 16401189 81 17413151 82 18474477 83 19587876 84 20754294 85 21974634 86 23251734 87 24588564 88 25986159 89 27445509 90 28969719 91 30562032 92 32223576 93 33955432 94 35760984 95 37643760 96 39604985 97 41645835 98 43769985 99 45981260 100 48280986 101 50670438 102 53153594 103 55734588 104 58414851 105 61195761 106 64081611 107 67076856 108 70183036 109 73401636 110 76737276 111 80194744 112 83775693 113 87481719 114 91317781 115 95289012 116 99397182 117 103644002 118 108034782 119 112575012 120 117266583 121 122111325 122 127114911 123 132283200 124 137618208 125 143121888 126 148800288 127 154659648 128 160702113 129 166929763 130 173349033 131 179966556 132 186784610 133 193805406 134 201035778 135 208482764 136 216148779 137 224036169 138 232152179 139 240504264 140 249094980 141 257926812 142 267007428 143 276344712 144 285941365 145 295800015 146 305928765 147 316335940 148 327024390 149 337996890 150 349261990 151 360828468 152 372699327 153 384877493 154 397371975 155 410192016 156 423340776 157 436821336 158 450643176 159 464816016 160 479343177 161 494227899 162 509480145 163 525110124 164 541121322 165 557517142 166 574308042 167 591504732 168 609110867 169 627130017 170 645573147 171 664451480 172 683768844 173 703528980 174 723743372 175 744423768 176 765574173 177 787198503 178 809308773 179 831917268 180 855028174 181 878645586 182 902782062 183 927450436 184 952655079 185 978400269 186 1004699119 187 1031565024 188 1059002544 189 1087016144 190 1115619504 191 1144826592 192 1174642161 193 1205070867 194 1236126969 195 1267825020 196 1300169970 197 1333166670 198 1366829970 199 1401175020 200 1436206971 201 1471930873 202 1508362179 203 1545516648 204 1583399636 205 1622016396 206 1661382996 207 1701515816 208 1742420421 209 1784102271 210 1826578061 211 1869864804 212 1913968278 213 1958894154 214 2004659766 215 2051282772 216 2098769167 217 2147124837 218 2196367767 219 2246516272 220 2297576568 221 2349554760 222 2402469496 223 2456339760 224 2511171993 225 2566972523 226 2623760673 227 2681556108 228 2740365498 229 2800195398 230 2861065818 231 2922997116 232 2985996195 233 3050069841 234 3115238763 235 3181524024 236 3248932764 237 3317472004 238 3387163164 239 3458028024 240 3530073965 241 3603308247 242 3677753013 243 3753430772 244 3830349150 245 3908515650 246 3987953150 247 4068684900 248 4150718775 249 4234062525 250 4318739775 251 4404774528 252 4492174912 253 4580948928 254 4671120960 255 4762715776 256 4855741761 257 4950207171 258 5046137161 259 5143557276 260 5242476162 261 5342902334 262 5444861730 263 5548380684 264 5653468107 265 5760132777 266 5868401427 267 5978301192 268 6089841252 269 6203030652 270 6317896932 271 6434468040 272 6552753429 273 6672762415 274 6794523357 275 6918065028 276 7043397158 277 7170529338 278 7299490758 279 7430311028 280 7563000159 281 7697568021 282 7834044647 283 7972460496 284 8112825864 285 8255150904 286 8399466504 287 8545803984 288 8694173929 289 8844586779 290 8997074289 291 9151668652 292 9308380746 293 9467221302 294 9628222954 295 9791418780 296 9956819955 297 10124437505 298 10294304955 299 10466456280 300 10640902956 301 10817656308 302 10996750764 303 11178221208 304 11362079421 305 11548337031 306 11737029381 307 11928192276 308 12121837806 309 12317977906 310 12516648846 311 12717887364 312 12921705863 313 13128116589 314 13337156751 315 13548864032 316 13763251152 317 13980330672 318 14200140752 319 14422720032 320 14648081553 321 14876238195 322 15107229081 323 15341093820 324 15577845778 325 15817498158 326 16060091058 327 16305665068 328 16554233883 329 16805811033 330 17060437603 331 17318155176 332 17578977780 333 17842919276 334 18110021748 335 18380327784 336 18653851749 337 18930607839 338 19210639149 339 19493989284 340 19780672950 341 20070704682 342 20364128598 343 20660989332 344 20961301935 345 21265081285 346 21572372535 347 21883221360 348 22197643160 349 22515653160 350 22837297560 351 23162623088 352 23491645497 353 23824380363 354 24160874945 355 24501177036 356 24845302746 357 25193268006 358 25545121146 359 25900911036 360 26260654147 361 26624366769 362 26992098315 363 27363898744 364 27739784892 365 28119773412 366 28503914812 367 28892260152 368 29284826637 369 29681631287 370 30082725717 371 30488162100 372 30897958014 373 31312130850 374 31730733342 375 32153818788 376 32581405143 377 33013510173 378 33450187743 379 33891492288 380 34337442144 381 34788055456 382 35243387232 383 35703493056 384 36168391649 385 36638101539 386 37112678889 387 37592180444 388 38076625314 389 38566032414 390 39060459074 391 39559963212 392 40064564331 393 40574281737 394 41089173939 395 41609300040 396 42134679940 397 42665333340 398 43201319940 399 43742700040 400 44289493941 401 44841721743 402 45399444349 403 45962723268 404 46531579206 405 47106032666 406 47686145766 407 48271981236 408 48863560191 409 49460903541 410 50064074631 411 50673137424 412 51288113448 413 51909024024 414 52535933736 415 53168907792 416 53807968137 417 54453136507 418 55104478737 419 55762061292 420 56425906538 421 57096036630 422 57772518666 423 58455420380 424 59144764563 425 59840573793 426 60542916443 427 61251861528 428 61967432268 429 62689651668 430 63418589388 431 64154315736 432 64896854365 433 65646228711 434 66402509733 435 67165769044 436 67936030734 437 68713318674 438 69497705134 439 70289263044 440 71088016935 441 71893991117 442 72707259183 443 73527895392 444 74355924720 445 75191371920 446 76034311920 447 76884820320 448 77742922545 449 78608643795 450 79482060345 451 80363249148 452 81252236082 453 82149046798 454 83053758930 455 83966450796 456 84887148731 457 85815878841 458 86752720131 459 87697752296 460 88651002132 461 89612496204 462 90582314900 463 91560539304 464 92547196677 465 93542314047 466 94545973197 467 95558256612 468 96579192022 469 97608806922 470 98647184502 471 99694408660 472 100750507599 473 101815509285 474 102889498327 475 103972560048 476 105064723128 477 106166016008 478 107276524728 479 108396336048 480 109525479129 481 110663982891 482 111811934817 483 112969423116 484 114136477434 485 115313127174 486 116499461274 487 117695569404 488 118901481699 489 120117228049 490 121342898859 491 122578585272 492 123824317916 493 125080127172 494 126346104924 495 127622343800 496 128908874925 497 130205729175 498 131512999925 499 132830781300 500 134159104926 501 135498002178 502 136847567934 503 138207897828 504 139579023991 505 140960978301 506 142353857151 507 143757757696 508 145172712576 509 146598754176 510 148035980416 511 149484489984 512 150944316033 513 152415491459 514 153898115721 515 155392289052 516 156898045122 517 158415417342 518 159944506722 519 161485415052 520 163038176523 521 164602825065 522 166179463251 523 167768194440 524 169369053348 525 170982074428 526 172607361828 527 174245020488 528 175895085653 529 177557592303 530 179232646173 531 180920353796 532 182620750950 533 184333873146 534 186059827718 535 187798722804 536 189550594719 537 191315479509 538 193093486119 539 194884724304 540 196689230920 541 198507042552 542 200338269768 543 202183023952 544 204041342505 545 205913262555 546 207798896305 547 209698356780 548 211611681930 549 213538909430 550 215480153130 551 217435527708 552 219405071667 553 221388823233 554 223386897915 555 225399412056 556 227426404716 557 229467914676 558 231524059116 559 233594956056 560 235680645117 561 237781165639 562 239896636485 563 242027177364 564 244172828462 565 246333629682 566 248509701582 567 250701165572 568 252908062407 569 255130432557 570 257368398287 571 259622082720 572 261891527184 573 264176772720 574 266477943312 575 268795163808 576 271128476113 577 273477921843 578 275843626713 579 278225717308 580 280624236114 581 283039225326 582 285470812402 583 287919125676 584 290384208219 585 292866102809 586 295364938659 587 297880845864 588 300413868084 589 302964048684 590 305531518644 591 308116409832 592 310718766501 593 313338632607 594 315976140909 595 318631425060 596 321304529910 597 323995500010 598 326704469910 599 329431575060 600 332176860911 601 334940372613 602 337722246519 603 340522619888 604 343341538776 605 346179048936 606 349035288536 607 351910396656 608 354804419961 609 357717404811 610 360649491201 611 363600820044 612 366571438618 613 369561393894 614 372570827706 615 375599882812 616 378648607107 617 381717048177 618 384805349707 619 387913656312 620 391042016508 621 394190478500 622 397359187836 623 400548291000 624 403757837133 625 406987875063 626 410238552213 627 413510016948 628 416802319038 629 420115507938 630 423449732958 631 426805144356 632 430181792535 633 433579727581 634 436999100703 635 440440064064 636 443902668704 637 447386965344 638 450893107104 639 454421248064 640 457971439905 641 461543733987 642 465138285353 643 468755250012 644 472394680290 645 476056628190 646 479741250690 647 483448705740 648 487179046315 649 490932325065 650 494708700915 651 498508333768 652 502331277252 653 506177584668 654 510047416900 655 513940935816 656 517858195701 657 521799250511 658 525764263101 659 529753397316 660 533766708102 661 537804250074 662 541866188070 663 545952687924 664 550063805247 665 554199595317 666 558360224967 667 562545862032 668 566756562792 669 570992383192 670 575253492072 671 579540059280 672 583852141769 673 588189796155 674 592553193297 675 596942505068 676 601357789098 677 605799102678 678 610266618698 679 614760511068 680 619280838099 681 623827657761 682 628401144987 683 633001475736 684 637628709004 685 642282903444 686 646964236044 687 651672884824 688 656408909469 689 661172369319 690 665963443429 691 670782311892 692 675629035086 693 680503673042 694 685406406894 695 690337418820 696 695296769895 697 700284520845 698 705300854895 699 710345956320 700 715419886896 701 720522708048 702 725654605104 703 730815764448 704 736006248561 705 741226119571 706 746475564921 707 751754773116 708 757063807346 709 762402730446 710 767771731986 711 773171002604 712 778600606203 713 784060606329 714 789551194691 715 795072564072 716 800624779092 717 806207904012 718 811822132692 719 817467660072 720 823144551493 721 828852871935 722 834592817421 723 840364585060 724 846168240918 725 852003850698 726 857871612598 727 863771725908 728 869704257423 729 875669273573 730 881666974743 731 887697562416 732 893761104120 733 899857667016 734 905987453688 735 912150667824 736 918347377689 737 924577651179 738 930841693089 739 937139709324 740 943471768890 741 949837940422 742 956238430938 743 962673448572 744 969143063075 745 975647343825 746 982186500075 747 988760742200 748 995370140700 749 1002014765700 750 1008694828700 751 1015410542328 752 1022161977837 753 1028949206103 754 1035772440885 755 1042631897076 756 1049527646686 757 1056459761346 758 1063428457086 759 1070433951076 760 1077476316087 761 1084555624509 762 1091672094655 763 1098825945984 764 1106017252032 765 1113246085952 766 1120512668352 767 1127817220992 768 1135159818177 769 1142540533827 770 1149959590857 771 1157417213340 772 1164913476354 773 1172448454590 774 1180022373282 775 1187635458828 776 1195287787083 777 1202979433513 778 1210710625683 779 1218481592328 780 1226292410084 781 1234143155196 782 1242034057572 783 1249965348296 784 1257937104789 785 1265949404079 786 1274002478429 787 1282096561284 788 1290231730854 789 1298408064954 790 1306625798214 791 1314885166452 792 1323186248671 793 1331529123477 794 1339914027879 795 1348341200080 796 1356810719880 797 1365322666680 798 1373877279880 799 1382474800080 800 1391115307881 801 1399798883483 802 1408525768689 803 1417296206508 804 1426110278346 805 1434968065206 806 1443869811306 807 1452815762076 808 1461805999731 809 1470840606081 810 1479919827771 811 1489043912664 812 1498212943788 813 1507427003764 814 1516686341676 815 1525991207832 816 1535341686077 817 1544737859847 818 1554179980677 819 1563668301332 820 1573202906478 821 1582783880370 822 1592411477006 823 1602085951620 824 1611807389703 825 1621575876333 826 1631391667983 827 1641255022368 828 1651166025808 829 1661124764208 830 1671131496528 831 1681186482976 832 1691289810705 833 1701441566451 834 1711642011673 835 1721891409084 836 1732189846674 837 1742537412014 838 1752934369074 839 1763380983084 840 1773877342875 841 1784423536857 842 1795019831523 843 1805666494632 844 1816363615860 845 1827111284460 846 1837909769460 847 1848759341160 848 1859660090085 849 1870612106335 850 1881615661485 851 1892671028388 852 1903778298422 853 1914937562538 854 1926149094870 855 1937413170836 856 1948729882671 857 1960099322181 858 1971521766071 859 1982997492336 860 1994526594072 861 2006109163944 862 2017745481240 863 2029435826544 864 2041180293817 865 2052978976587 866 2064832156737 867 2076740117452 868 2088702953562 869 2100720759462 870 2112793819642 871 2124922419900 872 2137106655939 873 2149346623025 874 2161642608267 875 2173994900088 876 2186403595068 877 2198868789348 878 2211390772668 879 2223969836088 880 2236606077069 881 2249299592631 882 2262050675157 883 2274859618356 884 2287726520574 885 2300651479714 886 2313634790814 887 2326676750244 888 2339777457239 889 2352937010589 890 2366155707999 891 2379433848512 892 2392771532256 893 2406168858912 894 2419626128864 895 2433143643840 896 2446721504865 897 2460359812515 898 2474058869865 899 2487818981340 900 2501640248866 901 2515522773918 902 2529466862274 903 2543472821068 904 2557540753131 905 2571670760841 906 2585863152691 907 2600118238536 908 2614436122116 909 2628816906716 910 2643260903556 911 2657768425224 912 2672339576373 913 2686974461199 914 2701673393661 915 2716436689092 916 2731264453062 917 2746156790682 918 2761114018662 919 2776136455092 920 2791224206463 921 2806377378805 922 2821596291591 923 2836881265680 924 2852232408488 925 2867649826968 926 2883133843368 927 2898684781328 928 2914302749193 929 2929987854843 930 2945740423313 931 2961560781036 932 2977449037290 933 2993405300886 934 3009429899658 935 3025523162844 936 3041685200659 937 3057916122849 938 3074216260059 939 3090585944344 940 3107025286860 941 3123534398292 942 3140113612108 943 3156763263192 944 3173483463645 945 3190274325095 946 3207136183845 947 3224069377620 948 3241074019470 949 3258150221970 950 3275298324270 951 3292518666948 952 3309811364007 953 3327176528973 954 3344614503855 955 3362125632096 956 3379710028656 957 3397367808016 958 3415099315056 959 3432904896096 960 3450784667057 961 3468738743379 962 3486767472825 963 3504871204604 964 3523050055602 965 3541304142222 966 3559633815122 967 3578039426412 968 3596521093947 969 3615078935097 970 3633713303427 971 3652424553960 972 3671212805524 973 3690078176460 974 3709021023252 975 3728041703848 976 3747140338053 977 3766317045183 978 3785572184653 979 3804906117348 980 3824318964054 981 3843810845066 982 3863382122742 983 3883033160916 984 3902764081359 985 3922575005349 986 3942466298199 987 3962438326704 988 3982491213624 989 4002625081224 990 4022840297784 991 4043137233072 992 4063516010841 993 4083976754347 994 4104519834849 995 4125145625100 996 4145854249850 997 4166645833350 998 4187520749850 999 4208479375100 1000 4229521834851