0 1 1 4 2 12 3 26 4 43 5 64 6 99 7 133 8 161 9 210 10 274 11 318 12 364 13 441 14 528 15 593 16 649 17 746 18 877 19 953 20 1003 21 1145 22 1314 23 1383 24 1450 25 1629 26 1822 27 1911 28 1979 29 2179 30 2433 31 2524 32 2569 33 2831 34 3132 35 3199 36 3260 37 3568 38 3894 39 3980 40 4033 41 4363 42 4767 43 4846 44 4859 45 5268 46 5728 47 5766 48 5794 49 6258 50 6744 51 6800 52 6811 53 7298 54 7879 55 7919 56 7873 57 8456 58 9102 59 9084 60 9052 61 9699 62 10372 63 10371 64 10313 65 10984 66 11769 67 11743 68 11611 69 12395 70 13254 71 13153 72 13034 73 13891 74 14778 75 14693 76 14539 77 15421 78 16437 79 16318 80 16073 81 17085 82 18184 83 17973 84 17740 85 18834 86 19962 87 19766 88 19489 89 20609 90 21883 91 21644 92 21259 93 22526 94 23892 95 23544 96 23170 97 24528 98 25924 99 25590 100 25163 101 26548 102 28107 103 27721 104 27169 105 28718 106 30378 107 29866 108 29324 109 30973 110 32664 111 32165 112 31561 113 33238 114 35109 115 34549 116 33803 117 35661 118 37642 119 36939 120 36202 121 38169 122 40182 123 39491 124 38683 125 40679 126 42889 127 42128 128 41161 129 43355 130 45684 131 44763 132 43804 133 46116 134 48478 135 47568 136 46529 137 48871 138 51447 139 50458 140 49243 141 51800 142 54504 143 53338 144 52130 145 54814 146 57552 147 56396 148 55099 149 57814 150 60783 151 59539 152 58049 153 60996 154 64102 155 62664 156 61180 157 64263 158 67404 159 65975 160 64393 161 67508 162 70897 163 69371 164 67579 165 70943 166 74478 167 72741 168 70954 169 74463 170 78034 171 76305 172 74411 173 77953 174 81789 175 79954 176 77833 177 81641 178 85632 179 83569 180 81452 181 85414 182 89442 183 87386 184 85153 185 89149 186 93459 187 91288 188 88811 189 93090 190 97564 191 95148 192 92674 193 97116 194 101628 195 99218 196 96619 197 101096 198 105907 199 103373 200 100513 201 105290 202 110274 203 107478 204 104620 205 109569 206 114592 207 111801 208 108809 209 113794 210 119133 211 116209 212 112939 213 118241 214 123762 215 120559 216 117290 217 122773 218 128334 219 125135 220 121723 221 127243 222 133137 223 129796 224 126089 225 131943 226 138028 227 134391 228 130684 229 136728 230 142854 231 139220 232 135361 233 141443 234 147919 235 144134 236 139963 237 146396 238 153072 239 148974 240 144802 241 151434 242 158152 243 154056 244 149723 245 156394 246 163479 247 159223 248 154561 249 161600 250 168894 251 164308 252 159644 253 166891 254 174228 255 169643 256 164809 257 172096 258 179817 259 175063 260 169883 261 177555 262 185494 263 180393 264 175210 265 183099 266 191082 267 185981 268 180619 269 188549 270 196933 271 191654 272 185929 273 194261 274 202872 275 197229 276 191500 277 200058 278 208714 279 203070 280 197153 281 205753 282 214827 283 208996 284 202699 285 211718 286 221028 287 214816 288 208514 289 217768 290 227124 291 220910 292 214411 293 223708 294 233499 295 227089 296 220193 297 229926 298 239962 299 233154 300 226252 301 236229 302 246312 303 239501 304 232393 305 242414 306 252949 307 245933 308 238411 309 248885 310 259674 311 252243 312 244714 313 255441 314 266278 315 258843 316 251099 317 261871 318 273177 319 265528 320 257353 321 268595 322 280164 323 272083 324 263900 325 275404 326 287022 327 278936 328 270529 329 282079 330 294183 331 285874 332 277019 333 289056 334 301432 335 292674 336 283810 337 296118 338 308544 339 299780 340 290683 341 303038 342 315967 343 306971 344 297409 345 310268 346 323478 347 314016 348 304444 349 317583 350 330844 351 321375 352 311561 353 324748 354 338529 355 328819 356 318523 357 332231 358 346302 359 336109 360 325802 361 339799 362 353922 363 343721 364 333163 365 347209 366 361869 367 351418 368 340361 369 354945 370 369904 371 358953 372 347884 373 362766 374 377778 375 366818 376 355489 377 370421 378 385987 379 374768 380 362923 381 378410 382 394284 383 382548 384 370690 385 386484 386 402412 387 390666 388 378539 389 394384 390 410883 391 398869 392 386209 393 402626 394 419442 395 406894 396 394220 397 410953 398 427824 399 415265 400 402313 401 419098 402 436557 403 423721 404 410219 405 427593 406 445378 407 431991 408 418474 409 436173 410 454014 411 440615 412 426811 413 444563 414 463009 415 449324 416 434953 417 453311 418 472092 419 457839 420 443452 421 462144 422 480982 423 466716 424 452033 425 470779 426 490239 427 475678 428 460411 429 479780 430 499584 431 484438 432 469154 433 488866 434 508728 435 493568 436 477979 437 497746 438 518247 439 502783 440 486593 441 507000 442 527854 443 511788 444 495580 445 516339 446 537252 447 521171 448 504649 449 525464 450 547033 451 530639 452 513499 453 534971 454 556902 455 539889 456 522730 457 544563 458 566554 459 549525 460 532043 461 553933 462 576597 463 559246 464 541129 465 563693 466 586728 467 568741 468 550604 469 573538 470 596634 471 578630 472 560161 473 583153 474 606939 475 588604 476 569483 477 593166 478 617332 479 598344 480 579202 481 603264 482 627492 483 608486 484 589003 485 613124 486 638059 487 618713 488 598561 489 623390 490 648714 491 628698 492 608524 493 633741 494 659128 495 639093 496 618569 497 643846 498 669957 499 649573 500 628363 501 654365 502 680874 503 659803 504 638570 505 664969 506 691542 507 670451 508 648859 509 675319 510 702633 511 681184 512 658889 513 686091 514 713812 515 691659 516 669340 517 696948 518 724734 519 702560 520 679873 521 707543 522 736087 523 713546 524 690139 525 718568 526 747528 527 724266 528 700834 529 729678 530 758704 531 735420 532 711611 533 740518 534 770319 535 746659 536 722113 537 751796 538 782022 539 757624 540 733052 541 763159 542 793452 543 769031 544 744073 545 774244 546 805329 547 780523 548 754811 549 785775 550 817294 551 791733 552 765994 553 797391 554 828978 555 803393 556 777259 557 808721 558 841117 559 815138 560 788233 561 820505 562 853344 563 826593 564 799660 565 832374 566 865282 567 838506 568 811169 569 843949 570 877683 571 850504 572 822379 573 855986 574 890172 575 862204 576 834050 577 868108 578 902364 579 874370 580 845803 581 879928 582 915027 583 886621 584 857249 585 892218 586 927778 587 898566 588 869164 589 904593 590 940224 591 910985 592 881161 593 916658 594 953149 595 923489 596 892843 597 929201 598 966162 599 935679 600 905002 601 941829 602 978862 603 948351 604 917243 605 954139 606 992049 607 961108 608 929161 609 966935 610 1005324 611 973543 612 941564 613 979816 614 1018278 615 986468 616 954049 617 992371 618 1031727 619 999478 620 966203 621 1005420 622 1045264 623 1012158 624 978850 625 1018554 626 1058472 627 1025336 628 991579 629 1031354 630 1072183 631 1038599 632 1003969 633 1044656 634 1085982 635 1051524 636 1016860 637 1058043 638 1099444 639 1064955 640 1029833 641 1071088 642 1113417 643 1078471 644 1042459 645 1084643 646 1127478 647 1091641 648 1055594 649 1098283 650 1141194 651 1105325 652 1068811 653 1111573 654 1155429 655 1119094 656 1081673 657 1125381 658 1169752 659 1132509 660 1095052 661 1139274 662 1183722 663 1146446 664 1108513 665 1152809 666 1198219 667 1160468 668 1121611 669 1166870 670 1212804 671 1174128 672 1135234 673 1181016 674 1227028 675 1188318 676 1148939 677 1194796 678 1241787 679 1202593 680 1162273 681 1209110 682 1256634 683 1216498 684 1176140 685 1223509 686 1271112 687 1230941 688 1190089 689 1237534 690 1286133 691 1245469 692 1203659 693 1252101 694 1301242 695 1259619 696 1217770 697 1266753 698 1315974 699 1274315 700 1231963 701 1281023 702 1331257 703 1289096 704 1245769 705 1295843 706 1346628 707 1303491 708 1260124 709 1310748 710 1361614 711 1318440 712 1274561 713 1325263 714 1377159 715 1333474 716 1288603 717 1340336 718 1392792 719 1348114 720 1303202 721 1355494 722 1408032 723 1363316 724 1317883 725 1370254 726 1423839 727 1378603 728 1332161 729 1385580 730 1439734 731 1393488 732 1347004 733 1400991 734 1455228 735 1408943 736 1361929 737 1415996 738 1471297 739 1424483 740 1376443 741 1431575 742 1487454 743 1439613 744 1391530 745 1447239 746 1503202 747 1455321 748 1406699 749 1462489 750 1519533 751 1471114 752 1421449 753 1478321 754 1535952 755 1486489 756 1436780 757 1494238 758 1551954 759 1502450 760 1452193 761 1509733 762 1568547 763 1518496 764 1467179 765 1525818 766 1585228 767 1534116 768 1482754 769 1541988 770 1601484 771 1550330 772 1498411 773 1557728 774 1618339 775 1566629 776 1513633 777 1574066 778 1635282 779 1582494 780 1529452 781 1590489 782 1651792 783 1598961 784 1545353 785 1606474 786 1668909 787 1615513 788 1560811 789 1623065 790 1686114 791 1631623 792 1576874 793 1639741 794 1702878 795 1648343 796 1593019 797 1655971 798 1720257 799 1665148 800 1608713 801 1672815 802 1737724 803 1681503 804 1625020 805 1689744 806 1754742 807 1698476 808 1641409 809 1706219 810 1772383 811 1715534 812 1657339 813 1723316 814 1790112 815 1732134 816 1673890 817 1740498 818 1807384 819 1749360 820 1690523 821 1757218 822 1825287 823 1766671 824 1706689 825 1774568 826 1843278 827 1783516 828 1723484 829 1792003 830 1860804 831 1800995 832 1740361 833 1808968 834 1878969 835 1818559 836 1756763 837 1826571 838 1897222 839 1835649 840 1773802 841 1844259 842 1915002 843 1853381 844 1790923 845 1861469 846 1933429 847 1871198 848 1807561 849 1879325 850 1951944 851 1888533 852 1824844 853 1897266 854 1969978 855 1906518 856 1842209 857 1914721 858 1988667 859 1924588 860 1859083 861 1932830 862 2007444 863 1942168 864 1876610 865 1951024 866 2025732 867 1960406 868 1894219 869 1968724 870 2044683 871 1978729 872 1911329 873 1987086 874 2063722 875 1996554 876 1929100 877 2005533 878 2082264 879 2015045 880 1946953 881 2023478 882 2101477 883 2033621 884 1964299 885 2042093 886 2120778 887 2051691 888 1982314 889 2060793 890 2139574 891 2070435 892 2000411 893 2078983 894 2159049 895 2089264 896 2017993 897 2097851 898 2178612 899 2107579 900 2036252 901 2116804 902 2197662 903 2126576 904 2054593 905 2135239 906 2217399 907 2145658 908 2072411 909 2154360 910 2237224 911 2164218 912 2090914 913 2173566 914 2256528 915 2183468 916 2109499 917 2192246 918 2276527 919 2202803 920 2127553 921 2211620 922 2296614 923 2221608 924 2146300 925 2231079 926 2316172 927 2241111 928 2165129 929 2250004 930 2336433 931 2260699 932 2183419 933 2269631 934 2356782 935 2279749 936 2202410 937 2289343 938 2376594 939 2299505 940 2221483 941 2308513 942 2397117 943 2319346 944 2240009 945 2328393 946 2417728 947 2338641 948 2259244 949 2348358 950 2437794 951 2358650 952 2278561 953 2367773 954 2458579 955 2378744 956 2297323 957 2387906 958 2479452 959 2398284 960 2316802 961 2408124 962 2499772 963 2418546 964 2336363 965 2427784 966 2520819 967 2438893 968 2355361 969 2448170 970 2541954 971 2458678 972 2375084 973 2468641 974 2562528 975 2479193 976 2394889 977 2488546 978 2583837 979 2499793 980 2414123 981 2509185 982 2605234 983 2519823 984 2434090 985 2529909 986 2626062 987 2540591 988 2454139 989 2550059 990 2647633 991 2561444 992 2473609 993 2570951 994 2669292 995 2581719 996 2493820 997 2591928 998 2690374 999 2602740 1000 2514113