0 1 1 4 2 9 3 18 4 32 5 46 6 64 7 93 8 130 9 170 10 214 11 247 12 260 13 340 14 400 15 473 16 556 17 594 18 646 19 687 20 810 21 936 22 1046 23 1093 24 1184 25 1240 26 1284 27 1535 28 1642 29 1832 30 1864 31 1913 32 2096 33 2106 34 2352 35 2549 36 2856 37 2890 38 2916 39 3047 40 3132 41 3472 42 3594 43 4093 44 4106 45 4030 46 4246 47 4359 48 4756 49 4920 50 5538 51 5539 52 5398 53 5550 54 5816 55 6317 56 6288 57 7212 58 7252 59 6905 60 7146 61 7402 62 8056 63 8025 64 8988 65 9182 66 8662 67 8703 68 9296 69 10080 70 9850 71 11137 72 11200 73 10634 74 10670 75 11187 76 12374 77 11914 78 13238 79 13577 80 12824 81 12764 82 13452 83 14697 84 14222 85 15752 86 15984 87 15273 88 15044 89 15690 90 17358 91 16749 92 18452 93 18786 94 17780 95 17507 96 18310 97 20104 98 19506 99 21365 100 21510 101 20606 102 20278 103 21025 104 23232 105 22328 106 24486 107 24727 108 23402 109 23256 110 24048 111 26237 112 25504 113 27896 114 28008 115 26669 116 26224 117 27250 118 29768 119 28601 120 31592 121 31558 122 29756 123 29599 124 30704 125 33412 126 32162 127 35265 128 35376 129 33352 130 32890 131 34395 132 37274 133 35578 134 39350 135 39479 136 37052 137 36616 138 38076 139 41353 140 39534 141 43416 142 43782 143 40985 144 40136 145 42174 146 45798 147 43493 148 47986 149 48122 150 45080 151 44247 152 46146 153 50480 154 47774 155 52247 156 52894 157 49518 158 48382 159 50689 160 55052 161 52230 162 57222 163 57531 164 54214 165 52756 166 54920 167 60169 168 56958 169 62220 170 62744 171 58785 172 57368 173 59778 174 65106 175 61965 176 67496 177 67690 178 63824 179 62243 180 64704 181 70650 182 66866 183 72973 184 73304 185 68720 186 67326 187 69865 188 75878 189 72266 190 78822 191 78927 192 74192 193 72312 194 75226 195 81833 196 77446 197 84900 198 84858 199 79277 200 77822 201 80946 202 87782 203 83245 204 90834 205 91022 206 85140 207 83061 208 86886 209 94028 210 88634 211 97327 212 97518 213 90996 214 88962 215 92641 216 100484 217 94814 218 103614 219 104279 220 97108 221 94400 222 98952 223 107321 224 100974 225 110556 226 110854 227 103421 228 100652 229 104998 230 114390 231 107421 232 117060 233 118028 234 110088 235 106843 236 111760 237 121294 238 114046 239 124403 240 124908 241 117000 242 113330 243 117981 244 128802 245 121066 246 131712 247 132523 248 123680 249 120012 250 125098 251 135969 252 128304 253 139368 254 139618 255 130977 256 127058 257 132142 258 143914 259 135271 260 147226 261 147670 262 137912 263 134321 264 139470 265 151298 266 142930 267 155463 268 155626 269 145628 270 141302 271 147041 272 159642 273 150174 274 163982 275 163891 276 152732 277 148940 278 154974 279 167953 280 158210 281 172192 282 172378 283 160789 284 156212 285 163156 286 176526 287 165617 288 181108 289 181324 290 168764 291 164225 292 171060 293 185342 294 174010 295 189611 296 190476 297 177088 298 171580 299 179601 300 194590 301 182294 302 199004 303 199331 304 185554 305 179996 306 187706 307 204085 308 190920 309 207672 310 208946 311 194443 312 188234 313 196702 314 213226 315 199743 316 217442 317 218076 318 203600 319 196773 320 204958 321 223162 322 208962 323 227091 324 228096 325 212384 326 205554 327 214289 328 232614 329 218414 330 237056 331 237407 332 221912 333 214756 334 223482 335 242965 336 227514 337 247222 338 247846 339 230937 340 224156 341 233028 342 252514 343 237379 344 257920 345 258128 346 240900 347 233121 348 242736 349 263322 350 246676 351 268823 352 268764 353 250004 354 242932 355 252865 356 273932 357 257002 358 279292 359 279627 360 260306 361 252144 362 263310 363 284855 364 266436 365 290624 366 290914 367 270463 368 262314 369 273272 370 296046 371 277051 372 301398 373 302480 374 280928 375 271633 376 284040 377 307706 378 287502 379 313155 380 313632 381 291580 382 282184 383 294237 384 319566 385 298310 386 324020 387 325631 388 302752 389 292482 390 305450 391 330985 392 309298 393 336230 394 336966 395 314115 396 303172 397 315708 398 343322 399 320751 400 348216 401 349440 402 324938 403 314017 404 327304 405 355010 406 332472 407 360515 408 360902 409 336720 410 325352 411 338665 412 367760 413 343650 414 373092 415 373745 416 347806 417 336904 418 350374 419 379531 420 355716 421 386166 422 386374 423 359987 424 347914 425 362260 426 392698 427 367095 428 399488 429 399396 430 371096 431 359837 432 374680 433 405626 434 379620 435 412243 436 412608 437 383660 438 370996 439 387325 440 418946 441 391040 442 425996 443 426331 444 395940 445 383334 446 399362 447 432491 448 403926 449 438978 450 440314 451 408575 452 394564 453 412416 454 446540 455 416519 456 453152 457 453716 458 421434 459 407225 460 424674 461 460874 462 429476 463 466187 464 468118 465 434832 466 419620 467 438095 468 474568 469 442662 470 480788 471 481745 472 448430 473 432362 474 450362 475 489299 476 456380 477 495086 478 496594 479 461399 480 445292 481 464168 482 503222 483 470319 484 509792 485 510248 486 475390 487 458793 488 477672 489 518410 490 483592 491 524675 492 525508 493 488538 494 472496 495 491561 496 532350 497 497932 498 540144 499 540429 500 502988 501 485514 502 505630 503 547931 504 511374 505 555894 506 555768 507 516107 508 499624 509 520268 510 563172 511 526111 512 570926 513 571368 514 530886 515 512769 516 535146 517 578830 518 539572 519 587073 520 587490 521 545328 522 527244 523 549299 524 594708 525 554684 526 602348 527 603877 528 560130 529 540374 530 564566 531 611203 532 569430 533 618934 534 619534 535 575135 536 555232 537 578884 538 627900 539 584587 540 634176 541 636380 542 590746 543 569661 544 594600 545 643856 546 599912 547 651171 548 652232 549 606622 550 584488 551 608859 552 661018 553 615832 554 667816 555 669505 556 621660 557 599546 558 624892 559 677187 560 632022 561 684842 562 685372 563 637867 564 615158 565 640580 566 694760 567 647395 568 702106 569 703036 570 653098 571 630963 572 656654 573 710934 574 663936 575 720001 576 720278 577 669758 578 646016 579 672883 580 728948 581 679448 582 738116 583 738013 584 684884 585 662250 586 689770 587 746507 588 696454 589 755386 590 755924 591 701947 592 677372 593 706888 594 764508 595 711891 596 774000 597 774470 598 718534 599 693993 600 723096 601 782776 602 729224 603 791465 604 793304 605 735526 606 709052 607 740575 608 801654 609 746168 610 810450 611 811229 612 752736 613 726034 614 756984 615 820763 616 763500 617 827890 618 830424 619 770587 620 742546 621 774912 622 839016 623 780997 624 847306 625 848524 626 788662 627 759495 628 791174 629 858584 630 799188 631 866245 632 868214 633 805798 634 776632 635 809467 636 876950 637 817612 638 885652 639 886249 640 824284 641 794374 642 827268 643 896955 644 835074 645 905294 646 906296 647 841559 648 812392 649 845498 650 915288 651 853859 652 925612 653 925918 654 860398 655 829411 656 863956 657 935700 658 871452 659 946121 660 945972 661 877574 662 847778 663 883083 664 955590 665 890664 666 965714 667 966225 668 896846 669 864918 670 902428 671 975967 672 908088 673 986690 674 987208 675 915561 676 883706 677 920760 678 996540 679 927673 680 1006406 681 1008450 682 934746 683 900655 684 940510 685 1017844 686 946732 687 1027829 688 1028640 689 954130 690 919768 691 958947 692 1039402 693 966232 694 1047446 695 1050297 696 974196 697 938330 698 979100 699 1059919 700 985950 701 1069252 702 1070628 703 994519 704 957360 705 997406 706 1081876 707 1006341 708 1090544 709 1092730 710 1013758 711 976567 712 1017928 713 1102540 714 1026970 715 1112265 716 1112960 717 1034486 718 996486 719 1037859 720 1124940 721 1046552 722 1134250 723 1135441 724 1053838 725 1016626 726 1058272 727 1145449 728 1067584 729 1156966 730 1157356 731 1074953 732 1035646 733 1078878 734 1168284 735 1087241 736 1179918 737 1179766 738 1094114 739 1056179 740 1100232 741 1190524 742 1108704 743 1201741 744 1202376 745 1115602 746 1075282 747 1121827 748 1213246 749 1128172 750 1225122 751 1225741 752 1136508 753 1096204 754 1142240 755 1236187 756 1149990 757 1247108 758 1249356 759 1157857 760 1115136 761 1164202 762 1259868 763 1171181 764 1270948 765 1271870 766 1179400 767 1136391 768 1184720 769 1283808 770 1192886 771 1292729 772 1295906 773 1201746 774 1157014 775 1207115 776 1306584 777 1214760 778 1317002 779 1318467 780 1224274 781 1178142 782 1227412 783 1330989 784 1237388 785 1340588 786 1342984 787 1245577 788 1199470 789 1250186 790 1353848 791 1260285 792 1364684 793 1365402 794 1268534 795 1221503 796 1272324 797 1378664 798 1281902 799 1389033 800 1390284 801 1289962 802 1243794 803 1294891 804 1401386 805 1305150 806 1414162 807 1414561 808 1313288 809 1264840 810 1317668 811 1426609 812 1326910 813 1439512 814 1439332 815 1334457 816 1287484 817 1341282 818 1451150 819 1350589 820 1463648 821 1464306 822 1358192 823 1308527 824 1365098 825 1476280 826 1372042 827 1489429 828 1490086 829 1381238 830 1331630 831 1387593 832 1501580 833 1396100 834 1513614 835 1516143 836 1404762 837 1352456 838 1411824 839 1527677 840 1419456 841 1539828 842 1540884 843 1428533 844 1375856 845 1434410 846 1554032 847 1443313 848 1563848 849 1567330 850 1453088 851 1398555 852 1459008 853 1579108 854 1467362 855 1590485 856 1592176 857 1477848 858 1421762 859 1481303 860 1605898 861 1492282 862 1616386 863 1619087 864 1501292 865 1445152 866 1506316 867 1631005 868 1517410 869 1642868 870 1643630 871 1526477 872 1469368 873 1530570 874 1658254 875 1541109 876 1669562 877 1670962 878 1549944 879 1493823 880 1555318 881 1683144 882 1566634 883 1697063 884 1697554 885 1575538 886 1516866 887 1580301 888 1710732 889 1590426 890 1724870 891 1724663 892 1598742 893 1541664 894 1606112 895 1737633 896 1616334 897 1751268 898 1751980 899 1624685 900 1564748 901 1632154 902 1765070 903 1639833 904 1779480 905 1780190 906 1649836 907 1589951 908 1656800 909 1792726 910 1666122 911 1805913 912 1808624 913 1675560 914 1612686 915 1683245 916 1821258 917 1691622 918 1834570 919 1835639 920 1701484 921 1638264 922 1707890 923 1850021 924 1717650 925 1860744 926 1864518 927 1728257 928 1663026 929 1734758 930 1877326 931 1743869 932 1889810 933 1891618 934 1755272 935 1688297 936 1759082 937 1906544 938 1770990 939 1918055 940 1920934 941 1780800 942 1713782 943 1786305 944 1933912 945 1798338 946 1946882 947 1947715 948 1808200 949 1740128 950 1812716 951 1963573 952 1824170 953 1975896 954 1977426 955 1833761 956 1766728 957 1839670 958 1990638 959 1851901 960 2005840 961 2006332 962 1861580 963 1791767 964 1866828 965 2020702 966 1877730 967 2036003 968 2035824 969 1886796 970 1818722 971 1894857 972 2049914 973 1905918 974 2064660 975 2065507 976 1915000 977 1843748 978 1923134 979 2079689 980 1931420 981 2095304 982 2096102 983 1942329 984 1871102 985 1949830 986 2109718 987 1959935 988 2123994 989 2126978 990 1970208 991 1895781 992 1978502 993 2140650 994 1987622 995 2155023 996 2156246 997 1998316 998 1923490 999 2005241 1000 2171814