0 1 1 1 2 1 3 1 4 2 5 1 6 1 7 3 8 3 9 1 10 1 11 4 12 7 13 4 14 1 15 1 16 5 17 13 18 13 19 5 20 1 21 1 22 6 23 21 24 34 25 21 26 6 27 1 28 1 29 7 30 31 31 73 32 73 33 31 34 7 35 1 36 1 37 8 38 43 39 136 40 209 41 136 42 43 43 8 44 1 45 1 46 9 47 57 48 229 49 501 50 501 51 229 52 57 53 9 54 1 55 1 56 10 57 73 58 358 59 1045 60 1546 61 1045 62 358 63 73 64 10 65 1 66 1 67 11 68 91 69 529 70 1961 71 4051 72 4051 73 1961 74 529 75 91 76 11 77 1 78 1 79 12 80 111 81 748 82 3393 83 9276 84 13327 85 9276 86 3393 87 748 88 111 89 12 90 1 91 1 92 13 93 133 94 1021 95 5509 96 19081 97 37633 98 37633 99 19081 100 5509 101 1021 102 133 103 13 104 1 105 1 106 14 107 157 108 1354 109 8501 110 36046 111 93289 112 130922 113 93289 114 36046 115 8501 116 1354 117 157 118 14 119 1 120 1 121 15 122 183 123 1753 124 12585 125 63591 126 207775 127 394353 128 394353 129 207775 130 63591 131 12585 132 1753 133 183 134 15 135 1 136 1 137 16 138 211 139 2224 140 18001 141 106096 142 424051 143 1047376 144 1441729 145 1047376 146 424051 147 106096 148 18001 149 2224 150 211 151 16 152 1 153 1 154 17 155 241 156 2773 157 25013 158 169021 159 805597 160 2501801 161 4596553 162 4596553 163 2501801 164 805597 165 169021 166 25013 167 2773 168 241 169 17 170 1 171 1 172 18 173 273 174 3406 175 33909 176 259026 177 1442173 178 5470158 179 12975561 180 17572114 181 12975561 182 5470158 183 1442173 184 259026 185 33909 186 3406 187 273 188 18 189 1 190 1 191 19 192 307 193 4129 194 45001 195 384091 196 2456299 197 11109337 198 32989969 199 58941091 200 58941091 201 32989969 202 11109337 203 2456299 204 384091 205 45001 206 4129 207 307 208 19 209 1 210 1 211 20 212 343 213 4948 214 58625 215 553636 216 4010455 217 21204548 218 76751233 219 175721140 220 234662231 221 175721140 222 76751233 223 21204548 224 4010455 225 553636 226 58625 227 4948 228 343 229 20 230 1 231 1 232 21 233 381 234 5869 235 75141 236 778641 237 6315001 238 38398641 239 165625929 240 472630861 241 824073141 242 824073141 243 472630861 244 165625929 245 38398641 246 6315001 247 778641 248 75141 249 5869 250 381 251 21 252 1 253 1 254 22 255 421 256 6898 257 94933 258 1071766 259 9636817 260 66471826 261 335262313 262 1163391958 263 2581284541 264 3405357682 265 2581284541 266 1163391958 267 335262313 268 66471826 269 9636817 270 1071766 271 94933 272 6898 273 421 274 22 275 1 276 1 277 23 278 463 279 8041 280 118409 281 1447471 282 14308663 283 110676833 284 642451441 285 2654025319 286 7307593151 287 12470162233 288 12470162233 289 7307593151 290 2654025319 291 642451441 292 110676833 293 14308663 294 1447471 295 118409 296 8041 297 463 298 23 299 1 300 1 301 24 302 507 303 9304 304 146001 305 1922136 306 20739259 307 178134552 308 1174226049 309 5671386136 310 18941512731 311 40864292184 312 53334454417 313 40864292184 314 18941512731 315 5671386136 316 1174226049 317 178134552 318 20739259 319 1922136 320 146001 321 9304 322 507 323 24 324 1 325 1 326 25 327 553 328 10693 329 178165 330 2514181 331 29424085 332 278295193 333 2059640713 334 11453449105 335 45481765921 336 121247816845 337 202976401213 338 202976401213 339 121247816845 340 45481765921 341 11453449105 342 2059640713 343 278295193 344 29424085 345 2514181 346 178165 347 10693 348 553 349 25 350 1 351 1 352 26 353 601 354 12214 355 215381 356 3244186 357 40956901 358 423470006 359 3484717129 360 22021483546 361 102195627281 362 329604456886 363 693347907421 364 896324308634 365 693347907421 366 329604456886 367 102195627281 368 22021483546 369 3484717129 370 423470006 371 40956901 372 3244186 373 215381 374 12214 375 601 376 26 377 1 378 1 379 27 380 651 381 13873 382 258153 383 4135011 384 56041987 385 629438601 386 5711078673 387 40558249963 388 216730118331 389 829903882017 390 2148321709561 391 3535017524403 392 3535017524403 393 2148321709561 394 829903882017 395 216730118331 396 40558249963 397 5711078673 398 629438601 399 56041987 400 4135011 401 258153 402 13873 403 651 404 27 405 1 406 1 407 28 408 703 409 15676 410 307009 411 5211916 412 75507103 413 916136908 414 9098838721 415 71920704124 416 436944953791 417 1954055782108 418 6103575192193 419 12548540320876 420 16083557845279 421 12548540320876 422 6103575192193 423 1954055782108 424 436944953791 425 71920704124 426 9098838721 427 916136908 428 75507103 429 5211916 430 307009 431 15676 432 703 433 28 434 1 435 1 436 29 437 757 438 17629 439 362501 440 6502681 441 100317169 442 1308430817 443 14134347529 444 123320412181 445 842527453421 446 4338087083749 447 16062421776397 448 40476722545169 449 65573803186921 450 65573803186921 451 40476722545169 452 16062421776397 453 4338087083749 454 842527453421 455 123320412181 456 14134347529 457 1308430817 458 100317169 459 6502681 460 362501 461 17629 462 757 463 29 464 1 465 1 466 30 467 813 468 19738 469 425205 470 8037726 471 131588665 472 1836980538 473 21463442793 474 205209960670 475 1561734494661 476 9144481575450 477 39511091161693 478 119823200043678 479 241253367679185 480 306827170866106 481 241253367679185 482 119823200043678 483 39511091161693 484 9144481575450 485 1561734494661 486 205209960670 487 21463442793 488 1836980538 489 131588665 490 8037726 491 425205 492 19738 493 813 494 30 495 1 496 1 497 31 498 871 499 22009 500 495721 501 9850231 502 170604751 503 2539200721 504 31930889329 505 332419088431 506 2794938616471 507 18412283563081 508 91568136166681 509 328634683136839 510 807927483311551 511 1290434218669921 512 1290434218669921 513 807927483311551 514 328634683136839 515 91568136166681 516 18412283563081 517 2794938616471 518 332419088431 519 31930889329 520 2539200721 521 170604751 522 9850231 523 495721 524 22009 525 871 526 31 527 1 528 1 529 32 530 931 531 24448 532 574673 533 11976256 534 218831107 535 3460321376 536 46626733633 537 525590073568 538 4847038223171 539 35591363004352 540 201301915072081 541 842278868238848 542 2485452283923043 543 4909234733857696 544 6199668952527617 545 4909234733857696 546 2485452283923043 547 842278868238848 548 201301915072081 549 35591363004352 550 4847038223171 551 525590073568 552 46626733633 553 3460321376 554 218831107 555 11976256 556 574673 557 24448 558 931 559 32 560 1 561 1 562 33 563 993 564 27061 565 662709 566 14454861 567 277932493 568 4654554633 569 66940339401 570 812968077529 571 8171229107481 572 66335687785533 573 422249317829053 574 2032664638405701 575 7086337847838789 576 17028146983530961 577 26846616451246353 578 26846616451246353 579 17028146983530961 580 7086337847838789 581 2032664638405701 582 422249317829053 583 66335687785533 584 8171229107481 585 812968077529 586 66940339401 587 4654554633 588 277932493 589 14454861 590 662709 591 27061 592 993 593 33 594 1 595 1 596 34 597 1057 598 29854 599 760501 600 17328226 601 349790029 602 6186372382 603 94622910409 604 1232608680226 605 13427129843161 606 119653108240414 607 849345673881277 608 4649589534342754 609 18878242003182661 610 54309931242376606 611 105394372192969489 612 132240988644215842 613 105394372192969489 614 54309931242376606 615 18878242003182661 616 4649589534342754 617 849345673881277 618 119653108240414 619 13427129843161 620 1232608680226 621 94622910409 622 6186372382 623 349790029 624 17328226 625 760501 626 29854 627 1057 628 34 629 1 630 1 631 35 632 1123 633 32833 634 868745 635 20641771 636 436519195 637 8131899833 638 131859347473 639 1835071734835 640 21556810618451 641 209536628422705 642 1645373927307673 643 10138830666120443 644 47335546940862475 645 160604998959958441 646 377844723929464865 647 588633468315403843 648 588633468315403843 649 377844723929464865 650 160604998959958441 651 47335546940862475 652 10138830666120443 653 1645373927307673 654 209536628422705 655 21556810618451 656 1835071734835 657 131859347473 658 8131899833 659 436519195 660 20641771 661 868745 662 32833 663 1123 664 35 665 1 666 1 667 36 668 1191 669 36004 670 988161 671 24444276 672 540488551 673 10580430036 674 181350326529 675 2686677928516 676 33882897420711 677 357235056697476 678 3081211226192641 679 21180324426577044 680 112429800421661031 681 443778629007698356 682 1246803623807490561 683 2380337795595885156 684 2968971263911288999 685 2380337795595885156 686 1246803623807490561 687 443778629007698356 688 112429800421661031 689 21180324426577044 690 3081211226192641 691 357235056697476 692 33882897420711 693 2686677928516 694 181350326529 695 10580430036 696 540488551 697 24444276 698 988161 699 36004 700 1191 701 36 702 1 703 1 704 37 705 1261 706 39373 707 1119493 708 28788001 709 664339177 710 13636064401 711 246405525193 712 3873412055773 713 52233614769061 714 594359973500437 715 5595650767265101 716 42570185481576793 717 254373429747347233 718 1153811833120635481 719 3816483607166825617 720 8803698102396787861 721 13564373693588558173 722 13564373693588558173 723 8803698102396787861 724 3816483607166825617 725 1153811833120635481 726 254373429747347233 727 42570185481576793 728 5595650767265101 729 594359973500437 730 52233614769061 731 3873412055773 732 246405525193 733 13636064401 734 664339177 735 28788001 736 1119493 737 39373 738 1261 739 37 740 1 741 1 742 38 743 1333 744 42946 745 1263509 746 33728806 747 811004833 748 17419484258 749 331048965481 750 5505564994534 751 79100394054221 752 967071845128258 753 9882471447634813 754 82625931422081126 755 550897971719425849 756 2840258839445550946 757 10916941671289999313 758 29999359707124127398 759 56410454014314490981 760 69974827707903049154 761 56410454014314490981 762 29999359707124127398 763 10916941671289999313 764 2840258839445550946 765 550897971719425849 766 82625931422081126 767 9882471447634813 768 967071845128258 769 79100394054221 770 5505564994534 771 331048965481 772 17419484258 773 811004833 774 33728806 775 1263509 776 42946 777 1333 778 38 779 1 780 1 781 39 782 1407 783 46729 784 1421001 785 39326271 786 983732839 787 22069858497 788 440137480689 789 7723214721271 790 117834514611951 791 1541641607587929 792 17014791129640057 793 155369391396527439 794 1146880568461500951 795 6655860285655759441 796 29377931001220167009 797 94879581028960162887 798 214877019857456672479 799 327697927886085654441 800 327697927886085654441 801 214877019857456672479 802 94879581028960162887 803 29377931001220167009 804 6655860285655759441 805 1146880568461500951 806 155369391396527439 807 17014791129640057 808 1541641607587929 809 117834514611951 810 7723214721271 811 440137480689 812 22069858497 813 983732839 814 39326271 815 1421001 816 46729 817 1407 818 39 819 1 820 1 821 40 822 1483 823 50728 824 1592785 825 45643816 826 1186105675 827 27746892328 828 579493354753 829 10702655410600 830 172890164557291 831 2411745942184360 832 28619653271179153 833 283841520215780008 834 2303643608370636715 835 14919329861447147176 836 74822072432348982145 837 280467589440890151208 838 754865494585690965643 839 1399496554158060983080 840 1727194482044146637521 841 1399496554158060983080 842 754865494585690965643 843 280467589440890151208 844 74822072432348982145 845 14919329861447147176 846 2303643608370636715 847 283841520215780008 848 28619653271179153 849 2411745942184360 850 172890164557291 851 10702655410600 852 579493354753 853 27746892328 854 1186105675 855 45643816 856 1592785 857 50728 858 1483 859 40 860 1 861 1 862 41 863 1561 864 54949 865 1779701 866 52748821 867 1422063301 868 34633022201 869 756052222729 870 14663892736801 871 250122311770001 872 3707925602915821 873 47119352562234301 874 505033804901100749 875 4478815087922020861 876 32122538388369661441 877 181315837002841133201 878 779892416461632990361 879 2462697953106973897609 880 5482159931449737760181 881 8281153039765859726341 882 8281153039765859726341 883 5482159931449737760181 884 2462697953106973897609 885 779892416461632990361 886 181315837002841133201 887 32122538388369661441 888 4478815087922020861 889 505033804901100749 890 47119352562234301 891 3707925602915821 892 250122311770001 893 14663892736801 894 756052222729 895 34633022201 896 1422063301 897 52748821 898 1779701 899 54949 900 1561 901 41 902 1 903 1 904 42 905 1641 906 59398 907 1982613 908 60712746 909 1695926197 910 42935761926 911 978027361353 912 19879332929578 913 357148865876001 914 5609717413046022 915 76060303868446621 916 877089297426429738 917 8452596370942940973 918 66677192513929212166 919 420025114785995488017 920 2051867647811565686826 921 7511114563042996619353 922 19824604328577866107398 923 36271084122927079387941 924 44552237162692939114282 925 36271084122927079387941 926 19824604328577866107398 927 7511114563042996619353 928 2051867647811565686826 929 420025114785995488017 930 66677192513929212166 931 8452596370942940973 932 877089297426429738 933 76060303868446621 934 5609717413046022 935 357148865876001 936 19879332929578 937 978027361353 938 42935761926 939 1695926197 940 60712746 941 1982613 942 59398 943 1641 944 42 945 1 946 1 947 43 948 1723 949 64081 950 2202409 951 69611251 952 2012419123 953 52890205033 954 1255091538961 955 26683802934139 956 503787793244011 957 8361062842516033 958 120555411103436473 959 1489640880735475651 960 15523069639558351459 961 133859418832759525081 962 933985728999910071073 963 5134236876859864951243 964 21549178059352390445851 965 66615865437610370161969 966 145914282751921834591561 967 218456450997775993367443 968 218456450997775993367443 969 145914282751921834591561 970 66615865437610370161969 971 21549178059352390445851 972 5134236876859864951243 973 933985728999910071073 974 133859418832759525081 975 15523069639558351459 976 1489640880735475651 977 120555411103436473 978 8361062842516033 979 503787793244011 980 26683802934139 981 1255091538961 982 52890205033 983 2012419123 984 69611251 985 2202409 986 64081 987 1723 988 43 989 1 990 1 991 44 992 1807 993 69004 994 2440001 995 79524316 996 2376695599 997 64761688412 998 1598577634369 999 35486049186316 1000 702581122539791 1001 12289700367152044 1002 187872020059988737 1003 2478424831025281724 1004 27802319803528367791 1005 260648364396903639676 1006 2000820809222777465729 1007 12274663828221788247532 1008 58482795719960572808719 1009 209327042135427305929676 1010 542406369323479156739521 1011 980149217579244660514204 1012 1198605668577020653881647 1013 980149217579244660514204 1014 542406369323479156739521 1015 209327042135427305929676 1016 58482795719960572808719 1017 12274663828221788247532 1018 2000820809222777465729 1019 260648364396903639676 1020 27802319803528367791 1021 2478424831025281724 1022 187872020059988737 1023 12289700367152044 1024 702581122539791 1025 35486049186316 1026 1598577634369 1027 64761688412 1028 2376695599 1029 79524316 1030 2440001 1031 69004 1032 1807 1033 44 1034 1 1035 1 1036 45 1037 1893 1038 74173 1039 2696325 1040 90536361 1041 2794363105 1042 78848622273 1043 2021699274633 1044 46781873036965 1045 969419151881181 1046 17831366092836165 1047 288204774170181133 1048 4045645175369955873 1049 48657292133825026905 1050 493494408990278911561 1051 4142571510546929867025 1052 28152421221220259455773 1053 150899059503438141931093 1054 618761425263122724400845 1055 1874723678075686559978901 1056 4044349155369603186936985 1057 6004647590528092507965393 1058 6004647590528092507965393 1059 4044349155369603186936985 1060 1874723678075686559978901 1061 618761425263122724400845 1062 150899059503438141931093 1063 28152421221220259455773 1064 4142571510546929867025 1065 493494408990278911561 1066 48657292133825026905 1067 4045645175369955873 1068 288204774170181133 1069 17831366092836165 1070 969419151881181 1071 46781873036965 1072 2021699274633 1073 78848622273 1074 2794363105 1075 90536361 1076 2696325 1077 74173 1078 1893 1079 45 1080 1 1081 1 1082 46 1083 1981 1084 79594 1085 2972341 1086 102736366 1087 3271509001 1088 95485491466 1089 2539792781929 1090 61169071746286 1091 1324279643744341 1092 25559758440773866 1093 435681178576005661 1094 6487981436149809454 1095 83355239768178971041 1096 910529206043204428426 1097 8312945340897388101841 1098 62166374978007476373166 1099 371843008411430330386669 1100 1729934543942373607766506 1101 6061264520784232678572421 1102 15434882911162665478466926 1103 27567930377271475039277881 1104 33572577967799567547243274 1105 27567930377271475039277881 1106 15434882911162665478466926 1107 6061264520784232678572421 1108 1729934543942373607766506 1109 371843008411430330386669 1110 62166374978007476373166 1111 8312945340897388101841 1112 910529206043204428426 1113 83355239768178971041 1114 6487981436149809454 1115 435681178576005661 1116 25559758440773866 1117 1324279643744341 1118 61169071746286 1119 2539792781929 1120 95485491466 1121 3271509001 1122 102736366 1123 2972341 1124 79594 1125 1981 1126 46 1127 1 1128 1 1129 47 1130 2071 1131 85273 1132 3269033 1133 116217991 1134 3814727167 1135 115046033201 1136 3170581760113 1137 79364365217983 1138 1792098374113991 1139 36223369111466857 1140 649657571690039641 1141 10234643500362164183 1142 139994272223358353263 1143 1640388588050579832001 1144 16208855884741850686817 1145 132590090657305284112591 1146 878586590393395000590583 1147 4597016674507698304457273 1148 18436493026046687166589321 1149 54804080150752083238023847 1150 116543611795402745151891551 1151 171679472549945695230447313 1152 171679472549945695230447313 1153 116543611795402745151891551 1154 54804080150752083238023847 1155 18436493026046687166589321 1156 4597016674507698304457273 1157 878586590393395000590583 1158 132590090657305284112591 1159 16208855884741850686817 1160 1640388588050579832001 1161 139994272223358353263 1162 10234643500362164183 1163 649657571690039641 1164 36223369111466857 1165 1792098374113991 1166 79364365217983 1167 3170581760113 1168 115046033201 1169 3814727167 1170 116217991 1171 3269033 1172 85273 1173 2071 1174 47 1175 1 1176 1 1177 48 1178 2163 1179 91216 1180 3587409 1181 131079696 1182 4431145363 1183 137946596208 1184 3934465691841 1185 102222500255344 1186 2403789091576851 1187 50790445192654608 1188 956374672979326033 1189 15898498821850237776 1190 230826012329455685619 1191 2890717184573264397616 1192 30777323181433121541633 1193 273910161452560881843888 1194 1997581339997529575307571 1195 11662033834324874581803984 1196 53035183904894159321919441 1197 182090635087220969488044688 1198 456111035840981385678163923 1199 805741871227189621133838576 1200 977421343777135316364285889 1201 805741871227189621133838576 1202 456111035840981385678163923 1203 182090635087220969488044688 1204 53035183904894159321919441 1205 11662033834324874581803984 1206 1997581339997529575307571 1207 273910161452560881843888 1208 30777323181433121541633 1209 2890717184573264397616 1210 230826012329455685619 1211 15898498821850237776 1212 956374672979326033 1213 50790445192654608 1214 2403789091576851 1215 102222500255344 1216 3934465691841 1217 137946596208 1218 4431145363 1219 131079696 1220 3587409 1221 91216 1222 2163 1223 48 1224 1 1225 1 1226 49 1227 2257 1228 97429 1229 3928501 1230 147424861 1231 5128453309 1232 164649686377 1233 4854833957449 1234 130757736096361 1235 3197432743756681 1236 70503527307908509 1237 1391055102316928317 1238 24344047253820753109 1239 374111021334525984181 1240 4990631267923639696561 1241 57023540590242398853649 1242 549460711493172343519777 1243 4384202971829024689334209 1244 28355179051799379593025061 1245 144975517395048125411064901 1246 569256988634201399986420429 1247 1661800799157527216914688557 1248 3486244942521452759627344249 1249 5097728684975832001895021401 1250 5097728684975832001895021401 1251 3486244942521452759627344249 1252 1661800799157527216914688557 1253 569256988634201399986420429 1254 144975517395048125411064901 1255 28355179051799379593025061 1256 4384202971829024689334209 1257 549460711493172343519777 1258 57023540590242398853649 1259 4990631267923639696561 1260 374111021334525984181 1261 24344047253820753109 1262 1391055102316928317 1263 70503527307908509 1264 3197432743756681 1265 130757736096361 1266 4854833957449 1267 164649686377 1268 5128453309 1269 147424861 1270 3928501 1271 97429 1272 2257 1273 49 1274 1