1 4 2 9 3 25 4 49 5 121 6 403 7 1207 8 1729 9 736 10 2668 11 403 12 2701 13 574 14 1462 15 3478 16 1855 17 5605 18 976 19 5092 20 1207 21 2701 22 7663 23 3154 24 8722 25 7663 26 10201 27 31003 28 75007 29 98209 30 35143 31 91567 32 17161 33 100147 34 129409 35 140209 36 22801 37 117907 38 58843 39 127087 40 64183 41 173809 42 32761 43 36481 44 75463 45 155827 46 197209 47 23632 48 71806 49 163894 50 211138 51 77356 52 222748 53 34222 54 38152 55 193264 56 95206 57 258778 58 46612 59 213844 60 51142 61 108106 62 114856 63 215821 64 35143 65 97969 66 226021 67 44023 68 247021 69 257821 70 329107 71 124609 72 342127 73 280021 74 139129 75 368767 76 146689 77 382387 78 314821 79 41704 80 369736 81 382966 82 52204 83 57754 84 144622 85 410026 86 152392 87 423856 88 344578 89 75604 90 168532 91 356788 92 466546 93 381808 94 95254 95 496006 96 153415 97 460645 98 65125 99 169975 100 78445 101 407515 102 420535 103 205495 104 549085 105 99925 106 447175 107 460795 108 234235 109 596005 110 63706 111 428542 112 193708 113 441772 114 567004 115 85816 116 93586 117 222478 118 482662 119 232468 120 630004 121 109726 122 253048 123 525352 124 263638 125 135436 126 75007 127 643063 128 659323 129 528529 130 247021 131 692443 132 257821 133 117907 134 573049 135 127087 136 743623 137 291421 138 619369 139 635209 140 734572 141 95698 142 105088 143 269944 144 602056 145 769312 146 786982 147 305374 148 649606 149 822922 150 317584 151 682306 152 165628 153 342604 154 698956 155 643063 156 108409 157 844561 158 863041 159 692443 160 140209 161 709303 162 342127 163 743623 164 173809 165 761083 166 382387 167 197209 168 796603 169 9082009 170 3141313 171 9273919 172 1226221 173 1341331 174 3409933 175 9663739 176 9861649 177 1577551 178 1698661 179 3827863 180 10263469 181 8479687 182 2073991 183 4263793 184 8667397 185 3321133 186 9993199 187 7942987 188 3605953 189 10399219 190 1739161 191 4048183 192 4199593 193 2003581 194 2138791 195 9271657 196 4665823 197 1226221 198 3785773 199 8666257 200 3939283 201 11332609 202 1626151 203 9056077 204 11766829 205 11986939 206 9859717 207 12433159 208 4902343 209 12659269 210 2480011 211 10273537 212 1341331 213 3949393 214 9189517 215 12043789 216 1626151 217 9595537 218 2219791 219 10431577 220 5122663 221 2528611 222 13893469 223 12738769 224 4611943 225 10332907 226 13205389 227 4787653 228 13441699 229 10767127 230 2235991 231 5145073 232 13920319 233 2561011 234 2726521 235 5696203 236 11659567 237 14653249 238 5883913 239 14901559 240 1739161 241 4951273 242 2068381 243 5324893 244 14639599 245 5514703 246 14890009 247 11989117 248 2750821 249 15396829 250 6096133 251 12697747 252 1698661 253 11347027 254 14579149 255 5098693 256 14831659 257 2044081 258 11813647 259 12049957 260 12528577 261 6088243 262 12770887 263 16124209 264 6705973 265 13509817 266 16923739 267 15502339 268 2187391 269 5635933 270 5841943 271 2561011 272 13051837 273 6259963 274 16835389 275 13809067 276 6901993 277 14065477 278 17659219 279 1946881 280 2138791 281 5981263 282 2528611 283 13817407 284 3128341 285 14340427 286 3332251 287 7081813 288 14604937 289 18378499 290 18665209 291 2073991 292 13522537 293 6104383 294 2686021 295 6554803 296 18497959 297 3104041 298 7479643 299 19376389 300 15679417 301 7954063 302 15958027 303 19972009 304 6013006 305 2216122 306 14324734 307 14598454 308 18670858 309 18966778 310 7189606 311 7430926 312 19866538 313 3749962 314 7919566 315 16282774 316 20476378 317 20784298 318 2347432 319 6575656 320 19612348 321 2795872 322 15625744 323 3023092 324 7311916 325 7561336 326 3483532 327 21162448 328 6657466 329 15497554 330 6908986 331 2714062 332 16379314 333 20871958 334 7675546 335 3426022 336 17279074 337 21832318 338 8460106 339 4155982 340 17888914 341 8993146 342 18196834 343 20854888 344 2616052 345 7773556 346 21827548 347 3352312 348 17442904 349 3601732 350 17752924 351 4106572 352 18378964 353 4361992 354 9131656 355 23488648 356 9409276 357 23826868 358 2753362 359 17262214 360 7855366 361 17892454 362 3519922 363 18210574 364 23463778 365 18852814 366 9253966 367 19176934 368 7639156 369 3156292 370 3421912 371 23744728 372 8778436 373 24093148 374 3959152 375 19310464 376 25150408 377 5057632 378 10247536 379 23642758 380 18742954 381 3307702 382 8852146 383 19751914 384 20092234 385 25425358 386 9751906 387 4706302 388 20778874 389 10361746 390 21125194 391 26518918 392 10669666 393 26887438 394 19143904 395 3177292 396 8605636 397 24938668 398 25303288 399 3746932 400 4034752 401 26038528 402 9833716 403 21228424 404 21582844 405 27533008 406 5503852 407 22297684 408 3030682 409 8638846 410 25884058 411 9581206 412 20942734 413 9899326 414 4510282 415 21661774 416 4812202 417 28162378 418 22755334 419 23123854 420 8976076 421 26448628 422 20979064 423 21343684 424 27603088 425 10607176 426 22449544 427 10939396 428 28775548 429 5324032 430 29966008 431 3010003 432 3321133 433 27481957 434 9682669 435 22179211 436 4266523 437 28669747 438 4906783 439 23318401 440 29875537 441 11724649 442 30281467 443 28021417 444 28423447 445 3785773 446 22940881 447 11427919 448 24110371 449 30463597 450 5767153 451 24900031 452 6104383 453 9682669 454 28954807 455 22914691 456 3939283 457 29781067 458 4951273 459 11460319 460 24502411 461 31035457 462 5635933 463 32735977 464 3409933 465 23258131 466 10379629 467 30312427 468 10743259 469 30736657 470 4440223 471 11476519 472 24878251 473 32021347 474 5488513 475 5841943 476 12591409 477 33324037 478 6554803 479 23995501 480 10727059 481 11476519 482 32568907 483 26076151 484 5686423 485 12615709 486 26498281 487 33451567 488 6783013 489 34790557 490 4048183 491 25157101 492 25581331 493 32653837 494 11846149 495 33100267 496 5145073 497 26435791 498 26866021 499 33999127 500 6259963 501 6635593 502 13805299 503 14203129 504 25476241 505 11427919 506 25908571 507 11821849 508 4949053 509 26779231 510 12615709 511 34991017 512 6471973 513 13821499 514 28544551 515 7245433 516 29439211 517 3971173 518 33651757 519 34114387 520 27106471 521 12591409 522 35045647 523 6292153 524 28904191 525 36457537 526 36932167 527 15069589 528 30273481 529 11724649 530 4902343 531 12550909 532 12967039 533 28787101 534 6096133 535 13805299 536 14227429 537 30174691 538 7307923 539 38434987 540 27712351 541 4665823 542 28174981 543 36027367 544 12918439 545 36512197 546 5475883 547 13772899 548 29574871 549 30518131 550 39463177 551 4017004 552 12025012 553 28065028 554 12456352 555 36588976 556 4841284 557 29010508 558 38076796 559 6092704 560 30443728 561 15086392 562 39582616 563 7789264 564 15979072 565 40596496 566 4579654 567 29772178 568 38044606 569 13696762 570 38550646 571 14593642 572 31235698 573 39568726 574 32221378 575 4301824 576 4733164 577 30041908 578 38494156 579 39008296 580 5601844 581 6039184 582 14528032 583 14987572 584 40562716 585 6919864 586 7363204 587 15912652 588 16378192 589 42135136 590 34049428 591 31301518 592 31807558 593 40500226 594 41028466 595 32825638 596 15855142 597 16328782 598 8492194 599 34885798 600 39874996 601 5499724 602 14348212 603 6412804 604 33103468 605 6872344 606 33623608 607 16263172 608 8262964 609 17232652 610 17720392 611 31792378 612 14234002 613 32314618 614 41366926 615 14717842 616 33893338 617 43006246 618 7543894 619 34955818 620 17662882 621 8970814 622 36564538 623 14103592 624 5840944 625 34146868 626 43439596 627 16083352 628 43998136 629 7274164 630 35225548 631 17085232 632 17589172 633 45685756 634 9213124 635 14457022 636 6014554 637 15463102 638 43856746 639 15969142 640 7478074 641 45562666 642 18529342 643 37692838 644 47286586 645 19047382 646 47865226 647 5204284 648 15324592 649 34605328 650 6686104 651 8185924 652 8689864 653 37962568 654 48322876 655 15169882 656 44642446 657 45225286 658 6873814 659 16742602 660 36504178 661 17270842 662 7891894 663 37643458 664 38216098 665 48169486 666 18867562 667 39367378 668 19942042 669 49960006 670 15034015 671 45106045 672 5537155 673 6050305 674 16098715 675 46887895 676 7601755 677 48085795 678 39118285 679 9171205 680 39704035 681 50505595 682 5177515 683 35825605 684 15926995 685 46659685 686 38165005 687 18112795 688 39346705 689 8868265 690 50313985 691 50930035 692 41134255 693 47011225 694 37765075 695 6931075 696 17399725 697 38361025 698 8549125 699 19641925 700 51338275 701 9637825 702 41978725 703 16094605 704 47966815 705 17219905 706 17785555 707 39754945 708 8213785 709 9874135 710 42207145 711 21221455 712 53639065 713 38092315 714 17023885 715 38704465 716 49556755 717 7304695 718 39934765 719 7862245 720 18751135 721 51465805 722 9546895 723 42419365 724 53392855 725 21082135 726 5803555 727 16811665 728 38851885 729 50526445 730 6928855 731 40098385 732 7494505 733 41983135 734 20332765 735 53768695 736 20926615 737 10352755 738 10930405 739 18359095 740 52809235 741 8264065 742 42154855 743 8843815 744 20152945 745 42795205 746 54128335 747 54790885 748 21964795 749 56121985 750 22572745 751 6128575 752 6710425 753 41019475 754 42310375 755 8467975 756 19956925 757 54471775 758 56489725 759 22409125 760 11437225 761 6294085 762 41142595 763 18514405 764 7479985 765 42449695 766 54799015 767 20362855 768 55477765 769 9273835 770 44425345 771 9875785 772 45087895 773 56841265 774 57526015 775 11085685 776 47087545 777 18269785 778 19516285 779 43237465 780 55796905 781 21401035 782 11333995 783 47267365 784 42085042 785 6648166 786 55502974 787 44106322 788 20582458 789 44784082 790 21221818 791 46145602 792 22506538 793 59002774 794 59708734 795 11609446 796 6198616 797 19048108 798 7443136 799 8068396 800 20337028 801 20984488 802 9324916 803 22285408 804 22938868 805 49055452 806 61469284 807 18770278 808 6993586 809 44302342 810 7626946 811 57468754 812 46390222 813 47090182 814 22709638 815 60345394 816 10823746 817 48496102 818 49202062 819 62523874 820 6527836 821 7169296 822 45078112 823 20461228 824 58454644 825 46488232 826 21794548 827 22464208 828 60639424 829 10406596 830 48618412 831 23809528 832 62105944 833 62842204 834 50766592 835 8000566 836 46570042 837 60917254 838 9973246 839 62399974 840 24247858 841 11963926 842 12631486 843 8190376 844 60432424 845 48814432 846 10193356 847 23302468 848 23994328 849 63430264 850 11538676 851 51011212 852 12214336 853 65699644 854 46685062 855 60669754 856 48888142 857 23724598 858 63699994 859 11097226 860 25130518 861 65227114 862 65993674 863 13154506 864 7210276 865 20618428 866 60890884 867 61653544 868 22730608 869 49692112 870 11331436 871 24860788 872 66271504 873 12721156 874 13419016 875 27008968 876 20994058 877 22420378 878 49741522 879 63414094 880 23136538 881 10165726 882 52017202 883 25297018 884 66533134 885 12271606 886 26747338 887 68893414 888 49012072 889 8265556 890 49774732 891 52074712 892 65987704 893 66778564 894 11805856 895 53618032 896 12519916 897 54392692 898 27205768 899 13954036 900 55948012 901 7050007 902 21789391 903 63922033 904 50643589 905 65511973 906 23995501 907 52976899 908 67911883 909 68715853 910 21429751 911 64101853 912 8666257 913 51435559 914 65707993 915 10848067 916 68132203 917 55384909 918 56180779 919 28174981 920 50643589 921 8126797 922 22555051 923 65887813 924 66701983 925 53025499 926 24821761 927 53823469 928 25581331 929 27872041 930 57843319 931 51419359 932 66051433 933 9056077 934 9801547 935 24470221 936 69352513 937 11298487 938 71015053 939 29106241 940 8500417 941 53009299 942 24878251 943 11526697 944 56277979 945 71211073 946 57924319 947 13817407 948 58750489 949 73744183 950 74592553 951 52976899 952 53799169 953 24502411 954 69695953 955 55449709 956 10987237 957 56277979 958 71390893 959 72241363 960 12528577 961 28451761 962 58774789 963 29247631 964 74804773 965 14855587 966 23318401 967 53758669 968 9655807 969 71554513 970 26498281 971 72413083 972 74136223 973 28904191 974 14340427 975 60473629 976 15128197 977 76735933 978 23702131 979 55384909 980 25308271 981 56229379 982 11433457 983 27732481 984 58774789 985 74307943 986 76931953 987 30992761 988 56180779 989 25714201 990 72707923 991 11659567 992 28168711 993 60473629 994 29815051 995 61338199 996 77111773 997 30641221 998 8667397 999 56115979 1000 72831043