0 1 1 8 2 29 3 74 4 153 5 275 6 450 7 687 8 996 9 1387 10 1869 11 2452 12 3145 13 3958 14 4901 15 5983 16 7214 17 8603 18 10160 19 11895 20 13817 21 15936 22 18261 23 20802 24 23569 25 26571 26 29818 27 33319 28 37084 29 41123 30 45445 31 50060 32 54977 33 60206 34 65757 35 71639 36 77862 37 84435 38 91368 39 98671 40 106353 41 114424 42 122893 43 131770 44 141065 45 150787 46 160946 47 171551 48 182612 49 194139 50 206141 51 218628 52 231609 53 245094 54 259093 55 273615 56 288670 57 304267 58 320416 59 337127 60 354409 61 372272 62 390725 63 409778 64 429441 65 449723 66 470634 67 492183 68 514380 69 537235 70 560757 71 584956 72 609841 73 635422 74 661709 75 688711 76 716438 77 744899 78 774104 79 804063 80 834785 81 866280 82 898557 83 931626 84 965497 85 1000179 86 1035682 87 1072015 88 1109188 89 1147211 90 1186093 91 1225844 92 1266473 93 1307990 94 1350405 95 1393727 96 1437966 97 1483131 98 1529232 99 1576279 100 1624281 101 1673248 102 1723189 103 1774114 104 1826033 105 1878955 106 1932890 107 1987847 108 2043836 109 2100867 110 2158949 111 2218092 112 2278305 113 2339598 114 2401981 115 2465463 116 2530054 117 2595763 118 2662600 119 2730575 120 2799697 121 2869976 122 2941421 123 3014042 124 3087849 125 3162851 126 3239058 127 3316479 128 3395124 129 3475003 130 3556125 131 3638500 132 3722137 133 3807046 134 3893237 135 3980719 136 4069502 137 4159595 138 4251008 139 4343751 140 4437833 141 4533264 142 4630053 143 4728210 144 4827745 145 4928667 146 5030986 147 5134711 148 5239852 149 5346419 150 5454421 151 5563868 152 5674769 153 5787134 154 5900973 155 6016295 156 6133110 157 6251427 158 6371256 159 6492607 160 6615489 161 6739912 162 6865885 163 6993418 164 7122521 165 7253203 166 7385474 167 7519343 168 7654820 169 7791915 170 7930637 171 8070996 172 8213001 173 8356662 174 8501989 175 8648991 176 8797678 177 8948059 178 9100144 179 9253943 180 9409465 181 9566720 182 9725717 183 9886466 184 10048977 185 10213259 186 10379322 187 10547175 188 10716828 189 10888291 190 11061573 191 11236684 192 11413633 193 11592430 194 11773085 195 11955607 196 12140006 197 12326291 198 12514472 199 12704559 200 12896561 201 13090488 202 13286349 203 13484154 204 13683913 205 13885635 206 14089330 207 14295007 208 14502676 209 14712347 210 14924029 211 15137732 212 15353465 213 15571238 214 15791061 215 16012943 216 16236894 217 16462923 218 16691040 219 16921255 220 17153577 221 17388016 222 17624581 223 17863282 224 18104129 225 18347131 226 18592298 227 18839639 228 19089164 229 19340883 230 19594805 231 19850940 232 20109297 233 20369886 234 20632717 235 20897799 236 21165142 237 21434755 238 21706648 239 21980831 240 22257313 241 22536104 242 22817213 243 23100650 244 23386425 245 23674547 246 23965026 247 24257871 248 24553092 249 24850699 250 25150701 251 25453108 252 25757929 253 26065174 254 26374853 255 26686975 256 27001550 257 27318587 258 27638096 259 27960087 260 28284569 261 28611552 262 28941045 263 29273058 264 29607601 265 29944683 266 30284314 267 30626503 268 30971260 269 31318595 270 31668517 271 32021036 272 32376161 273 32733902 274 33094269 275 33457271 276 33822918 277 34191219 278 34562184 279 34935823 280 35312145 281 35691160 282 36072877 283 36457306 284 36844457 285 37234339 286 37626962 287 38022335 288 38420468 289 38821371 290 39225053 291 39631524 292 40040793 293 40452870 294 40867765 295 41285487 296 41706046 297 42129451 298 42555712 299 42984839 300 43416841 301 43851728 302 44289509 303 44730194 304 45173793 305 45620315 306 46069770 307 46522167 308 46977516 309 47435827 310 47897109 311 48361372 312 48828625 313 49298878 314 49772141 315 50248423 316 50727734 317 51210083 318 51695480 319 52183935 320 52675457 321 53170056 322 53667741 323 54168522 324 54672409 325 55179411 326 55689538 327 56202799 328 56719204 329 57238763 330 57761485 331 58287380 332 58816457 333 59348726 334 59884197 335 60422879 336 60964782 337 61509915 338 62058288 339 62609911 340 63164793 341 63722944 342 64284373 343 64849090 344 65417105 345 65988427 346 66563066 347 67141031 348 67722332 349 68306979 350 68894981 351 69486348 352 70081089 353 70679214 354 71280733 355 71885655 356 72493990 357 73105747 358 73720936 359 74339567 360 74961649 361 75587192 362 76216205 363 76848698 364 77484681 365 78124163 366 78767154 367 79413663 368 80063700 369 80717275 370 81374397 371 82035076 372 82699321 373 83367142 374 84038549 375 84713551 376 85392158 377 86074379 378 86760224 379 87449703 380 88142825 381 88839600 382 89540037 383 90244146 384 90951937 385 91663419 386 92378602 387 93097495 388 93820108 389 94546451 390 95276533 391 96010364 392 96747953 393 97489310 394 98234445 395 98983367 396 99736086 397 100492611 398 101252952 399 102017119 400 102785121 401 103556968 402 104332669 403 105112234 404 105895673 405 106682995 406 107474210 407 108269327 408 109068356 409 109871307 410 110678189 411 111489012 412 112303785 413 113122518 414 113945221 415 114771903 416 115602574 417 116437243 418 117275920 419 118118615 420 118965337 421 119816096 422 120670901 423 121529762 424 122392689 425 123259691 426 124130778 427 125005959 428 125885244 429 126768643 430 127656165 431 128547820 432 129443617 433 130343566 434 131247677 435 132155959 436 133068422 437 133985075 438 134905928 439 135830991 440 136760273 441 137693784 442 138631533 443 139573530 444 140519785 445 141470307 446 142425106 447 143384191 448 144347572 449 145315259 450 146287261 451 147263588 452 148244249 453 149229254 454 150218613 455 151212335 456 152210430 457 153212907 458 154219776 459 155231047 460 156246729 461 157266832 462 158291365 463 159320338 464 160353761 465 161391643 466 162433994 467 163480823 468 164532140 469 165587955 470 166648277 471 167713116 472 168782481 473 169856382 474 170934829 475 172017831 476 173105398 477 174197539 478 175294264 479 176395583 480 177501505 481 178612040 482 179727197 483 180846986 484 181971417 485 183100499 486 184234242 487 185372655 488 186515748 489 187663531 490 188816013 491 189973204 492 191135113 493 192301750 494 193473125 495 194649247 496 195830126 497 197015771 498 198206192 499 199401399 500 200601401 501 201806208 502 203015829 503 204230274 504 205449553 505 206673675 506 207902650 507 209136487 508 210375196 509 211618787 510 212867269 511 214120652 512 215378945 513 216642158 514 217910301 515 219183383 516 220461414 517 221744403 518 223032360 519 224325295 520 225623217 521 226926136 522 228234061 523 229547002 524 230864969 525 232187971 526 233516018 527 234849119 528 236187284 529 237530523 530 238878845 531 240232260 532 241590777 533 242954406 534 244323157 535 245697039 536 247076062 537 248460235 538 249849568 539 251244071 540 252643753 541 254048624 542 255458693 543 256873970 544 258294465 545 259720187 546 261151146 547 262587351 548 264028812 549 265475539 550 266927541 551 268384828 552 269847409 553 271315294 554 272788493 555 274267015 556 275750870 557 277240067 558 278734616 559 280234527 560 281739809 561 283250472 562 284766525 563 286287978 564 287814841 565 289347123 566 290884834 567 292427983 568 293976580 569 295530635 570 297090157 571 298655156 572 300225641 573 301801622 574 303383109 575 304970111 576 306562638 577 308160699 578 309764304 579 311373463 580 312988185 581 314608480 582 316234357 583 317865826 584 319502897 585 321145579 586 322793882 587 324447815 588 326107388 589 327772611 590 329443493 591 331120044 592 332802273 593 334490190 594 336183805 595 337883127 596 339588166 597 341298931 598 343015432 599 344737679 600 346465681 601 348199448 602 349938989 603 351684314 604 353435433 605 355192355 606 356955090 607 358723647 608 360498036 609 362278267 610 364064349 611 365856292 612 367654105 613 369457798 614 371267381 615 373082863 616 374904254 617 376731563 618 378564800 619 380403975 620 382249097 621 384100176 622 385957221 623 387820242 624 389689249 625 391564251 626 393445258 627 395332279 628 397225324 629 399124403 630 401029525 631 402940700 632 404857937 633 406781246 634 408710637 635 410646119 636 412587702 637 414535395 638 416489208 639 418449151 640 420415233 641 422387464 642 424365853 643 426350410 644 428341145 645 430338067 646 432341186 647 434350511 648 436366052 649 438387819 650 440415821 651 442450068 652 444490569 653 446537334 654 448590373 655 450649695 656 452715310 657 454787227 658 456865456 659 458950007 660 461040889 661 463138112 662 465241685 663 467351618 664 469467921 665 471590603 666 473719674 667 475855143 668 477997020 669 480145315 670 482300037 671 484461196 672 486628801 673 488802862 674 490983389 675 493170391 676 495363878 677 497563859 678 499770344 679 501983343 680 504202865 681 506428920 682 508661517 683 510900666 684 513146377 685 515398659 686 517657522 687 519922975 688 522195028 689 524473691 690 526758973 691 529050884 692 531349433 693 533654630 694 535966485 695 538285007 696 540610206 697 542942091 698 545280672 699 547625959 700 549977961 701 552336688 702 554702149 703 557074354 704 559453313 705 561839035 706 564231530 707 566630807 708 569036876 709 571449747 710 573869429 711 576295932 712 578729265 713 581169438 714 583616461 715 586070343 716 588531094 717 590998723 718 593473240 719 595954655 720 598442977 721 600938216 722 603440381 723 605949482 724 608465529 725 610988531 726 613518498 727 616055439 728 618599364 729 621150283 730 623708205 731 626273140 732 628845097 733 631424086 734 634010117 735 636603199 736 639203342 737 641810555 738 644424848 739 647046231 740 649674713 741 652310304 742 654953013 743 657602850 744 660259825 745 662923947 746 665595226 747 668273671 748 670959292 749 673652099 750 676352101 751 679059308 752 681773729 753 684495374 754 687224253 755 689960375 756 692703750 757 695454387 758 698212296 759 700977487 760 703749969 761 706529752 762 709316845 763 712111258 764 714913001 765 717722083 766 720538514 767 723362303 768 726193460 769 729031995 770 731877917 771 734731236 772 737591961 773 740460102 774 743335669 775 746218671 776 749109118 777 752007019 778 754912384 779 757825223 780 760745545 781 763673360 782 766608677 783 769551506 784 772501857 785 775459739 786 778425162 787 781398135 788 784378668 789 787366771 790 790362453 791 793365724 792 796376593 793 799395070 794 802421165 795 805454887 796 808496246 797 811545251 798 814601912 799 817666239 800 820738241 801 823817928 802 826905309 803 830000394 804 833103193 805 836213715 806 839331970 807 842457967 808 845591716 809 848733227 810 851882509 811 855039572 812 858204425 813 861377078 814 864557541 815 867745823 816 870941934 817 874145883 818 877357680 819 880577335 820 883804857 821 887040256 822 890283541 823 893534722 824 896793809 825 900060811 826 903335738 827 906618599 828 909909404 829 913208163 830 916514885 831 919829580 832 923152257 833 926482926 834 929821597 835 933168279 836 936522982 837 939885715 838 943256488 839 946635311 840 950022193 841 953417144 842 956820173 843 960231290 844 963650505 845 967077827 846 970513266 847 973956831 848 977408532 849 980868379 850 984336381 851 987812548 852 991296889 853 994789414 854 998290133 855 1001799055 856 1005316190 857 1008841547 858 1012375136 859 1015916967 860 1019467049 861 1023025392 862 1026592005 863 1030166898 864 1033750081 865 1037341563 866 1040941354 867 1044549463 868 1048165900 869 1051790675 870 1055423797 871 1059065276 872 1062715121 873 1066373342 874 1070039949 875 1073714951 876 1077398358 877 1081090179 878 1084790424 879 1088499103 880 1092216225 881 1095941800 882 1099675837 883 1103418346 884 1107169337 885 1110928819 886 1114696802 887 1118473295 888 1122258308 889 1126051851 890 1129853933 891 1133664564 892 1137483753 893 1141311510 894 1145147845 895 1148992767 896 1152846286 897 1156708411 898 1160579152 899 1164458519 900 1168346521 901 1172243168 902 1176148469 903 1180062434 904 1183985073 905 1187916395 906 1191856410 907 1195805127 908 1199762556 909 1203728707 910 1207703589 911 1211687212 912 1215679585 913 1219680718 914 1223690621 915 1227709303 916 1231736774 917 1235773043 918 1239818120 919 1243872015 920 1247934737 921 1252006296 922 1256086701 923 1260175962 924 1264274089 925 1268381091 926 1272496978 927 1276621759 928 1280755444 929 1284898043 930 1289049565 931 1293210020 932 1297379417 933 1301557766 934 1305745077 935 1309941359 936 1314146622 937 1318360875 938 1322584128 939 1326816391 940 1331057673 941 1335307984 942 1339567333 943 1343835730 944 1348113185 945 1352399707 946 1356695306 947 1360999991 948 1365313772 949 1369636659 950 1373968661 951 1378309788 952 1382660049 953 1387019454 954 1391388013 955 1395765735 956 1400152630 957 1404548707 958 1408953976 959 1413368447 960 1417792129 961 1422225032 962 1426667165 963 1431118538 964 1435579161 965 1440049043 966 1444528194 967 1449016623 968 1453514340 969 1458021355 970 1462537677 971 1467063316 972 1471598281 973 1476142582 974 1480696229 975 1485259231 976 1489831598 977 1494413339 978 1499004464 979 1503604983 980 1508214905 981 1512834240 982 1517462997 983 1522101186 984 1526748817 985 1531405899 986 1536072442 987 1540748455 988 1545433948 989 1550128931 990 1554833413 991 1559547404 992 1564270913 993 1569003950 994 1573746525 995 1578498647 996 1583260326 997 1588031571 998 1592812392 999 1597602799 1000 1602402801