0 0 1 4 2 35 3 117 4 274 5 530 6 909 7 1435 8 2132 9 3024 10 4135 11 5489 12 7110 13 9022 14 11249 15 13815 16 16744 17 20060 18 23787 19 27949 20 32570 21 37674 22 43285 23 49427 24 56124 25 63400 26 71279 27 79785 28 88942 29 98774 30 109305 31 120559 32 132560 33 145332 34 158899 35 173285 36 188514 37 204610 38 221597 39 239499 40 258340 41 278144 42 298935 43 320737 44 343574 45 367470 46 392449 47 418535 48 445752 49 474124 50 503675 51 534429 52 566410 53 599642 54 634149 55 669955 56 707084 57 745560 58 785407 59 826649 60 869310 61 913414 62 958985 63 1006047 64 1054624 65 1104740 66 1156419 67 1209685 68 1264562 69 1321074 70 1379245 71 1439099 72 1500660 73 1563952 74 1628999 75 1695825 76 1764454 77 1834910 78 1907217 79 1981399 80 2057480 81 2135484 82 2215435 83 2297357 84 2381274 85 2467210 86 2555189 87 2645235 88 2737372 89 2831624 90 2928015 91 3026569 92 3127310 93 3230262 94 3335449 95 3442895 96 3552624 97 3664660 98 3779027 99 3895749 100 4014850 101 4136354 102 4260285 103 4386667 104 4515524 105 4646880 106 4780759 107 4917185 108 5056182 109 5197774 110 5341985 111 5488839 112 5638360 113 5790572 114 5945499 115 6103165 116 6263594 117 6426810 118 6592837 119 6761699 120 6933420 121 7108024 122 7285535 123 7465977 124 7649374 125 7835750 126 8025129 127 8217535 128 8412992 129 8611524 130 8813155 131 9017909 132 9225810 133 9436882 134 9651149 135 9868635 136 10089364 137 10313360 138 10540647 139 10771249 140 11005190 141 11242494 142 11483185 143 11727287 144 11974824 145 12225820 146 12480299 147 12738285 148 12999802 149 13264874 150 13533525 151 13805779 152 14081660 153 14361192 154 14644399 155 14931305 156 15221934 157 15516310 158 15814457 159 16116399 160 16422160 161 16731764 162 17045235 163 17362597 164 17683874 165 18009090 166 18338269 167 18671435 168 19008612 169 19349824 170 19695095 171 20044449 172 20397910 173 20755502 174 21117249 175 21483175 176 21853304 177 22227660 178 22606267 179 22989149 180 23376330 181 23767834 182 24163685 183 24563907 184 24968524 185 25377560 186 25791039 187 26208985 188 26631422 189 27058374 190 27489865 191 27925919 192 28366560 193 28811812 194 29261699 195 29716245 196 30175474 197 30639410 198 31108077 199 31581499 200 32059700 201 32542704 202 33030535 203 33523217 204 34020774 205 34523230 206 35030609 207 35542935 208 36060232 209 36582524 210 37109835 211 37642189 212 38179610 213 38722122 214 39269749 215 39822515 216 40380444 217 40943560 218 41511887 219 42085449 220 42664270 221 43248374 222 43837785 223 44432527 224 45032624 225 45638100 226 46248979 227 46865285 228 47487042 229 48114274 230 48747005 231 49385259 232 50029060 233 50678432 234 51333399 235 51993985 236 52660214 237 53332110 238 54009697 239 54692999 240 55382040 241 56076844 242 56777435 243 57483837 244 58196074 245 58914170 246 59638149 247 60368035 248 61103852 249 61845624 250 62593375 251 63347129 252 64106910 253 64872742 254 65644649 255 66422655 256 67206784 257 67997060 258 68793507 259 69596149 260 70405010 261 71220114 262 72041485 263 72869147 264 73703124 265 74543440 266 75390119 267 76243185 268 77102662 269 77968574 270 78840945 271 79719799 272 80605160 273 81497052 274 82395499 275 83300525 276 84212154 277 85130410 278 86055317 279 86986899 280 87925180 281 88870184 282 89821935 283 90780457 284 91745774 285 92717910 286 93696889 287 94682735 288 95675472 289 96675124 290 97681715 291 98695269 292 99715810 293 100743362 294 101777949 295 102819595 296 103868324 297 104924160 298 105987127 299 107057249 300 108134550 301 109219054 302 110310785 303 111409767 304 112516024 305 113629580 306 114750459 307 115878685 308 117014282 309 118157274 310 119307685 311 120465539 312 121630860 313 122803672 314 123983999 315 125171865 316 126367294 317 127570310 318 128780937 319 129999199 320 131225120 321 132458724 322 133700035 323 134949077 324 136205874 325 137470450 326 138742829 327 140023035 328 141311092 329 142607024 330 143910855 331 145222609 332 146542310 333 147869982 334 149205649 335 150549335 336 151901064 337 153260860 338 154628747 339 156004749 340 157388890 341 158781194 342 160181685 343 161590387 344 163007324 345 164432520 346 165865999 347 167307785 348 168757902 349 170216374 350 171683225 351 173158479 352 174642160 353 176134292 354 177634899 355 179144005 356 180661634 357 182187810 358 183722557 359 185265899 360 186817860 361 188378464 362 189947735 363 191525697 364 193112374 365 194707790 366 196311969 367 197924935 368 199546712 369 201177324 370 202816795 371 204465149 372 206122410 373 207788602 374 209463749 375 211147875 376 212841004 377 214543160 378 216254367 379 217974649 380 219704030 381 221442534 382 223190185 383 224947007 384 226713024 385 228488260 386 230272739 387 232066485 388 233869522 389 235681874 390 237503565 391 239334619 392 241175060 393 243024912 394 244884199 395 246752945 396 248631174 397 250518910 398 252416177 399 254322999 400 256239400 401 258165404 402 260101035 403 262046317 404 264001274 405 265965930 406 267940309 407 269924435 408 271918332 409 273922024 410 275935535 411 277958889 412 279992110 413 282035222 414 284088249 415 286151215 416 288224144 417 290307060 418 292399987 419 294502949 420 296615970 421 298739074 422 300872285 423 303015627 424 305169124 425 307332800 426 309506679 427 311690785 428 313885142 429 316089774 430 318304705 431 320529959 432 322765560 433 325011532 434 327267899 435 329534685 436 331811914 437 334099610 438 336397797 439 338706499 440 341025740 441 343355544 442 345695935 443 348046937 444 350408574 445 352780870 446 355163849 447 357557535 448 359961952 449 362377124 450 364803075 451 367239829 452 369687410 453 372145842 454 374615149 455 377095355 456 379586484 457 382088560 458 384601607 459 387125649 460 389660710 461 392206814 462 394763985 463 397332247 464 399911624 465 402502140 466 405103819 467 407716685 468 410340762 469 412976074 470 415622645 471 418280499 472 420949660 473 423630152 474 426321999 475 429025225 476 431739854 477 434465910 478 437203417 479 439952399 480 442712880 481 445484884 482 448268435 483 451063557 484 453870274 485 456688610 486 459518589 487 462360235 488 465213572 489 468078624 490 470955415 491 473843969 492 476744310 493 479656462 494 482580449 495 485516295 496 488464024 497 491423660 498 494395227 499 497378749 500 500374250 501 503381754 502 506401285 503 509432867 504 512476524 505 515532280 506 518600159 507 521680185 508 524772382 509 527876774 510 530993385 511 534122239 512 537263360 513 540416772 514 543582499 515 546760565 516 549950994 517 553153810 518 556369037 519 559596699 520 562836820 521 566089424 522 569354535 523 572632177 524 575922374 525 579225150 526 582540529 527 585868535 528 589209192 529 592562524 530 595928555 531 599307309 532 602698810 533 606103082 534 609520149 535 612950035 536 616392764 537 619848360 538 623316847 539 626798249 540 630292590 541 633799894 542 637320185 543 640853487 544 644399824 545 647959220 546 651531699 547 655117285 548 658716002 549 662327874 550 665952925 551 669591179 552 673242660 553 676907392 554 680585399 555 684276705 556 687981334 557 691699310 558 695430657 559 699175399 560 702933560 561 706705164 562 710490235 563 714288797 564 718100874 565 721926490 566 725765669 567 729618435 568 733484812 569 737364824 570 741258495 571 745165849 572 749086910 573 753021702 574 756970249 575 760932575 576 764908704 577 768898660 578 772902467 579 776920149 580 780951730 581 784997234 582 789056685 583 793130107 584 797217524 585 801318960 586 805434439 587 809563985 588 813707622 589 817865374 590 822037265 591 826223319 592 830423560 593 834638012 594 838866699 595 843109645 596 847366874 597 851638410 598 855924277 599 860224499 600 864539100 601 868868104 602 873211535 603 877569417 604 881941774 605 886328630 606 890730009 607 895145935 608 899576432 609 904021524 610 908481235 611 912955589 612 917444610 613 921948322 614 926466749 615 930999915 616 935547844 617 940110560 618 944688087 619 949280449 620 953887670 621 958509774 622 963146785 623 967798727 624 972465624 625 977147500 626 981844379 627 986556285 628 991283242 629 996025274 630 1000782405 631 1005554659 632 1010342060 633 1015144632 634 1019962399 635 1024795385 636 1029643614 637 1034507110 638 1039385897 639 1044279999 640 1049189440 641 1054114244 642 1059054435 643 1064010037 644 1068981074 645 1073967570 646 1078969549 647 1083987035 648 1089020052 649 1094068624 650 1099132775 651 1104212529 652 1109307910 653 1114418942 654 1119545649 655 1124688055 656 1129846184 657 1135020060 658 1140209707 659 1145415149 660 1150636410 661 1155873514 662 1161126485 663 1166395347 664 1171680124 665 1176980840 666 1182297519 667 1187630185 668 1192978862 669 1198343574 670 1203724345 671 1209121199 672 1214534160 673 1219963252 674 1225408499 675 1230869925 676 1236347554 677 1241841410 678 1247351517 679 1252877899 680 1258420580 681 1263979584 682 1269554935 683 1275146657 684 1280754774 685 1286379310 686 1292020289 687 1297677735 688 1303351672 689 1309042124 690 1314749115 691 1320472669 692 1326212810 693 1331969562 694 1337742949 695 1343532995 696 1349339724 697 1355163160 698 1361003327 699 1366860249 700 1372733950 701 1378624454 702 1384531785 703 1390455967 704 1396397024 705 1402354980 706 1408329859 707 1414321685 708 1420330482 709 1426356274 710 1432399085 711 1438458939 712 1444535860 713 1450629872 714 1456740999 715 1462869265 716 1469014694 717 1475177310 718 1481357137 719 1487554199 720 1493768520 721 1500000124 722 1506249035 723 1512515277 724 1518798874 725 1525099850 726 1531418229 727 1537754035 728 1544107292 729 1550478024 730 1556866255 731 1563272009 732 1569695310 733 1576136182 734 1582594649 735 1589070735 736 1595564464 737 1602075860 738 1608604947 739 1615151749 740 1621716290 741 1628298594 742 1634898685 743 1641516587 744 1648152324 745 1654805920 746 1661477399 747 1668166785 748 1674874102 749 1681599374 750 1688342625 751 1695103879 752 1701883160 753 1708680492 754 1715495899 755 1722329405 756 1729181034 757 1736050810 758 1742938757 759 1749844899 760 1756769260 761 1763711864 762 1770672735 763 1777651897 764 1784649374 765 1791665190 766 1798699369 767 1805751935 768 1812822912 769 1819912324 770 1827020195 771 1834146549 772 1841291410 773 1848454802 774 1855636749 775 1862837275 776 1870056404 777 1877294160 778 1884550567 779 1891825649 780 1899119430 781 1906431934 782 1913763185 783 1921113207 784 1928482024 785 1935869660 786 1943276139 787 1950701485 788 1958145722 789 1965608874 790 1973090965 791 1980592019 792 1988112060 793 1995651112 794 2003209199 795 2010786345 796 2018382574 797 2025997910 798 2033632377 799 2041285999 800 2048958800 801 2056650804 802 2064362035 803 2072092517 804 2079842274 805 2087611330 806 2095399709 807 2103207435 808 2111034532 809 2118881024 810 2126746935 811 2134632289 812 2142537110 813 2150461422 814 2158405249 815 2166368615 816 2174351544 817 2182354060 818 2190376187 819 2198417949 820 2206479370 821 2214560474 822 2222661285 823 2230781827 824 2238922124 825 2247082200 826 2255262079 827 2263461785 828 2271681342 829 2279920774 830 2288180105 831 2296459359 832 2304758560 833 2313077732 834 2321416899 835 2329776085 836 2338155314 837 2346554610 838 2354973997 839 2363413499 840 2371873140 841 2380352944 842 2388852935 843 2397373137 844 2405913574 845 2414474270 846 2423055249 847 2431656535 848 2440278152 849 2448920124 850 2457582475 851 2466265229 852 2474968410 853 2483692042 854 2492436149 855 2501200755 856 2509985884 857 2518791560 858 2527617807 859 2536464649 860 2545332110 861 2554220214 862 2563128985 863 2572058447 864 2581008624 865 2589979540 866 2598971219 867 2607983685 868 2617016962 869 2626071074 870 2635146045 871 2644241899 872 2653358660 873 2662496352 874 2671654999 875 2680834625 876 2690035254 877 2699256910 878 2708499617 879 2717763399 880 2727048280 881 2736354284 882 2745681435 883 2755029757 884 2764399274 885 2773790010 886 2783201989 887 2792635235 888 2802089772 889 2811565624 890 2821062815 891 2830581369 892 2840121310 893 2849682662 894 2859265449 895 2868869695 896 2878495424 897 2888142660 898 2897811427 899 2907501749 900 2917213650 901 2926947154 902 2936702285 903 2946479067 904 2956277524 905 2966097680 906 2975939559 907 2985803185 908 2995688582 909 3005595774 910 3015524785 911 3025475639 912 3035448360 913 3045442972 914 3055459499 915 3065497965 916 3075558394 917 3085640810 918 3095745237 919 3105871699 920 3116020220 921 3126190824 922 3136383535 923 3146598377 924 3156835374 925 3167094550 926 3177375929 927 3187679535 928 3198005392 929 3208353524 930 3218723955 931 3229116709 932 3239531810 933 3249969282 934 3260429149 935 3270911435 936 3281416164 937 3291943360 938 3302493047 939 3313065249 940 3323659990 941 3334277294 942 3344917185 943 3355579687 944 3366264824 945 3376972620 946 3387703099 947 3398456285 948 3409232202 949 3420030874 950 3430852325 951 3441696579 952 3452563660 953 3463453592 954 3474366399 955 3485302105 956 3496260734 957 3507242310 958 3518246857 959 3529274399 960 3540324960 961 3551398564 962 3562495235 963 3573614997 964 3584757874 965 3595923890 966 3607113069 967 3618325435 968 3629561012 969 3640819824 970 3652101895 971 3663407249 972 3674735910 973 3686087902 974 3697463249 975 3708861975 976 3720284104 977 3731729660 978 3743198667 979 3754691149 980 3766207130 981 3777746634 982 3789309685 983 3800896307 984 3812506524 985 3824140360 986 3835797839 987 3847478985 988 3859183822 989 3870912374 990 3882664665 991 3894440719 992 3906240560 993 3918064212 994 3929911699 995 3941783045 996 3953678274 997 3965597410 998 3977540477 999 3989507499 1000 4001498500