0 0 1 4 2 32 3 108 4 250 5 492 6 854 7 1360 8 2021 9 2885 10 3965 11 5285 12 6849 13 8719 14 10901 15 13419 16 16270 17 19530 18 23198 19 27298 20 31820 21 36854 22 42392 23 48458 24 55035 25 62227 26 70019 27 78435 28 87451 29 97185 30 107615 31 118765 32 130604 33 143264 34 156716 35 170984 36 186030 37 202000 38 218858 39 236628 40 255265 41 274929 42 295577 43 317233 44 339845 45 363587 46 388409 47 414335 48 441306 49 469510 50 498890 51 529470 52 561184 53 594234 54 628556 55 664174 56 701015 57 739295 58 778943 59 819983 60 862335 61 906229 62 951587 63 998433 64 1046680 65 1096572 66 1148024 67 1201060 68 1255586 69 1311860 70 1369790 71 1429400 72 1490589 73 1553629 74 1618421 75 1684989 76 1753225 77 1823415 78 1895453 79 1969363 80 2045030 81 2122754 82 2202422 83 2284058 84 2367540 85 2453182 86 2540864 87 2630610 88 2722291 89 2816235 90 2912315 91 3010555 92 3110819 93 3213449 94 3318311 95 3425429 96 3534660 97 3646360 98 3760388 99 3876768 100 3995350 101 4116504 102 4240082 103 4366108 104 4494425 105 4625417 106 4758929 107 4894985 108 5033421 109 5174635 110 5318465 111 5464935 112 5613874 113 5765694 114 5920226 115 6077494 116 6237320 117 6400130 118 6565748 119 6734198 120 6905295 121 7079479 122 7256567 123 7436583 124 7619335 125 7805277 126 7994219 127 8186185 128 8380976 129 8579060 130 8780240 131 8984540 132 9191754 133 9402364 134 9616166 135 9833184 136 10053205 137 10276725 138 10503533 139 10733653 140 10966865 141 11203679 142 11443877 143 11687483 144 11934270 145 12184762 146 12438734 147 12696210 148 12956956 149 13221510 150 13489640 151 13761370 152 14036459 153 14315459 154 14598131 155 14884499 156 15174315 157 15468145 158 15765743 159 16067133 160 16372060 161 16681104 162 16994012 163 17310808 164 17631230 165 17955872 166 18284474 167 18617060 168 18953361 169 19293985 170 19638665 171 19987425 172 20339989 173 20696979 174 21058121 175 21423439 176 21792650 177 22166390 178 22544378 179 22926638 180 23312880 181 23703754 182 24098972 183 24498558 184 24902215 185 25310607 186 25723439 187 26140735 188 26562191 189 26988485 190 27419315 191 27854705 192 28294344 193 28738924 194 29188136 195 29642004 196 30100210 197 30563460 198 31031438 199 31504168 200 31981325 201 32463629 202 32950757 203 33442733 204 33939225 205 34440967 206 34947629 207 35459235 208 35975446 209 36497010 210 37023590 211 37555210 212 38091524 213 38633294 214 39180176 215 39732194 216 40288995 217 40851355 218 41418923 219 41991723 220 42569395 221 43152729 222 43741367 223 44335333 224 44934260 225 45538952 226 46149044 227 46764560 228 47385126 229 48011560 230 48643490 231 49280940 232 49923529 233 50572089 234 51226241 235 51886009 236 52551005 237 53222075 238 53898833 239 54581303 240 55269090 241 55963054 242 56662802 243 57368358 244 58079320 245 58796562 246 59519684 247 60248710 248 60983231 249 61724135 250 62471015 251 63223895 252 63982359 253 64747309 254 65518331 255 66295449 256 67078240 257 67867620 258 68663168 259 69464908 260 70272410 261 71086604 262 71907062 263 72733808 264 73566405 265 74405797 266 75251549 267 76103685 268 76961761 269 77826735 270 78698165 271 79576075 272 80460014 273 81350954 274 82248446 275 83152514 276 84062700 277 84979990 278 85903928 279 86834538 280 87771355 281 88715379 282 89666147 283 90623683 284 91587515 285 92558657 286 93536639 287 94521485 288 95512716 289 96511360 290 97516940 291 98529480 292 99548494 293 100575024 294 101608586 295 102649204 296 103696385 297 104751185 298 105813113 299 106882193 300 107957925 301 109041379 302 110132057 303 111229983 304 112334650 305 113447142 306 114566954 307 115694110 308 116828096 309 117970010 310 119119340 311 120276110 312 121439799 313 122611519 314 123790751 315 124977519 316 126171295 317 127373205 318 128582723 319 129799873 320 131024120 321 132256604 322 133496792 323 134744708 324 135999810 325 137263252 326 138534494 327 139813560 328 141099901 329 142394685 330 143697365 331 145007965 332 146325929 333 147652439 334 148986941 335 150329459 336 151679430 337 153038050 338 154404758 339 155779578 340 157161940 341 158553054 342 159952352 343 161359858 344 162774995 345 164198987 346 165631259 347 167071835 348 168520131 349 169977385 350 171443015 351 172917045 352 174398884 353 175889784 354 177389156 355 178897024 356 180412790 357 181937720 358 183471218 359 185013308 360 186563385 361 188122729 362 189690737 363 191267433 364 192852205 365 194446347 366 196049249 367 197660935 368 199280786 369 200910110 370 202548290 371 204195350 372 205850664 373 207515554 374 209189396 375 210872214 376 212563375 377 214264215 378 215974103 379 217693063 380 219420455 381 221157629 382 222903947 383 224659433 384 226423440 385 228197332 386 229980464 387 231772860 388 233573866 389 235384860 390 237205190 391 239034880 392 240873269 393 242721749 394 244579661 395 246447029 396 248323185 397 250209535 398 252105413 399 254010843 400 255925150 401 257849754 402 259783982 403 261727858 404 263680700 405 265643942 406 267616904 407 269599610 408 271591371 409 273593635 410 275605715 411 277627635 412 279658699 413 281700369 414 283751951 415 285813469 416 287884220 417 289965680 418 292057148 419 294158648 420 296269470 421 298391104 422 300522842 423 302664708 424 304815985 425 306978177 426 309150569 427 311333185 428 313525301 429 315728435 430 317941865 431 320165615 432 322398954 433 324643414 434 326898266 435 329163534 436 331438480 437 333724650 438 336021308 439 338328478 440 340645415 441 342973679 442 345312527 443 347661983 444 350021295 445 352392037 446 354773459 447 357165585 448 359567656 449 361981260 450 364405640 451 366840820 452 369286034 453 371742884 454 374210606 455 376689224 456 379177965 457 381678445 458 384189893 459 386712333 460 389244985 461 391789479 462 394345037 463 396911683 464 399488630 465 402077522 466 404677574 467 407288810 468 409910436 469 412544110 470 415189040 471 417845250 472 420511939 473 423190779 474 425880971 475 428582539 476 431294675 477 434019065 478 436754903 479 439502213 480 442260180 481 445030504 482 447812372 483 450605808 484 453409990 485 456226632 486 459054914 487 461894860 488 464745641 489 467608985 490 470484065 491 473370905 492 476268669 493 479179099 494 482101361 495 485035479 496 487980610 497 490938510 498 493908338 499 496890118 500 499883000 501 502888754 502 505906532 503 508936358 504 511977375 505 515031367 506 518097479 507 521175735 508 524265271 509 527367885 510 530482715 511 533609785 512 536748224 513 539899844 514 543063776 515 546240044 516 549427770 517 552628780 518 555842198 519 559068048 520 562305445 521 565556229 522 568819517 523 572095333 524 575382785 525 578683727 526 581997269 527 585323435 528 588661326 529 592012810 530 595376990 531 598753890 532 602142604 533 605545014 534 608960216 535 612388234 536 615828155 537 619281875 538 622748483 539 626228003 540 629719515 541 633224929 542 636743327 543 640274733 544 643818220 545 647375712 546 650946284 547 654529960 548 658125806 549 661735760 550 665358890 551 668995220 552 672643809 553 676306609 554 679982681 555 683672049 556 687373765 557 691089795 558 694819193 559 698561983 560 702317210 561 706086854 562 709869962 563 713666558 564 717475680 565 721299322 566 725136524 567 728987310 568 732850711 569 736728735 570 740620415 571 744525775 572 748443839 573 752376629 574 756323171 575 760283489 576 764256600 577 768244540 578 772246328 579 776261988 580 780290530 581 784334004 582 788391422 583 792462808 584 796547165 585 800646557 586 804759989 587 808887485 588 813028041 589 817183735 590 821353565 591 825537555 592 829734694 593 833947074 594 838173686 595 842414554 596 846668660 597 850938110 598 855221888 599 859520018 600 863831475 601 868158379 602 872499707 603 876855483 604 881224675 605 885609417 606 890008679 607 894422485 608 898849796 609 903292760 610 907750340 611 912222560 612 916708374 613 921209944 614 925726226 615 930257244 616 934801945 617 939362505 618 943937873 619 948528073 620 953132045 621 957751979 622 962386817 623 967036583 624 971700210 625 976379902 626 981074594 627 985784310 628 990507976 629 995247810 630 1000002740 631 1004772790 632 1009556879 633 1014357239 634 1019172791 635 1024003559 636 1028848455 637 1033709725 638 1038586283 639 1043478153 640 1048384240 641 1053306804 642 1058244752 643 1063198108 644 1068165770 645 1073150012 646 1078149734 647 1083164960 648 1088194581 649 1093240885 650 1098302765 651 1103380245 652 1108472209 653 1113580959 654 1118705381 655 1123845499 656 1129000190 657 1134171770 658 1139359118 659 1144562258 660 1149780060 661 1155014854 662 1160265512 663 1165532058 664 1170813355 665 1176111747 666 1181426099 667 1186756435 668 1192101611 669 1197463985 670 1202842415 671 1208236925 672 1213646364 673 1219073104 674 1224515996 675 1229975064 676 1235449150 677 1240940640 678 1246448378 679 1251972388 680 1257511505 681 1263068129 682 1268641097 683 1274230433 684 1279834965 685 1285457107 686 1291095689 687 1296750735 688 1302421066 689 1308109110 690 1313813690 691 1319534830 692 1325271344 693 1331025674 694 1336796636 695 1342584254 696 1348387335 697 1354208335 698 1360046063 699 1365900543 700 1371770575 701 1377658629 702 1383563507 703 1389485233 704 1395422600 705 1401378092 706 1407350504 707 1413339860 708 1419344946 709 1425368260 710 1431408590 711 1437465960 712 1443539149 713 1449630669 714 1455739301 715 1461865069 716 1468006745 717 1474166855 718 1480344173 719 1486538723 720 1492749270 721 1498978354 722 1505224742 723 1511488458 724 1517768260 725 1524066702 726 1530382544 727 1536715810 728 1543065251 729 1549433435 730 1555819115 731 1562222315 732 1568641779 733 1575080089 734 1581535991 735 1588009509 736 1594499380 737 1601008200 738 1607534708 739 1614078928 740 1620639590 741 1627219304 742 1633816802 743 1640432108 744 1647063945 745 1653714937 746 1660383809 747 1667070585 748 1673773981 749 1680496635 750 1687237265 751 1693995895 752 1700771234 753 1707565934 754 1714378706 755 1721209574 756 1728057240 757 1734924370 758 1741809668 759 1748713158 760 1755633535 761 1762573479 762 1769531687 763 1776508183 764 1783501655 765 1790514797 766 1797546299 767 1804596185 768 1811663136 769 1818749860 770 1825855040 771 1832978700 772 1840119514 773 1847280204 774 1854459446 775 1861657264 776 1868872325 777 1876107365 778 1883361053 779 1890633413 780 1897923105 781 1905232879 782 1912561397 783 1919908683 784 1927273390 785 1934658282 786 1942062014 787 1949484610 788 1956924716 789 1964385110 790 1971864440 791 1979362730 792 1986878619 793 1994414899 794 2001970211 795 2009544579 796 2017136635 797 2024749185 798 2032380863 799 2040031693 800 2047700300 801 2055389504 802 2063097932 803 2070825608 804 2078571150 805 2086337392 806 2094122954 807 2101927860 808 2109750721 809 2117594385 810 2125457465 811 2133339985 812 2141240549 813 2149162019 814 2157103001 815 2165063519 816 2173042170 817 2181041830 818 2189061098 819 2197099998 820 2205157120 821 2213235354 822 2221333292 823 2229450958 824 2237586935 825 2245744127 826 2253921119 827 2262117935 828 2270333151 829 2278569685 830 2286826115 831 2295102465 832 2303397304 833 2311713564 834 2320049816 835 2328406084 836 2336780930 837 2345177300 838 2353593758 839 2362030328 840 2370485565 841 2378962429 842 2387459477 843 2395976733 844 2404512745 845 2413070487 846 2421648509 847 2430246835 848 2438864006 849 2447503010 850 2456162390 851 2464842170 852 2473540884 853 2482261534 854 2491002656 855 2499764274 856 2508544915 857 2517347595 858 2526170843 859 2535014683 860 2543877635 861 2552762729 862 2561668487 863 2570594933 864 2579540580 865 2588508472 866 2597497124 867 2606506560 868 2615535286 869 2624586360 870 2633658290 871 2642751100 872 2651863289 873 2660997929 874 2670153521 875 2679330089 876 2688526125 877 2697744715 878 2706984353 879 2716245063 880 2725525330 881 2734828254 882 2744152322 883 2753497558 884 2762862440 885 2772250082 886 2781658964 887 2791089110 888 2800538991 889 2810011735 890 2819505815 891 2829021255 892 2838556519 893 2848114749 894 2857694411 895 2867295529 896 2876916560 897 2886560660 898 2896226288 899 2905913468 900 2915620650 901 2925351004 902 2935102982 903 2944876608 904 2954670325 905 2964487317 906 2974326029 907 2984186485 908 2994067121 909 3003971135 910 3013896965 911 3023844635 912 3033812574 913 3043803994 914 3053817326 915 3063852594 916 3073908220 917 3083987430 918 3094088648 919 3104211898 920 3114355595 921 3124522979 922 3134712467 923 3144924083 924 3155156235 925 3165412177 926 3175690319 927 3185990685 928 3196311676 929 3206656560 930 3217023740 931 3227413240 932 3237823454 933 3248257664 934 3258714266 935 3269193284 936 3279693105 937 3290217025 938 3300763433 939 3311332353 940 3321922165 941 3332536179 942 3343172777 943 3353831983 944 3364512170 945 3375216662 946 3385943834 947 3396693710 948 3407464656 949 3418260010 950 3429078140 951 3439919070 952 3450781159 953 3461667759 954 3472577231 955 3483509599 956 3494463215 957 3505441445 958 3516442643 959 3527466833 960 3538512360 961 3549582604 962 3560675912 963 3571792308 964 3582930130 965 3594092772 966 3605278574 967 3616487560 968 3627718061 969 3638973485 970 3650252165 971 3661554125 972 3672877689 973 3684226279 974 3695598221 975 3706993539 976 3718410550 977 3729852690 978 3741318278 979 3752807338 980 3764318180 981 3775854254 982 3787413872 983 3798997058 984 3810602115 985 3822232507 986 3833886539 987 3845564235 988 3857263891 989 3868988985 990 3880737815 991 3892510405 992 3904305044 993 3916125224 994 3927969236 995 3939837104 996 3951727110 997 3963642760 998 3975582338 999 3987545868 1000 3999531625