0 1 1 3 2 3 3 21 4 9 5 11 6 21 7 9 8 1 9 133 10 693 11 69 12 7 13 189 14 3 15 7161 16 231 17 7 18 399 19 63 20 77 21 3311 22 4347 23 987 24 49 25 33 26 33 27 627 28 57 29 59 30 7161 31 2079 32 11 33 10787 34 207 35 2343 36 1463 37 4389 38 231 39 1659 40 6237 41 913 42 9933 43 693 44 161 45 7301833 46 19184319 47 4389 48 11 49 99 50 33 51 3399 52 231 53 1177 54 4389 55 43263 56 4807 57 1771 58 17523 59 231 60 26257 61 651 62 3 63 2178939 64 17157 65 2489 66 4304013 67 13041 68 161 69 45731 70 2312541 71 231 72 19 73 2793 74 57 75 2934987 76 279 77 713 78 38157 79 207 80 1771 81 238469 82 156123 83 9519 84 5719 85 566181 86 33 87 8673 88 28497 89 4117 90 3129357 91 9388071 92 2131591 93 68761 94 75411 95 44121 96 11 97 33 98 3 99 17479563 100 966207 101 33649 102 10397541 103 129789 104 209 105 1537664821 106 1002553299 107 43989 108 317471 109 399 110 14421 111 22511181 112 302841 113 1091189 114 5313 115 2507967 116 213521 117 320495021 118 1040193 119 1048971 120 589 121 3291921 122 1991409 123 3373203 124 5727 125 5773 126 551271567 127 7353 128 817 129 931 130 739233 131 14991 132 204953 133 32361 134 69 135 848055747 136 1991409 137 149017 138 80806677 139 168777 140 4882031 141 29396059 142 1197 143 3381 144 437 145 850839 146 850839 147 3326007 148 5580927 149 18791 150 6184017609 151 58311 152 341 153 130373383 154 405099 155 4484931 156 2658271 157 167471073 158 1311 159 10801329 160 10801329 161 9823 162 33624129 163 618849 164 3631831 165 1920059755229 166 315129379257 167 209666919 168 6407731 169 56373 170 211455123 171 212695329 172 14421 173 72523 174 258951 175 70915581 176 20136523 177 2389079 178 54208539 179 5177139 180 1801751 181 1811733 182 2139 183 5495091 184 2961 185 10199 186 987 187 68103 188 161 189 333224759 190 16625189889 191 7954527 192 76153 193 8901 194 69 195 243501621 196 962457 197 2449 198 3793065171 199 1844577 200 525481 201 54901 202 5589 203 44781 204 978397 205 2679829383 206 26017761 207 216353361 208 137193 209 452939 210 4986647014503 211 212700583557 212 17934564571 213 160745137 214 685377 215 70986993 216 149017 217 14421 218 1311 219 1317 220 111573 221 112079 222 1184799 223 2277 224 23 225 1732620659 226 45970701381 227 164703 228 54901 229 4347 230 48081 231 10325797813023 232 1315814408139 233 943909874963 234 445976193106983 235 60696301743 236 1257362183 237 33649 238 11428263 239 2544927 240 713 241 14973 242 2139 243 3226123221 244 213693 245 472261967 246 88235889 247 1247907573 248 948773 249 13416613 250 95445009 251 34707 252 16705199 253 2355433059 254 2649531 255 4559914388337 256 532977006429 257 148420219 258 7741041 259 1449 260 7192031 261 4216565510773 262 92702080359 263 16784733 264 39731603 265 41874129 266 236577 267 3849753 268 537 269 539 270 36871989 271 58311 272 6479 273 7661189557 274 1742661 275 66027489 276 370816170109 277 2011660959 278 187953 279 18753 280 161107023 281 392654779 282 88188177 283 176687973 284 7 285 260328607 286 94374819 287 13670349 288 537757 289 4731 290 666280923 291 12614613 292 3440349 293 224387207 294 11134893 295 4257 296 473 297 135041277217 298 1078413039 299 50855213211 300 1960482377 301 17644341393 302 10048929 303 18572379 304 6909 305 1457 306 391120149 307 3822021 308 9767387 309 1893521 310 847651959 311 2793 312 1501 313 49533 314 237 315 79268139637061133 316 144560462847 317 228373559 318 197989086351 319 227409076611 320 40452005803 321 1720556761 322 33267681 323 166854183 324 661274537 325 955833115083 326 3860439 327 2456643 328 4669497 329 1039243 330 5760179265687 331 52207062831 332 81700209437 333 236612294863 334 17884377 335 1496649 336 278597 337 7522119 338 75981 339 3894639 340 189724557 341 7430357 342 100947 343 1860309 344 19 345 204737183959 346 30535469524791 347 126981921 348 125763869 349 1106427 350 3826814871 351 40208343849597 352 48673258344249 353 345200413789 354 566211723 355 2224972827 356 186718301 357 3049254149557 358 5003626286043 359 13976555439 360 961093 361 3999 362 3999 363 104188551 364 48305727 365 2054153 366 368171097 367 915957 368 1073809 369 20179873 370 227471211 371 28842406293 372 2921849 373 26296641 374 2429007 375 220338289400691 376 567491673 377 6352117 378 34739680800027 379 5135529861 380 146896001483 381 8096630003 382 5693020389 383 1651587 384 1 385 71834037 386 71834037 387 2885511 388 34293 389 31027 390 57879276609 391 13434937263 392 165863423 393 166768938301 394 8788671 395 336567 396 653671564469 397 1961014693407 398 6735711 399 65401581 400 1423528029 401 248552513 402 49575603 403 29799 404 301 405 1624739613959 406 45743131449477 407 68109796293 408 38939781287 409 8805573 410 11867815839 411 9767212435497 412 1267436643 413 23406581 414 2379886971 415 63617942421 416 346364353181 417 18735563 418 12510628119 419 29929647 420 151110515591 421 453331546773 422 306927249 423 208189621535511 424 848394314061 425 4425412037 426 69657 427 512187921 428 9331 429 31476714101 430 7890417232929 431 68394552807 432 71704271 433 215112813 434 76330353 435 1767192603 436 16461 437 601741 438 792492897 439 24957 440 21748639 441 13948149887160181 442 817921101323817 443 9252477546189 444 1225610335033 445 3946227935167287 446 161724722709 447 2680167 448 643839 449 1333 450 883431087 451 35415868846743 452 2967664166929 453 1620512582423 454 6855219 455 115831751520639 456 66601289359 457 218843229 458 139263873 459 117604601853 460 2050978187049 461 2226903569 462 20207586320086011 463 56114864819739 464 5696166269 465 126994073182324733 466 81902115940664547 467 2067708355647 468 15310367648191 469 86446247937 470 89599302573 471 627195118011 472 29118122649 473 11148408821 474 5313 475 94374819 476 2506175749 477 5095055297717 478 5292834832593 479 2343888393 480 44935399 481 420831 482 57 483 814946019 484 368284809 485 6273764027 486 1432506004738221 487 1295620659 488 143957851 489 1581503 490 9144164718909 491 184918717083 492 36431934427 493 2375745618687 494 1031587329 495 153501066408644138877 496 14081374773749577 497 28532473337 498 3023044657773 499 163571554629 500 429318787647673 501 33386638747 502 48832749 503 9177 504 2386457 505 3424047 506 3701394807 507 186079211661 508 627938847 509 71096631677 510 1196788161723 511 242606057354991 512 4160553881 513 50304878743 514 280815842097 515 30048331071 516 1581503 517 6965343 518 1311 519 3308611341 520 4588747779 521 232001 522 85283437911441 523 2340658089 524 47466503 525 1654742948345672117009 526 46926336904699329 527 579337492650609 528 2666090528717 529 32331535611 530 38054217414147 531 15944672097453 532 644986735833 533 2764661454533 534 944760218871777 535 79465812802299 536 6275433373 537 88101475231 538 2634263379 539 2445927 540 63570367 541 63687981 542 651 543 22827 544 7623 545 1091 546 39021339 547 214011 548 23779 549 61088251 550 19871135361 551 4642397949 552 30450313 553 447503967 554 49722663 555 41591665087599 556 17310283347 557 26590297 558 47576361 559 24957 560 41148547 561 45800113210621 562 350058311037 563 77859821697 564 970632551 565 7271008439541 566 40374100371 567 145355307832588917 568 474671425179 569 59639581 570 4866323431636821 571 67223593899 572 450901913 573 1911553 574 86116401 575 44599676583 576 35058287 577 8098464297 578 503229 579 9561351 580 68357223 581 5924323163 582 106974021 583 112827028149 584 7977668657 585 163077839528368457 586 2417399683207578729 587 3141287368197 588 2379501824777 589 1654091019 590 112101 591 5492949 592 784707 593 561451 594 1345926351 595 2946234128265351 596 327359347585039 597 3764352053 598 1592327580849621 599 24428912277 600 45002651857 601 3139719897 602 3139719897 603 890368329 604 2679 605 143773 606 13779507 607 788049 608 47 609 19197479 610 129851271 611 9308253 612 522809882609 613 32008768323 614 14894727 615 84479757069939 616 974239791147 617 293818349711 618 1951632461877 619 2135821653 620 85466843 621 116696171031671 622 649060083 623 20063515899 624 1755279907 625 2295628968897 626 38535738087 627 1805246813631 628 7192218381 629 7203661847 630 40188074846453986758537 631 1186760879796064221 632 422293252585659983 633 35238268527259 634 1879065010341 635 209255673 636 744665537 637 75461001 638 1329877641 639 3186218251797 640 191820801711 641 1674191078879 642 164673932577 643 25636149 644 834673 645 3683034618571 646 16612169313663 647 139002171 648 2928501521 649 10043571 650 14472785811 651 810895716204519 652 11453922513 653 1663364080499 654 4709126037 655 22995279549 656 485280499 657 658931918491 658 1942161220989 659 2951609397 660 7505688134077 661 9930025401383871 662 9718197843 663 17126520562888861803 664 19480784710317 665 50382921483769633517 666 146438480542951382793 667 913894763418464031099 668 4256329570145873731 669 14275751448581 670 614388955257 671 142736827989 672 3699628453 673 584151861 674 11098885359 675 15269319201696483 676 2181331314528069 677 2873954301091 678 27040523772927 679 35537468121 680 2972351393 681 2956723 682 42555681 683 4055889 684 131537 685 100947 686 620103 687 4340721 688 247779 689 14231 690 65720636050839 691 285328376487 692 578999687959 693 14733357571649274799395133 694 648783011037334187259 695 1145873832754432089 696 210612324400347331 697 112941425934716049 698 1214423934781893 699 13208090968734639 700 13785229169997681 701 11911051163077 702 16323836683102179 703 48971510049306537 704 24258463766321 705 348661738338062303 706 376810908823107 707 1800318786599289 708 251586742253 709 24347104089 710 1730534421 711 4453075011 712 14926989 713 2509118359 714 39085894098867 715 3179676570836929317 716 78729835776981697 717 1104523595649454519 718 2844159246895193073 719 3961220743921749 720 4973803153 721 4322919 722 4322919 723 271967991 724 2928429 725 5363489459 726 86963370428823 727 1192220847 728 5696166269 729 3169516401362101 730 30723795528723 731 65044089033 732 38072058493 733 342648526437 734 272757 735 13170550033652852379 736 38255722859012673 737 1273645774267 738 3698197612227261633 739 17257232097 740 653857349453 741 1781487569531747 742 332634821775584036247 743 72305564798668089 744 2315482268507 745 534876404025117 746 46791742107 747 1866366329754819 748 2284414112307 749 919262078281 750 2374956133535729468571 751 2708815542263127 752 89474520443 753 4169895653 754 927613989 755 2097586821 756 127378829600099 757 382136488800297 758 29964507 759 3337758110255163 760 429344680998740661 761 10379237288271143281 762 26206719221067 763 3380666779517643 764 753225931678451 765 154517100013908972129251 766 16601339592505564281 767 705209616945141 768 109385701403 769 499170033 770 535880551173297 771 536576048319531 772 347748573117 773 7877799391 774 336860139 775 493885086651 776 106143367 777 374982169639 778 4650674589 779 66864815532537 780 20431194422654701 781 553036454313 782 3713244764673 783 555340644263795694297 784 491583418147337523 785 2179787311954246081 786 293189345891174942979 787 193967349503229351 788 19499363177573321 789 2394712727939 790 1370164257 791 20695323904017 792 6856866000731 793 10881846343160097 794 143994186015351 795 3306429115885533 796 16639256169 797 114897563 798 9432045399 799 2774403 800 105119047 801 17517984063503 802 292508082693 803 1464362893731 804 23807 805 17799628077 806 4735203 807 57252909 808 1624174629 809 232311929 810 699406535839772607 811 60167453546277 812 16960536627433861 813 9256891342782587 814 113974453751571 815 424373628063 816 6839055271301 817 292188237 818 26562567 819 42261142067458809 820 108737918539571515557 821 66263204472621277 822 258599636783941764927 823 3683815759974141 824 2112658843 825 71124167178288301 826 45531229923532567269 827 965892995683671 828 845169989049938783 829 52048591701022623 830 101477849400950187 831 711200267836520847 832 29836814995449 833 8113605140152672457 834 1248439405521 835 695238710859 836 168100746221639 837 1909093949917 838 22326215373 839 4744509 840 17832917989 841 104162073973749 842 3156426484053 843 654709303876467 844 14299021641 845 653225702071 846 1920890820093 847 814183294745133 848 9679734726414359 849 570530556208753 850 83477116207991583 851 209685450364791 852 578639561269 853 6230931 854 38275719 855 189321027574675227 856 2726279503689 857 77984644297 858 499294939210424259 859 168750401926239 860 111843533158819 861 29903007340909151911 862 34418122414513803 863 6357991948539 864 2243631567373 865 5988320130959661 866 5988320130959661 867 42064855315341 868 15637943330487 869 505868771591 870 4547426598477147 871 203616116349723 872 89107051 873 1882192036991 874 537249339 875 4254189728978409 876 42307848016668773 877 1142311896450056871 878 26283608210811 879 3487815555421323 880 15551414099584671 881 66398594867 882 2970955925965118553 883 191783111868642987 884 63348416293897 885 648420431058705613 886 19793463161092929 887 2479451730063 888 67906399 889 25688931 890 1568026659309 891 139748805649463620288899 892 2460310605510049677 893 4454483335406746477 894 1688614005154461 895 136483979295213 896 12015060898313 897 14501412240907036291 898 1675323288809973 899 385035346843917 900 2874562134890551 901 922734445299866871 902 90843074320565422040397 903 1761500056077445856739 904 835169323408266856653 905 3702696121413844239071 906 12637039278741411279333 907 4487668384401644211 908 417536894136551 909 104640178237 910 1093523343558087462867 911 109243025413046301 912 2853564909047 913 8319448161276147 914 396164198156007 915 49632974969950343631 916 57308735011137 917 35087677128523 918 530172760045761303933 919 228507607071 920 2848448881076491 921 670297974269 922 12370502601 923 35756366673 924 44704749280429 925 24733887784683 926 7631560563 927 3881716156479 928 1721964310017 929 47005123 930 413769748161 931 770853040823943 932 64410157463729 933 35151641036183 934 81933831 935 57253226921583 936 2187195378313 937 6561586134939 938 468584313 939 28402255617 940 68762255463 941 11125807 942 33377421 943 55802279709 944 9553549 945 53426059128058547602498981 946 48262935229558474783273146297 947 1416966351196753623453 948 772979651187790739 949 10754466244263 950 158079246435363 951 95843322641913 952 264466579286362299 953 8221870636264373 954 136566054277158891 955 653704190065816659 956 2970847038790939 957 14216128522096493839 958 6276710129838687 959 62210481203409 960 457231651 961 1371694953 962 105620511381 963 156616796643 964 144881403 965 145031617 966 22550371291749 967 29982765789 968 593973827 969 1939567480450243 970 3805075149555130803 971 183537912543 972 9640463998664639 973 2288743251481533 974 1034487813 975 242855927260184464149 976 16857699368497407 977 28361281945391 978 3018445317741 979 19049983709463 980 811679589227942897 981 15421912195330915043 982 167295064554016371 983 3031343143563 984 18827321701177 985 149467123179 986 979840029729 987 660810757635849 988 194527747317 989 9152053293473 990 443052737493398524991046009 991 3120030324869370561 992 346670036096596729 993 1324315718777139221 994 36207708664653 995 128747031897 996 27419545404713 997 10940398616480487 998 2140869693 999 5518635321528231 1000 175312605714360807