0 1 1 4 2 8 3 20 4 44 5 55 6 80 7 118 8 152 9 204 10 228 11 272 12 354 13 404 14 464 15 517 16 594 17 690 18 778 19 858 20 920 21 1036 22 1152 23 1276 24 1362 25 1439 26 1576 27 1730 28 1900 29 1982 30 2064 31 2282 32 2398 33 2632 34 2802 35 2711 36 3102 37 3284 38 3382 39 3682 40 3646 41 3916 42 4286 43 4378 44 4568 45 4713 46 4956 47 5226 48 5570 49 5706 50 5638 51 6218 52 6434 53 6680 54 7006 55 6829 56 7434 57 7780 58 8040 59 8240 60 8224 61 8848 62 9082 63 9548 64 9814 65 9445 66 10446 67 10738 68 10880 69 11520 70 11106 71 11810 72 12526 73 12716 74 12916 75 12959 76 13634 77 13992 78 14792 79 14742 80 14424 81 15788 82 15938 83 16340 84 17024 85 16323 86 17482 87 18172 88 18438 89 18826 90 18512 91 19610 92 20052 93 20838 94 21054 95 20299 96 22094 97 22466 98 22662 99 23616 100 22728 101 23932 102 25134 103 25230 104 25546 105 25365 106 26622 107 27038 108 28236 109 28180 110 27196 111 29726 112 29714 113 30248 114 31408 115 29759 116 31810 117 33048 118 33060 119 33614 120 32940 121 34698 122 35344 123 36376 124 36590 125 35157 126 38124 127 38338 128 38830 129 40116 130 38268 131 40404 132 42000 133 42220 134 42372 135 41815 136 43884 137 44310 138 46060 139 45866 140 44052 141 47974 142 47782 143 48422 144 50170 145 47343 146 50358 147 52140 148 51976 149 52618 150 51658 151 53918 152 54834 153 56416 154 56316 155 54203 156 58402 157 58598 158 59176 159 60854 160 57880 161 61212 162 63274 163 63208 164 63594 165 62463 166 65476 167 65858 168 68136 169 67916 170 64886 171 70446 172 70280 173 70812 174 73214 175 68913 176 73200 177 75796 178 75088 179 75918 180 74358 181 77540 182 78516 183 80800 184 80358 185 77107 186 83200 187 82936 188 83972 189 86024 190 81476 191 86276 192 88774 193 88608 194 89138 195 87115 196 91222 197 91728 198 94630 199 94186 200 89812 201 97370 202 96920 203 97496 204 100482 205 94835 206 100234 207 103486 208 102636 209 103404 210 101432 211 105226 212 106518 213 109584 214 108582 215 104095 216 112356 217 111730 218 112770 219 115512 220 109158 221 115700 222 118706 223 118072 224 118948 225 116005 226 121148 227 122054 228 125340 229 124718 230 118838 231 128464 232 128046 233 128364 234 132210 235 124513 236 131594 237 135648 238 134514 239 135210 240 132284 241 137518 242 138678 243 142724 244 141122 245 135063 246 145894 247 144554 248 145892 249 149644 250 140812 251 149218 252 152974 253 151998 254 153108 255 148839 256 155418 257 156484 258 160512 259 159262 260 152154 261 164050 262 163118 263 163706 264 168100 265 158651 266 167110 267 171982 268 170638 269 171202 270 167388 271 173990 272 175182 273 180122 274 177982 275 170125 276 183802 277 181866 278 183186 279 187836 280 176588 281 186908 282 191912 283 189924 284 191358 285 186119 286 193838 287 195434 288 199844 289 198334 290 189308 291 203782 292 202526 293 203412 294 208486 295 196299 296 207138 297 212810 298 211120 299 211518 300 206440 301 214886 302 215844 303 221648 304 219384 305 209147 306 225936 307 223320 308 224822 309 230752 310 216292 311 228938 312 234892 313 232384 314 233756 315 227519 316 236610 317 238266 318 243860 319 241352 320 230812 321 248038 322 246090 323 247338 324 253010 325 238279 326 251516 327 257770 328 255664 329 256176 330 249778 331 259946 332 260858 333 267714 334 264816 335 252291 336 272198 337 269546 338 270610 339 277470 340 260332 341 275118 342 282614 343 278772 344 280522 345 273119 346 283520 347 285446 348 292218 349 288950 350 275914 351 296600 352 294000 353 295652 354 302062 355 283967 356 300128 357 307276 358 304344 359 305406 360 297032 361 309256 362 310208 363 317862 364 314854 365 299359 366 323008 367 319548 368 320760 369 328744 370 308518 371 325662 372 334098 373 329974 374 331402 375 322835 376 334790 377 336782 378 344974 379 340446 380 325176 381 349958 382 346050 383 347964 384 355434 385 334033 386 353122 387 360854 388 357404 389 358624 390 348624 391 362446 392 364180 393 372598 394 368642 395 350797 396 377896 397 374430 398 375022 399 384106 400 360706 401 380340 402 390138 403 385300 404 386670 405 376537 406 390416 407 392464 408 402080 409 396566 410 378350 411 407216 412 402486 413 404404 414 413628 415 387751 416 410110 417 419254 418 414570 419 416486 420 404064 421 420292 422 422094 423 431392 424 426810 425 406415 426 437368 427 432754 428 433912 429 444054 430 417064 431 439386 432 450262 433 445102 434 446048 435 434067 436 450700 437 452278 438 463360 439 456768 440 435686 441 469358 442 463026 443 465228 444 475704 445 445927 446 471194 447 481970 448 476136 449 478042 450 464132 451 481956 452 484690 453 494790 454 489090 455 466013 456 500890 457 495758 458 497188 459 508038 460 477164 461 502806 462 514976 463 509008 464 509826 465 496009 466 514890 467 516474 468 528684 469 521946 470 496914 471 535078 472 528226 473 530154 474 542686 475 507683 476 536690 477 549122 478 541796 479 543982 480 528310 481 548336 482 550912 483 562478 484 555768 485 529803 486 569024 487 562558 488 564670 489 576656 490 541144 491 570914 492 583726 493 577152 494 577972 495 561729 496 583802 497 584774 498 598636 499 590692 500 562336 501 605442 502 597816 503 599492 504 613198 505 574233 506 606256 507 620594 508 611860 509 614034 510 596694 511 618474 512 621550 513 635126 514 626542 515 597275 516 641466 517 634084 518 636554 519 649258 520 609336 521 642894 522 657118 523 649052 524 650848 525 631905 526 656280 527 657776 528 672578 529 664526 530 631610 531 679798 532 671596 533 672924 534 688354 535 644631 536 680262 537 696204 538 686304 539 688480 540 669196 541 693368 542 696276 543 711514 544 701738 545 668615 546 718894 547 709346 548 712332 549 726850 550 681366 551 719630 552 734490 553 725740 554 727550 555 705839 556 733182 557 735194 558 751192 559 741530 560 705412 561 758828 562 749798 563 750760 564 767502 565 719353 566 758334 567 775770 568 765526 569 767014 570 745592 571 772284 572 775428 573 792946 574 780994 575 744175 576 800036 577 789410 578 792166 579 808742 580 757624 581 799876 582 816866 583 806106 584 809050 585 784253 586 814152 587 816780 588 833776 589 823338 590 783408 591 841810 592 831858 593 832998 594 851332 595 797903 596 840842 597 860052 598 848542 599 849974 600 825728 601 856388 602 858636 603 877720 604 865030 605 823577 606 886244 607 873142 608 876456 609 895078 610 837716 611 884554 612 903552 613 891320 614 893996 615 866717 616 899560 617 902806 618 921060 619 908810 620 865370 621 929514 622 917962 623 920040 624 939114 625 880463 626 927746 627 948248 628 936388 629 936990 630 910368 631 943856 632 946298 633 967230 634 953484 635 907211 636 975750 637 962092 638 964772 639 985718 640 922048 641 973292 642 994672 643 980164 644 983402 645 954085 646 989024 647 992630 648 1012628 649 999140 650 951550 651 1021114 652 1008538 653 1010846 654 1031618 655 966427 656 1019500 657 1041204 658 1027612 659 1028828 660 998694 661 1036608 662 1037984 663 1060648 664 1046100 665 994679 666 1069996 667 1055038 668 1057568 669 1080444 670 1010572 671 1066468 672 1090114 673 1073896 674 1076844 675 1044817 676 1082958 677 1086494 678 1109342 679 1093082 680 1041300 681 1117860 682 1103128 683 1106524 684 1128014 685 1057099 686 1114964 687 1138038 688 1123304 689 1125114 690 1091564 691 1132254 692 1134538 693 1158820 694 1143162 695 1086383 696 1168146 697 1152584 698 1154390 699 1179038 700 1103766 701 1163688 702 1189614 703 1171590 704 1174756 705 1140545 706 1180900 707 1184834 708 1209614 709 1191958 710 1134846 711 1218894 712 1202206 713 1205516 714 1229574 715 1151105 716 1215342 717 1239656 718 1223028 719 1225532 720 1188096 721 1232840 722 1235530 723 1260856 724 1243986 725 1182301 726 1271058 727 1254114 728 1255696 729 1282436 730 1200422 731 1265386 732 1292974 733 1274672 734 1276684 735 1239167 736 1283738 737 1287192 738 1315112 739 1294362 740 1232676 741 1324392 742 1305290 743 1308984 744 1335436 745 1249867 746 1318974 747 1345528 748 1327234 749 1330418 750 1289204 751 1336958 752 1340668 753 1367702 754 1348814 755 1282923 756 1377834 757 1359866 758 1361418 759 1389656 760 1301812 761 1371096 762 1401142 763 1380918 764 1383110 765 1342389 766 1391022 767 1394046 768 1423676 769 1402188 770 1334280 771 1434170 772 1412870 773 1416472 774 1445748 775 1351911 776 1427114 777 1456680 778 1435444 779 1439002 780 1394368 781 1446066 782 1450268 783 1478364 784 1458150 785 1386973 786 1489424 787 1469106 788 1472106 789 1501728 790 1406176 791 1481736 792 1513124 793 1492656 794 1493516 795 1449215 796 1502448 797 1504898 798 1537064 799 1513954 800 1440192 801 1547978 802 1524890 803 1528442 804 1560358 805 1458759 806 1539250 807 1571252 808 1548168 809 1551590 810 1504614 811 1558650 812 1563558 813 1594332 814 1571456 815 1495799 816 1604818 817 1583394 818 1586388 819 1617594 820 1514836 821 1596852 822 1629962 823 1607004 824 1608902 825 1560671 826 1618348 827 1620246 828 1654272 829 1630380 830 1549862 831 1665566 832 1641916 833 1644412 834 1678970 835 1569301 836 1655892 837 1691192 838 1664860 839 1668698 840 1618042 841 1676304 842 1680816 843 1714564 844 1689294 845 1607539 846 1725536 847 1701100 848 1705708 849 1738324 850 1627264 851 1716076 852 1750590 853 1726424 854 1728758 855 1675687 856 1737902 857 1740052 858 1776334 859 1750730 860 1663844 861 1788054 862 1762496 863 1764900 864 1801358 865 1685219 866 1776506 867 1814014 868 1786564 869 1789772 870 1736640 871 1797358 872 1802618 873 1839276 874 1811102 875 1723575 876 1850536 877 1823914 878 1828094 879 1863292 880 1744006 881 1839796 882 1876090 883 1849244 884 1852736 885 1795385 886 1861416 887 1864902 888 1902164 889 1875286 890 1782058 891 1914276 892 1888142 893 1889360 894 1928642 895 1803873 896 1901662 897 1941744 898 1912742 899 1915386 900 1857864 901 1924030 902 1928362 903 1968256 904 1937450 905 1843371 906 1980006 907 1950094 908 1955024 909 1993700 910 1864496 911 1967114 912 2005846 913 1977194 914 1981196 915 1918591 916 1989486 917 1993280 918 2032896 919 2003202 920 1905138 921 2045430 922 2016790 923 2018870 924 2059652 925 1928007 926 2030762 927 2073198 928 2043030 929 2044958 930 1983784 931 2054582 932 2058678 933 2101210 934 2068258 935 1967477 936 2113762 937 2081426 938 2085906 939 2127376 940 1989320 941 2098388 942 2141064 943 2108488 944 2113246 945 2047051 946 2121482 947 2126758 948 2167344 949 2136302 950 2031480 951 2180290 952 2150002 953 2152876 954 2195602 955 2054263 956 2164958 957 2209586 958 2177824 959 2179070 960 2113212 961 2189854 962 2192928 963 2237856 964 2204188 965 2095331 966 2251456 967 2216604 968 2221342 969 2266580 970 2117852 971 2234230 972 2279520 973 2244976 974 2249220 975 2179547 976 2258054 977 2263178 978 2307284 979 2272680 980 2162756 981 2320106 982 2287154 983 2290962 984 2335258 985 2185507 986 2303644 987 2349662 988 2316176 989 2317668 990 2247366 991 2328998 992 2331742 993 2379486 994 2343560 995 2227531 996 2392838 997 2357582 998 2360706 999 2408426 1000 2251296