0 1 1 14 2 54 3 135 4 271 5 476 6 764 7 1149 8 1645 9 2266 10 3026 11 3939 12 5019 13 6280 14 7736 15 9401 16 11289 17 13414 18 15790 19 18431 20 21351 21 24564 22 28084 23 31925 24 36101 25 40626 26 45514 27 50779 28 56435 29 62496 30 68976 31 75889 32 83249 33 91070 34 99366 35 108151 36 117439 37 127244 38 137580 39 148461 40 159901 41 171914 42 184514 43 197715 44 211531 45 225976 46 241064 47 256809 48 273225 49 290326 50 308126 51 326639 52 345879 53 365860 54 386596 55 408101 56 430389 57 453474 58 477370 59 502091 60 527651 61 554064 62 581344 63 609505 64 638561 65 668526 66 699414 67 731239 68 764015 69 797756 70 832476 71 868189 72 904909 73 942650 74 981426 75 1021251 76 1062139 77 1104104 78 1147160 79 1191321 80 1236601 81 1283014 82 1330574 83 1379295 84 1429191 85 1480276 86 1532564 87 1586069 88 1640805 89 1696786 90 1754026 91 1812539 92 1872339 93 1933440 94 1995856 95 2059601 96 2124689 97 2191134 98 2258950 99 2328151 100 2398751 101 2470764 102 2544204 103 2619085 104 2695421 105 2773226 106 2852514 107 2933299 108 3015595 109 3099416 110 3184776 111 3271689 112 3360169 113 3450230 114 3541886 115 3635151 116 3730039 117 3826564 118 3924740 119 4024581 120 4126101 121 4229314 122 4334234 123 4440875 124 4549251 125 4659376 126 4771264 127 4884929 128 5000385 129 5117646 130 5236726 131 5357639 132 5480399 133 5605020 134 5731516 135 5859901 136 5990189 137 6122394 138 6256530 139 6392611 140 6530651 141 6670664 142 6812664 143 6956665 144 7102681 145 7250726 146 7400814 147 7552959 148 7707175 149 7863476 150 8021876 151 8182389 152 8345029 153 8509810 154 8676746 155 8845851 156 9017139 157 9190624 158 9366320 159 9544241 160 9724401 161 9906814 162 10091494 163 10278455 164 10467711 165 10659276 166 10853164 167 11049389 168 11247965 169 11448906 170 11652226 171 11857939 172 12066059 173 12276600 174 12489576 175 12705001 176 12922889 177 13143254 178 13366110 179 13591471 180 13819351 181 14049764 182 14282724 183 14518245 184 14756341 185 14997026 186 15240314 187 15486219 188 15734755 189 15985936 190 16239776 191 16496289 192 16755489 193 17017390 194 17282006 195 17549351 196 17819439 197 18092284 198 18367900 199 18646301 200 18927501 201 19211514 202 19498354 203 19788035 204 20080571 205 20375976 206 20674264 207 20975449 208 21279545 209 21586566 210 21896526 211 22209439 212 22525319 213 22844180 214 23166036 215 23490901 216 23818789 217 24149714 218 24483690 219 24820731 220 25160851 221 25504064 222 25850384 223 26199825 224 26552401 225 26908126 226 27267014 227 27629079 228 27994335 229 28362796 230 28734476 231 29109389 232 29487549 233 29868970 234 30253666 235 30641651 236 31032939 237 31427544 238 31825480 239 32226761 240 32631401 241 33039414 242 33450814 243 33865615 244 34283831 245 34705476 246 35130564 247 35559109 248 35991125 249 36426626 250 36865626 251 37308139 252 37754179 253 38203760 254 38656896 255 39113601 256 39573889 257 40037774 258 40505270 259 40976391 260 41451151 261 41929564 262 42411644 263 42897405 264 43386861 265 43880026 266 44376914 267 44877539 268 45381915 269 45890056 270 46401976 271 46917689 272 47437209 273 47960550 274 48487726 275 49018751 276 49553639 277 50092404 278 50635060 279 51181621 280 51732101 281 52286514 282 52844874 283 53407195 284 53973491 285 54543776 286 55118064 287 55696369 288 56278705 289 56865086 290 57455526 291 58050039 292 58648639 293 59251340 294 59858156 295 60469101 296 61084189 297 61703434 298 62326850 299 62954451 300 63586251 301 64222264 302 64862504 303 65506985 304 66155721 305 66808726 306 67466014 307 68127599 308 68793495 309 69463716 310 70138276 311 70817189 312 71500469 313 72188130 314 72880186 315 73576651 316 74277539 317 74982864 318 75692640 319 76406881 320 77125601 321 77848814 322 78576534 323 79308775 324 80045551 325 80786876 326 81532764 327 82283229 328 83038285 329 83797946 330 84562226 331 85331139 332 86104699 333 86882920 334 87665816 335 88453401 336 89245689 337 90042694 338 90844430 339 91650911 340 92462151 341 93278164 342 94098964 343 94924565 344 95754981 345 96590226 346 97430314 347 98275259 348 99125075 349 99979776 350 100839376 351 101703889 352 102573329 353 103447710 354 104327046 355 105211351 356 106100639 357 106994924 358 107894220 359 108798541 360 109707901 361 110622314 362 111541794 363 112466355 364 113396011 365 114330776 366 115270664 367 116215689 368 117165865 369 118121206 370 119081726 371 120047439 372 121018359 373 121994500 374 122975876 375 123962501 376 124954389 377 125951554 378 126954010 379 127961771 380 128974851 381 129993264 382 131017024 383 132046145 384 133080641 385 134120526 386 135165814 387 136216519 388 137272655 389 138334236 390 139401276 391 140473789 392 141551789 393 142635290 394 143724306 395 144818851 396 145918939 397 147024584 398 148135800 399 149252601 400 150375001 401 151503014 402 152636654 403 153775935 404 154920871 405 156071476 406 157227764 407 158389749 408 159557445 409 160730866 410 161910026 411 163094939 412 164285619 413 165482080 414 166684336 415 167892401 416 169106289 417 170326014 418 171551590 419 172783031 420 174020351 421 175263564 422 176512684 423 177767725 424 179028701 425 180295626 426 181568514 427 182847379 428 184132235 429 185423096 430 186719976 431 188022889 432 189331849 433 190646870 434 191967966 435 193295151 436 194628439 437 195967844 438 197313380 439 198665061 440 200022901 441 201386914 442 202757114 443 204133515 444 205516131 445 206904976 446 208300064 447 209701409 448 211109025 449 212522926 450 213943126 451 215369639 452 216802479 453 218241660 454 219687196 455 221139101 456 222597389 457 224062074 458 225533170 459 227010691 460 228494651 461 229985064 462 231481944 463 232985305 464 234495161 465 236011526 466 237534414 467 239063839 468 240599815 469 242142356 470 243691476 471 245247189 472 246809509 473 248378450 474 249954026 475 251536251 476 253125139 477 254720704 478 256322960 479 257931921 480 259547601 481 261170014 482 262799174 483 264435095 484 266077791 485 267727276 486 269383564 487 271046669 488 272716605 489 274393386 490 276077026 491 277767539 492 279464939 493 281169240 494 282880456 495 284598601 496 286323689 497 288055734 498 289794750 499 291540751 500 293293751 501 295053764 502 296820804 503 298594885 504 300376021 505 302164226 506 303959514 507 305761899 508 307571395 509 309388016 510 311211776 511 313042689 512 314880769 513 316726030 514 318578486 515 320438151 516 322305039 517 324179164 518 326060540 519 327949181 520 329845101 521 331748314 522 333658834 523 335576675 524 337501851 525 339434376 526 341374264 527 343321529 528 345276185 529 347238246 530 349207726 531 351184639 532 353168999 533 355160820 534 357160116 535 359166901 536 361181189 537 363202994 538 365232330 539 367269211 540 369313651 541 371365664 542 373425264 543 375492465 544 377567281 545 379649726 546 381739814 547 383837559 548 385942975 549 388056076 550 390176876 551 392305389 552 394441629 553 396585610 554 398737346 555 400896851 556 403064139 557 405239224 558 407422120 559 409612841 560 411811401 561 414017814 562 416232094 563 418454255 564 420684311 565 422922276 566 425168164 567 427421989 568 429683765 569 431953506 570 434231226 571 436516939 572 438810659 573 441112400 574 443422176 575 445740001 576 448065889 577 450399854 578 452741910 579 455092071 580 457450351 581 459816764 582 462191324 583 464574045 584 466964941 585 469364026 586 471771314 587 474186819 588 476610555 589 479042536 590 481482776 591 483931289 592 486388089 593 488853190 594 491326606 595 493808351 596 496298439 597 498796884 598 501303700 599 503818901 600 506342501 601 508874514 602 511414954 603 513963835 604 516521171 605 519086976 606 521661264 607 524244049 608 526835345 609 529435166 610 532043526 611 534660439 612 537285919 613 539919980 614 542562636 615 545213901 616 547873789 617 550542314 618 553219490 619 555905331 620 558599851 621 561303064 622 564014984 623 566735625 624 569465001 625 572203126 626 574950014 627 577705679 628 580470135 629 583243396 630 586025476 631 588816389 632 591616149 633 594424770 634 597242266 635 600068651 636 602903939 637 605748144 638 608601280 639 611463361 640 614334401 641 617214414 642 620103414 643 623001415 644 625908431 645 628824476 646 631749564 647 634683709 648 637626925 649 640579226 650 643540626 651 646511139 652 649490779 653 652479560 654 655477496 655 658484601 656 661500889 657 664526374 658 667561070 659 670604991 660 673658151 661 676720564 662 679792244 663 682873205 664 685963461 665 689063026 666 692171914 667 695290139 668 698417715 669 701554656 670 704700976 671 707856689 672 711021809 673 714196350 674 717380326 675 720573751 676 723776639 677 726989004 678 730210860 679 733442221 680 736683101 681 739933514 682 743193474 683 746462995 684 749742091 685 753030776 686 756329064 687 759636969 688 762954505 689 766281686 690 769618526 691 772965039 692 776321239 693 779687140 694 783062756 695 786448101 696 789843189 697 793248034 698 796662650 699 800087051 700 803521251 701 806965264 702 810419104 703 813882785 704 817356321 705 820839726 706 824333014 707 827836199 708 831349295 709 834872316 710 838405276 711 841948189 712 845501069 713 849063930 714 852636786 715 856219651 716 859812539 717 863415464 718 867028440 719 870651481 720 874284601 721 877927814 722 881581134 723 885244575 724 888918151 725 892601876 726 896295764 727 899999829 728 903714085 729 907438546 730 911173226 731 914918139 732 918673299 733 922438720 734 926214416 735 930000401 736 933796689 737 937603294 738 941420230 739 945247511 740 949085151 741 952933164 742 956791564 743 960660365 744 964539581 745 968429226 746 972329314 747 976239859 748 980160875 749 984092376 750 988034376 751 991986889 752 995949929 753 999923510 754 1003907646 755 1007902351 756 1011907639 757 1015923524 758 1019950020 759 1023987141 760 1028034901 761 1032093314 762 1036162394 763 1040242155 764 1044332611 765 1048433776 766 1052545664 767 1056668289 768 1060801665 769 1064945806 770 1069100726 771 1073266439 772 1077442959 773 1081630300 774 1085828476 775 1090037501 776 1094257389 777 1098488154 778 1102729810 779 1106982371 780 1111245851 781 1115520264 782 1119805624 783 1124101945 784 1128409241 785 1132727526 786 1137056814 787 1141397119 788 1145748455 789 1150110836 790 1154484276 791 1158868789 792 1163264389 793 1167671090 794 1172088906 795 1176517851 796 1180957939 797 1185409184 798 1189871600 799 1194345201 800 1198830001 801 1203326014 802 1207833254 803 1212351735 804 1216881471 805 1221422476 806 1225974764 807 1230538349 808 1235113245 809 1239699466 810 1244297026 811 1248905939 812 1253526219 813 1258157880 814 1262800936 815 1267455401 816 1272121289 817 1276798614 818 1281487390 819 1286187631 820 1290899351 821 1295622564 822 1300357284 823 1305103525 824 1309861301 825 1314630626 826 1319411514 827 1324203979 828 1329008035 829 1333823696 830 1338650976 831 1343489889 832 1348340449 833 1353202670 834 1358076566 835 1362962151 836 1367859439 837 1372768444 838 1377689180 839 1382621661 840 1387565901 841 1392521914 842 1397489714 843 1402469315 844 1407460731 845 1412463976 846 1417479064 847 1422506009 848 1427544825 849 1432595526 850 1437658126 851 1442732639 852 1447819079 853 1452917460 854 1458027796 855 1463150101 856 1468284389 857 1473430674 858 1478588970 859 1483759291 860 1488941651 861 1494136064 862 1499342544 863 1504561105 864 1509791761 865 1515034526 866 1520289414 867 1525556439 868 1530835615 869 1536126956 870 1541430476 871 1546746189 872 1552074109 873 1557414250 874 1562766626 875 1568131251 876 1573508139 877 1578897304 878 1584298760 879 1589712521 880 1595138601 881 1600577014 882 1606027774 883 1611490895 884 1616966391 885 1622454276 886 1627954564 887 1633467269 888 1638992405 889 1644529986 890 1650080026 891 1655642539 892 1661217539 893 1666805040 894 1672405056 895 1678017601 896 1683642689 897 1689280334 898 1694930550 899 1700593351 900 1706268751 901 1711956764 902 1717657404 903 1723370685 904 1729096621 905 1734835226 906 1740586514 907 1746350499 908 1752127195 909 1757916616 910 1763718776 911 1769533689 912 1775361369 913 1781201830 914 1787055086 915 1792921151 916 1798800039 917 1804691764 918 1810596340 919 1816513781 920 1822444101 921 1828387314 922 1834343434 923 1840312475 924 1846294451 925 1852289376 926 1858297264 927 1864318129 928 1870351985 929 1876398846 930 1882458726 931 1888531639 932 1894617599 933 1900716620 934 1906828716 935 1912953901 936 1919092189 937 1925243594 938 1931408130 939 1937585811 940 1943776651 941 1949980664 942 1956197864 943 1962428265 944 1968671881 945 1974928726 946 1981198814 947 1987482159 948 1993778775 949 2000088676 950 2006411876 951 2012748389 952 2019098229 953 2025461410 954 2031837946 955 2038227851 956 2044631139 957 2051047824 958 2057477920 959 2063921441 960 2070378401 961 2076848814 962 2083332694 963 2089830055 964 2096340911 965 2102865276 966 2109403164 967 2115954589 968 2122519565 969 2129098106 970 2135690226 971 2142295939 972 2148915259 973 2155548200 974 2162194776 975 2168855001 976 2175528889 977 2182216454 978 2188917710 979 2195632671 980 2202361351 981 2209103764 982 2215859924 983 2222629845 984 2229413541 985 2236211026 986 2243022314 987 2249847419 988 2256686355 989 2263539136 990 2270405776 991 2277286289 992 2284180689 993 2291088990 994 2298011206 995 2304947351 996 2311897439 997 2318861484 998 2325839500 999 2332831501 1000 2339837501