1 8 2 24 3 63 4 80 5 275 6 252 7 1247 8 240 9 513 10 825 11 1541 12 455 13 4187 14 3277 15 1891 16 1040 17 14111 18 819 19 43739 20 2200 21 2107 22 4623 23 6533 24 1365 25 15251 26 8321 27 8829 28 6235 29 13747 30 2387 31 116003 32 2720 33 13333 34 42333 35 14981 36 3276 37 33227 38 131217 39 12403 40 4400 41 61337 42 6321 43 74563 44 10235 45 49051 46 19599 47 186497 48 3640 49 67571 50 8525 51 31621 52 20935 53 79501 54 3591 55 40051 56 16385 57 82669 58 41241 59 586343 60 7161 61 358559 62 348009 63 48133 64 5440 65 68251 66 10787 67 540959 68 39593 69 38503 70 22649 71 727751 72 4095 73 128627 74 88357 75 90751 76 218695 77 285671 78 26533 79 451091 80 13200 81 39609 82 184011 83 83333 84 16211 85 1910291 86 178709 87 182527 88 30705 89 191351 90 13237 91 498317 92 52264 93 358453 94 559491 95 109061 96 7280 97 377719 98 88537 99 79003 100 11275 101 491063 102 94863 103 638189 104 41605 105 88831 106 238503 107 551051 108 9139 109 2617309 110 69575 111 305287 112 49155 113 359341 114 104653 115 318551 116 68735 117 1097227 118 837329 119 227767 120 19096 121 967637 122 716141 123 909709 124 580015 125 156875 126 18963 127 1164083 128 16320 129 1333603 130 76373 131 206981 132 32361 133 4674419 134 432821 135 146611 136 118779 137 902831 138 45731 139 1394171 140 51475 141 319507 142 485357 143 1720577 144 13104 145 2526191 146 256961 147 302869 148 166135 149 2489791 150 20801 151 1370477 152 656085 153 188191 154 308821 155 298871 156 54431 157 5921099 158 701521 159 11130319 160 32800 161 1246463 162 18981 163 4896847 164 340715 165 218791 166 249999 167 11720729 168 43645 169 2517763 170 1389581 171 741133 172 372815 173 360533 174 144137 175 736751 176 65504 177 753667 178 574053 179 514447 180 21483 181 1968557 182 1494951 183 269011 184 156792 185 3837271 186 416641 187 2101133 188 1331515 189 286903 190 327183 191 878219 192 21840 193 1492663 194 604117 195 2284621 196 140911 197 26556389 198 86963 199 2855651 200 33825 201 3235699 202 981317 203 2390963 204 183443 205 1010651 206 1914567 207 3089683 208 124815 209 1226413 210 94643 211 9801373 212 567635 213 1090987 214 1653153 215 556421 216 24605 217 11311343 218 7851927 219 385003 220 208725 221 587861 222 232589 223 20299691 224 55709 225 4054051 226 1078023 227 32165447 228 313959 229 13852211 230 238337 231 1069993 232 206205 233 653333 234 86821 235 2212291 236 2511987 237 3373933 238 683301 239 916327 240 43615 241 3488717 242 137149 243 355023 244 1792795 245 722261 246 429359 247 10257911 248 1740045 249 497503 250 167761 251 2273057 252 75852 253 535877 254 1551941 255 1563151 256 70720 257 15070481 258 1563401 259 8055419 260 173575 261 819541 262 620943 263 8307119 264 86296 265 8436011 266 3400013 267 2855299 268 1298463 269 8110351 270 106609 271 4410797 272 197965 273 597871 274 2708493 275 12712151 276 137193 277 1844267 278 929633 279 3117547 280 113245 281 1898999 282 958521 283 16349477 284 1293337 285 1302451 286 1047121 287 3957731 288 32760 289 22059371 290 941699 291 8135779 292 643135 293 1032533 294 61103 295 7665871 296 441785 297 4238191 298 2134277 299 1433407 300 47275 301 5567339 302 4111431 303 736291 304 1738885 305 4469471 306 221347 307 6792683 308 411539 309 765703 310 896613 311 11614607 312 108173 313 9411911 314 16572293 315 1590751 316 2104563 317 78399173 318 2382569 319 4074907 320 72160 321 2477479 322 1318021 323 2508419 324 44289 325 2538251 326 1703677 327 8560207 328 1022145 329 1735147 330 236003 331 10525139 332 666664 333 2736631 334 35162187 335 9433601 336 81055 337 18179803 338 548497 339 9199783 340 1538647 341 1863907 342 578683 343 3296573 344 893545 345 954271 346 1081599 347 5784491 348 267683 349 29244107 350 164791 351 27115453 352 163760 353 157044053 354 2008597 355 10742371 356 956755 357 3062347 358 1543341 359 7744349 360 61061 361 113907413 362 5905671 363 1056331 364 840739 365 62365361 366 807033 367 8087213 368 520760 369 2182267 370 3289301 371 2205967 372 1249923 373 3342827 374 3538573 375 1690501 376 3994545 377 39808939 378 103759 379 72412499 380 726755 381 6973063 382 2634657 383 109164959 384 99008 385 8899661 386 2387797 387 8394031 388 1812351 389 138028871 390 320819 391 9179117 392 422733 393 3093697 394 40995701 395 13114001 396 97083 397 15139199 398 1904033 399 14020063 400 90200 401 23165771 402 3786713 403 14302471 404 2455315 405 1314631 406 2049517 407 39771227 408 392231 409 6696967 410 749573 411 2030341 412 5105512 413 4099439 414 269521 415 144693071 416 332840 417 4177507 418 1840667 419 4922413 420 235081 421 28369507 422 29404119 423 4298527 424 1702905 425 21686051 426 2181121 427 7299139 428 2755255 429 2948947 430 820193 431 2976487 432 45695 433 25514959 434 11751757 435 10604431 436 14275735 437 68765447 438 900389 439 80965649 440 441529 441 2337301 442 1763583 443 2358533 444 431951 445 11888621 446 31045169 447 4799887 448 167127 449 22589191 450 285541 451 26861561 452 2874728 453 2466133 454 96496341 455 2487941 456 523265 457 288246353 458 25183589 459 3375487 460 541675 461 25514507 462 457907 463 180107927 464 439904 465 1788421 466 1959999 467 26182823 468 161239 469 8805007 470 2929333 471 124267699 472 4186645 473 8959567 474 3157637 475 5419751 476 949547 477 121070233 478 2748981 479 33051959 480 130845 481 38885003 482 10466151 483 1869211 484 411447 485 3768451 486 167751 487 9493579 488 3580705 489 86102143 490 434449 491 3862207 492 1288077 493 9728863 494 15012409 495 2944261 496 4640120 497 35080319 498 583331 499 21925063 500 138875 501 40173187 502 6819171 503 21262817 504 113477 505 40817131 506 1095053 507 18518683 508 4655823 509 4150387 510 1156793 511 34482281 512 211072 513 6321187 514 45211443 515 7434541 516 1250963 517 10698799 518 16600537 519 4314967 520 381865 521 538587919 522 586283 523 32834987 524 1379435 525 4415251 526 24921357 527 13338371 528 258888 529 154484399 530 1248797 531 3387781 532 8845783 533 88656023 534 1339457 535 11456491 536 2164105 537 59999011 538 6952037 539 48821543 540 119133 541 115923317 542 13232391 543 3542533 544 593895 545 3568661 546 1246613 547 47887663 548 4514155 549 75970621 550 1001275 551 3647621 552 365848 553 7344947 554 5532801 555 7398151 556 2788899 557 14899751 558 2509171 559 12507067 560 334109 561 7561159 562 5696997 563 88770463 564 1597535 565 19162541 566 49048431 567 38597959 568 2426785 569 240920291 570 763427 571 52181407 572 3141363 573 39418963 574 4147261 575 17208601 576 65520 577 7996067 578 3372529 579 40241659 580 2567975 581 5406787 582 4757081 583 8163167 584 1284805 585 2741311 586 3097599 587 86850173 588 183309 589 30544363 590 4181921 591 16773763 592 1325355 593 4224533 594 253327 595 8502551 596 6402831 597 8559787 598 1492109 599 40198891 600 104005 601 21681677 602 16702017 603 61101991 604 10961095 605 4832861 606 2208873 607 75187877 608 3499120 609 14843767 610 9082961 611 5979247 612 547651 613 82688797 614 9056501 615 4543621 616 1234617 617 115757839 618 2297109 619 33734263 620 2390968 621 18519463 622 23222993 623 74544443 624 272155 625 35159375 626 28235733 627 55053109 628 29605495 629 9504191 630 281263 631 47793203 632 3507605 633 134655559 634 235197519 635 96798131 636 4424771 637 9744827 638 1732889 639 3270403 640 216480 641 4935701 642 3857357 643 168716771 644 1756907 645 8328241 646 7525257 647 117232519 648 63973 649 50558399 650 750761 651 5090821 652 5111031 653 5122133 654 19986029 655 10303151 656 2725720 657 21012247 658 5205441 659 6955087 660 525481 661 57692081 662 31575417 663 12318541 664 1999992 665 111461981 666 2137009 667 90784037 668 85946555 669 17911807 670 5950549 671 54046367 672 243165 673 97871699 674 50893741 675 60161401 676 1090051 677 51347743 678 4310957 679 101450749 680 2051027 681 81642367 682 4885499 683 5603333 684 732571 685 11268251 686 4159261 687 18888379 688 2680635 689 73548047 690 1006787 691 57312923 692 2884264 693 97998517 694 17353473 695 173915411 696 720685 697 19442119 698 87732321 699 3913003 700 494373 701 283082027 702 1406437 703 65255273 704 327520 705 23867071 706 471132159 707 24002651 708 3768335 709 36208631 710 13337929 711 8095447 712 2870265 713 26455153 714 1058531 715 20459011 716 2572235 717 57593743 718 23233047 719 12417131 720 122915 721 31201997 722 18326641 723 6278533 724 15745195 725 8417251 726 306659 727 12691967 728 1679941 729 3190833 730 21178333 731 76966991 732 1345055 733 118227037 734 24261639 735 8650951 736 1041520 737 26082431 738 1165403 739 65559647 740 2427359 741 6594901 742 2305529 743 28727353 744 2083205 745 66619391 746 10028481 747 46887697 748 10615719 749 15720013 750 472781 751 236937497 752 10652120 753 54449431 754 16507433 755 20536001 756 246519 757 165063851 758 48278537 759 23053867 760 2180265 761 6955541 762 8148581 763 153718559 764 4391095 765 4686391 766 267623549 767 49431617 768 247520 769 141952787 770 3773863 771 21415297 772 7163391 773 71723579 774 9335221 775 57677051 776 3020585 777 14497267 778 159821429 779 14575091 780 796873 781 214735951 782 15112333 783 14725099 784 704555 785 14800391 786 1448867 787 104080751 788 74533769 789 17443213 790 8267677 791 10018807 792 388332 793 60386951 794 45417597 795 25292131 796 5712099 797 53373497 798 7648033 799 421386209 800 180400 801 77009743 802 15444917 803 18067501 804 3029747 805 15560651 806 10402237 807 36484471 808 4906585 809 10479787 810 680481 811 78944363 812 4169707 813 5292631 814 16705153 815 74411131 816 728429 817 40062413 818 8036033 819 53675623 820 1703575 821 97083251 822 6091023 823 162586943 824 15316536 825 16343251 826 12298317 827 172376573 828 411579 829 82487159 830 21347777 831 8293381 832 665680 833 8333333 834 9759197 835 92057081 836 5522001 837 58864537 838 14767239 839 321029927 840 705243 841 186750779 842 79422493 843 17064007 844 78410984 845 79989391 846 2236549 847 86117879 848 3086843 849 11541307 850 21013201 851 86926247 852 3397499 853 17471147 854 11677597 855 81893611 856 8265765 857 105782939 858 1560803 859 487046129 860 1864075 861 8902741 862 8929461 863 143028443 864 137085 865 65866291 866 9006401 867 54140683 868 35255271 869 344396867 870 3184289 871 100165001 872 36510641 873 15253057 874 70622059 875 85769251 876 1672151 877 221538971 878 242896947 879 6186403 880 923197 881 363282113 882 267589 883 31199923 884 3216623 885 43876531 886 7075599 887 122764349 888 1162945 889 57370853 890 5259199 891 9533701 892 93135507 893 22342861 894 14399661 895 32053531 896 278545 897 64384867 898 67767573 899 116404319 900 145607 901 48722477 902 5167663 903 6680437 904 8624184 905 9835541 906 7398399 907 167856677 908 69273137 909 33063967 910 3428093 911 43181401 912 1569795 913 230112521 914 864739059 915 6813151 916 69261055 917 100930523 918 600799 919 74345263 920 1191685 921 40728463 922 76543521 923 23868781 924 1373721 925 61625351 926 102921197 927 20633167 928 1099760 929 96681031 930 2092097 931 104031803 932 5226664 933 6969511 934 78548469 935 13996951 936 381017 937 52693133 938 21129389 939 17645689 940 6657575 941 42516263 942 21306157 943 53370029 944 12559935 945 128620171 946 3768113 947 43060091 948 5864183 949 36037327 950 1199671 951 144728887 952 2848641 953 21810359 954 13578407 955 36494371 956 4581635 957 76950457 958 22035917 959 220759883 960 317200 961 266006723 962 56351353 963 22266487 964 27909736 965 11182421 966 1954307 967 688285459 968 685745 969 52599259 970 4154909 971 113166167 972 132867 973 90907391 974 15188557 975 11415301 976 6095503 977 106928743 978 40238513 979 38351347 980 578579 981 116564491 982 11586621 983 270594343 984 3434872 985 116448671 986 11989921 987 58465933 988 45037227 989 58718909 990 687487 991 388943717 992 9280240 993 19732897 994 105240957 995 166350071 996 1749993 997 182947507 998 39862117 999 15978007 1000 349525