1 1 2 22 3 202 4 130033 5 1942165 6 285373 7 15637242 8 2715027 9 1235905 10 28677249 11 1832656 12 13337667 13 1840302 14 13218127 15 32769805 16 13257151 17 12564203 18 2740608 19 9287193 20 778209 21 8253074 22 2972871 23 1270532 24 58383242 25 4563358 26 30184653 27 110706148 28 3120274 29 23859178 30 18217997 31 11831885 32 19654883 33 73038 34 45748 35 772824 36 30324531 37 536086 38 1028854 39 647579 40 687569 41 2099505 42 12067389 43 3691397 44 1751712 45 10406299 46 5316246 47 6479112 48 857237 49 4837218 50 321163 51 13561818 52 3335508 53 7056003 54 6427485 55 5046197 56 12810922 57 40711 58 103494 59 41881 60 103224 61 32206 62 131439 63 16306 64 252939 65 215286 66 8005062 67 6913557 68 4849085 69 7099371 70 4863044 71 503106 72 6389 73 4906 74 135887 75 38659 76 91967 77 386565 78 117585 79 208823 80 2181485 81 10746603 82 319308761 83 163341483 84 22795339 85 14571196 86 10597864 87 22884946 88 19341827 89 11718979 90 3708117 91 9318866 92 7142667 93 7365968 94 11293599 95 4635675 96 6999079 97 647736 98 7203809 99 3397886 100 7223769 101 3120747 102 8176448 103 27845437 104 19947733 105 22826425 106 10582189 107 6091997 108 12214841 109 1992294 110 11823328 111 37926571 112 34974516 113 66380809 114 80846447 115 82065012 116 16650536 117 27227504 118 119232834 119 29072213 120 15941842 121 3927756 122 16947502 123 19197256 124 22635592 125 5974906 126 5930559 127 5973355 128 3610461 129 1696804 130 20176488 131 189247251 132 15479749 133 363485 134 14942937 135 3717042 136 3404768 137 100610183 138 452691 139 5252407 140 4548084 141 12146553 142 3731301 143 8931055 144 16274041 145 8261842 146 66832 147 21432 148 113542 149 20532 150 70892 151 783636 152 42782 153 103182 154 412431 155 6465194 156 6891291 157 6319895 158 3883491 159 6294685 160 7203303 161 4769278 162 3074603 163 8278641 164 4293523 165 1056345 166 14705 167 3566511 168 6542684 169 4924407 170 681392 171 369032 172 6567 173 189332 174 4912006 175 9274059 176 2528077 177 16524211 178 2151585 179 11732483 180 39765202 181 61955283 182 20444362 183 3211473 184 13247925 185 435659 186 840718 187 644158 188 22763618 189 19528334 190 6935831 191 46491263 192 11278088 193 3044448 194 7737184 195 2115296 196 11345927 197 10969076 198 4142952 199 6117197 200 56325692 201 242456946 202 6700751 203 36645344 204 7773017 205 40466315 206 11227937 207 575898 208 2546327 209 13912335 210 1741933 211 356711 212 1218223 213 20894724 214 2036176 215 17397099 216 2601257 217 17938699 218 3655038 219 11916033 220 114688862 221 37200093 222 84587594 223 4203398 224 34601423 225 9896285 226 2457837 227 9905236 228 32725354 229 10437001 230 2427444 231 2940263 232 42701804 233 97528956 234 17058149 235 45507673 236 14401232 237 1774386 238 19361882 239 11122547 240 4786182 241 6989821 242 4775928 243 1286963 244 5147502 245 1290806 246 25142859 247 2157445 248 10361583 249 2368898 250 279967 251 15914499 252 134885576 253 41104956 254 35631631 255 771154 256 7335179 257 8937294 258 723509 259 866074 260 522421 261 105573 262 43055 263 9857753 264 14765561 265 30221224 266 18699989 267 23248023 268 63087671 269 88096095 270 255932531 271 17294973 272 78845828 273 43460313 274 83125574 275 3070241 276 7638894 277 4260476 278 6378272 279 54161306 280 4715792 281 9617796 282 2551037 283 1656102 284 32326 285 1959001 286 27745542 287 1630656 288 15665679 289 2778388 290 2799369 291 1335059 292 2662365 293 15905127 294 1530672 295 1714712 296 20217193 297 22373707 298 20211865 299 11504893 300 12460138 301 5107838 302 10680498 303 3225734 304 17563524 305 8186156 306 40830074 307 80001438 308 33279857 309 10560599 310 42180677 311 8007072 312 153160412 313 30466302 314 40196432 315 104802 316 30767 317 143772 318 17 319 13 320 241 321 105915 322 505429 323 715484 324 875836 325 5581458 326 7928673 327 8395625 328 2579505 329 1370191 330 12146726 331 28201379 332 5906284 333 8864361 334 820293 335 67724 336 672498 337 7262756 338 19862342 339 132997542 340 12378623 341 10869185 342 5018337 343 8658752 344 17594147 345 8834486 346 15002939 347 8955275 348 4740831 349 7436324 350 30033181 351 4176892 352 34606 353 119154 354 17821 355 136992 356 10471 357 423192 358 5350873 359 9782595 360 3398429 361 1045605 362 21550629 363 1589436 364 16001604 365 1589486 366 16014834 367 3400131 368 2190437 369 1575642 370 3000347 371 44805635 372 10093229 373 640194 374 3626 375 370194 376 9296 377 37042 378 65127 379 66523 380 354045 381 93919 382 3335498 383 10566774 384 3175383 385 11162544 386 113204003 387 66391251 388 52166846 389 1009581 390 25302114 391 65712998 392 28737828 393 777148 394 21404732 395 20207936 396 12645104 397 607094 398 42091578 399 116147781 400 469793346 401 9182051 402 25184303 403 5342318 404 8297064 405 6321821 406 5622183 407 1580256 408 4918427 409 11248605 410 2954629 411 1534695 412 3541117 413 43639432 414 59956473 415 576324 416 94656 417 244417 418 3157491 419 14357775 420 524996065 421 107877621 422 31634584 423 1029078 424 22695493 425 19975435 426 2719953 427 9020095 428 37074469 429 9533608 430 6855292 431 6353406 432 3691792 433 17922531 434 2485995 435 1776091 436 30709764 437 102535742 438 2297282 439 102522647 440 368184743 441 89023718 442 5083403 443 6757785 444 3765203 445 359751 446 148303 447 4265771 448 5993115 449 5593995 450 4371733 451 8087238 452 2910183 453 1874227 454 24194205 455 1011211671 456 33184582 457 7399597 458 6456209 459 3629925 460 11720753 461 31944831 462 101533286 463 2624131 464 9280575 465 4895627 466 47458 467 3256678 468 1309998 469 27042273 470 1683825 471 3312527 472 2210751 473 19247954 474 23321122 475 18577642 476 28235851 477 18538681 478 29427883 479 1235755 480 19862541 481 1784945 482 13184919 483 4203465 484 5572887 485 6182475 486 5584083 487 4212945 488 7651499 489 31714654 490 42366423 491 29850628 492 22319 493 114487 494 4764073 495 7414965 496 3445 497 944945 498 47149119 499 923776 500 4834794 501 7310658 502 7446054 503 5700138 504 2922149 505 2509173 506 9746054 507 32048288 508 16273988 509 8329454 510 25722521 511 12262544 512 10154951 513 2486034 514 9072866 515 2693942 516 1687287 517 1409229 518 2680737 519 16982436 520 91067999 521 301694756 522 5411544 523 4352646 524 5135829 525 263746 526 935084 527 4453746 528 1002407 529 453035 530 1221613 531 18381888 532 483546 533 9127 534 2764713 535 1503065 536 348791 537 1248184 538 20471616 539 187497728 540 3383863 541 1373178 542 15770902 543 23234963 544 22532618 545 2071048 546 21016053 547 2152895 548 20137653 549 355913759 550 130555575 551 417703 552 13027281 553 204505166 554 22672599 555 1077747 556 4946935 557 916413 558 35195 559 379473 560 11417 561 4866 562 438437 563 608212 564 1023437 565 33869839 566 7485496 567 569721 568 4671526 569 33084124 570 12529948 571 25814509 572 12185095 573 27282949 574 1291446 575 19014 576 181031 577 2902565 578 18784539 579 147263543 580 986975 581 248795 582 1790729 583 928374 584 3827611 585 6621714 586 3842261 587 12427 588 275556 589 5572499 590 6023444 591 5901183 592 300319 593 786719 594 693455 595 4962621 596 5720528 597 620823 598 7113568 599 5458416 600 9792864 601 2404143 602 10205485 603 22316995 604 23934331 605 92613144 606 39326671 607 10815895 608 22581073 609 15298318 610 16554313 611 2800682 612 6345857 613 35521529 614 63810447 615 21103478 616 20634254 617 69479916 618 33481829 619 73661856 620 18277094 621 14344 622 168951 623 314485 624 80625 625 403765 626 126939 627 20690776 628 15201244 629 21415051 630 24849595 631 2110113 632 3666971 633 15119712 634 122280004 635 51245841 636 635262 637 7104712 638 35798137 639 15149515 640 22148863 641 1997631 642 11741134 643 226184 644 2398691 645 27333726 646 60085721 647 7248335 648 4877595 649 4624073 650 9632898 651 391614 652 226963 653 2802821 654 119715545 655 30618883 656 17774758 657 19995949 658 6819164 659 39042124 660 13153576 661 18484369 662 2842695 663 8251133 664 62104628 665 69916587 666 49010318 667 53712087 668 14399882 669 31351337 670 10989755 671 3134961 672 7478735 673 7161 674 187604 675 835039 676 4245855 677 1070059 678 23862465 679 1024427 680 24934275 681 298683141 682 11189606 683 13892654 684 16940273 685 9181991 686 482961 687 9018191 688 28325453 689 22123012 690 11551462 691 18649012 692 2988231 693 7879392 694 6657282 695 5336342 696 6098832 697 4022992 698 36130456 699 175099269 700 12819376 701 2701664 702 18079557 703 130775678 704 3480353 705 2062359 706 11804606 707 369641 708 883726 709 7200721 710 6282045 711 3746319 712 1213045 713 2765301 714 1645945 715 20993121 716 131836651 717 19822746 718 1283049 719 18273297 720 18845941 721 70755 722 445517 723 14963838 724 3638943 725 6467415 726 226760563 727 684658 728 6810177 729 902512 730 5907462 731 9182157 732 78137792 733 6720632 734 48603202 735 46424033 736 698895 737 32101309 738 138759 739 97475 740 362679 741 8760468 742 186433723 743 356381 744 37787266 745 35103531 746 1288914 747 18119553 748 3010308 749 885008 750 2423328 751 1017038 752 23158854 753 1102971 754 40121223 755 58434494 756 4027493 757 32884565 758 16222025 759 19322141 760 7527755 761 41918639 762 3708506 763 9832441 764 7879747 765 19724686 766 16499839 767 1498666 768 3781067 769 6229602 770 4100667 771 13252362 772 95397593 773 48368481 774 55124 775 78576 776 43832 777 2027784 778 16053216 779 83998053 780 105763028 781 42210087 782 34698428 783 18002644 784 345864 785 12271201 786 17540545 787 17869201 788 2051834 789 2688051 790 2478244 791 55146449 792 2617295 793 9381951 794 3458295 795 6723991 796 37706095 797 4122793 798 13742292 799 108343527 800 38067458 801 11175833 802 29744141 803 15274415 804 22556957 805 23604392 806 11168542 807 497427 808 8755945 809 4951521 810 7160312 811 34753349 812 4130348 813 10341689 814 3516404 815 15795783 816 2242721 817 68855 818 47281 819 751962 820 33594193 821 9869338 822 43787593 823 32805282 824 49889632 825 4267189 826 8053694 827 8026561 828 29072755 829 15314419 830 23079259 831 6726106 832 9908306 833 35751374 834 9599001 835 5785542 836 3880977 837 915889 838 60546915 839 570537 840 40932412 841 11763007 842 4450779 843 5222536 844 9137854 845 45224551 846 7633585 847 6999903 848 4634685 849 5274411 850 10552205 851 32451431 852 6888305 853 31118765 854 4931219 855 13413244 856 1897776 857 13464994 858 20905192 859 2164221 860 15037445 861 5155635 862 259007 863 1284238 864 21629338 865 297957 866 8869288 867 14143588 868 44708363 869 5246315 870 9996417 871 5355162 872 6041917 873 91432 874 1818473 875 2563494 876 2592806 877 2872362 878 2302162 879 18915057 880 1773325 881 13778937 882 4031039 883 10775268 884 3279308 885 1959702 886 2109277 887 11105955 888 3830857 889 11369655 890 3036535 891 14336487 892 3783042 893 11777177 894 30180002 895 14726756 896 37559776 897 14460244 898 38335621 899 8987812 900 58472887 901 54345765 902 429795635 903 15414853 904 2298078 905 19734993 906 2256678 907 14292843 908 94079552 909 1418537 910 15893442 911 1481451 912 4485242 913 58785382 914 28347582 915 14585857 916 2368215 917 10706137 918 13595215 919 18787723 920 225768 921 9596773 922 37057931 923 2098786 924 303326 925 1830194 926 18766008 927 2853694 928 7896276 929 530438 930 837524 931 18573 932 66458 933 2443147 934 10464195 935 303489925 936 74393763 937 5878769 938 9469085 939 3723111 940 2088903 941 2558345 942 13120457 943 4058955 944 13679 945 3839865 946 14405 947 383431 948 17386 949 8199382 950 3103326 951 7235609 952 6253137 953 3730215 954 3368617 955 11853529 956 38170426 957 59330316 958 28057552 959 23618 960 1039653 961 2235109 962 20282436 963 1160884 964 3813186 965 9035889 966 136858967 967 64947065 968 6687839 969 3837804 970 14162931 971 3131734 972 2469168 973 9495318 974 564008 975 472267 976 7293 977 568 978 11737 979 181839 980 283357 981 49015284 982 29881748 983 18176153 984 8007995 985 19385933 986 6930038 987 8001909 988 472047 989 7277965 990 31924327 991 1423539 992 2299043 993 15029964 994 3681596 995 6938712 996 3524221 997 4615365 998 7443453 999 4639584 1000 5507898