1 1 2 2 3 2 4 4 5 5 6 4 7 7 8 13 9 13 10 7 11 11 12 29 13 44 14 29 15 11 16 16 17 53 18 127 19 127 20 53 21 16 22 22 23 85 24 288 25 493 26 288 27 85 28 22 29 29 30 125 31 529 32 1474 33 1474 34 529 35 125 36 29 37 37 38 173 39 850 40 3365 41 6068 42 3365 43 850 44 173 45 37 46 46 47 229 48 1251 49 6211 50 18528 51 18528 52 6211 53 1251 54 229 55 46 56 56 57 293 58 1732 59 10017 60 42738 61 78674 62 42738 63 10017 64 1732 65 293 66 56 67 67 68 365 69 2293 70 14783 71 79563 72 244131 73 244131 74 79563 75 14783 76 2293 77 365 78 67 79 79 80 445 81 2934 82 20509 83 129173 84 569420 85 1056756 86 569420 87 129173 88 20509 89 2934 90 445 91 79 92 92 93 533 94 3655 95 27195 96 191583 97 1070036 98 3320837 99 3320837 100 1070036 101 191583 102 27195 103 3655 104 533 105 92 106 106 107 629 108 4456 109 34841 110 266793 111 1750150 112 7822881 113 14564701 114 7822881 115 1750150 116 266793 117 34841 118 4456 119 629 120 106 121 121 122 733 123 5337 124 43447 125 354803 126 2610438 127 14827629 128 46222275 129 46222275 130 14827629 131 2610438 132 354803 133 43447 134 5337 135 733 136 121 137 137 138 845 139 6298 140 53013 141 455613 142 3650950 143 24422839 144 109796227 145 204666202 146 109796227 147 24422839 148 3650950 149 455613 150 53013 151 6298 152 845 153 137 154 154 155 965 156 7339 157 63539 158 569223 159 4871686 160 36628371 161 209669425 162 654583926 163 654583926 164 209669425 165 36628371 166 4871686 167 569223 168 63539 169 7339 170 965 171 154 172 172 173 1093 174 8460 175 75025 176 695633 177 6272646 178 51446975 179 347528967 180 1565655536 181 2919462498 182 1565655536 183 347528967 184 51446975 185 6272646 186 695633 187 75025 188 8460 189 1093 190 172 191 191 192 1229 193 9661 194 87471 195 834843 196 7853830 197 68878827 198 523851329 199 3008954622 200 9395548782 201 9395548782 202 3008954622 203 523851329 204 68878827 205 7853830 206 834843 207 87471 208 9661 209 1229 210 191 211 211 212 1373 213 10942 214 100877 215 986853 216 9615238 217 88923927 218 738729703 219 5015111608 220 22601899794 221 42143180174 222 22601899794 223 5015111608 224 738729703 225 88923927 226 9615238 227 986853 228 100877 229 10942 230 1373 231 211 232 232 233 1525 234 12303 235 115243 236 1151663 237 11556870 238 111582275 239 992175375 240 7594282816 241 43675471992 242 136317297772 243 136317297772 244 43675471992 245 7594282816 246 992175375 247 111582275 248 11556870 249 1151663 250 115243 251 12303 252 1525 253 232 254 254 255 1685 256 13744 257 130569 258 1329273 259 13678726 260 136853871 261 1284188983 262 10748969866 263 73151641602 264 329511039106 265 614251526864 266 329511039106 267 73151641602 268 10748969866 269 1284188983 270 136853871 271 13678726 272 1329273 273 130569 274 13744 275 1685 276 254 277 277 278 1853 279 15265 280 146855 281 1519683 282 15980806 283 164738715 284 1614770527 285 14479604013 286 111231071625 287 639748311539 288 1995268984323 289 1995268984323 290 639748311539 291 111231071625 292 14479604013 293 1614770527 294 164738715 295 15980806 296 1519683 297 146855 298 15265 299 1853 300 277 301 301 302 2029 303 16866 304 164101 305 1722893 306 18463110 307 195236807 308 1983920007 309 18786231710 310 157972251624 311 1076144680915 312 4842893884876 313 9024782449736 314 4842893884876 315 1076144680915 316 157972251624 317 18786231710 318 1983920007 319 195236807 320 18463110 321 1722893 322 164101 323 16866 324 2029 325 301 326 326 327 2213 328 18547 329 182307 330 1938903 331 21125638 332 228348147 333 2391637423 334 23668855311 335 213387964545 336 1642465123438 337 9441125178417 338 29419638620088 339 29419638620088 340 9441125178417 341 1642465123438 342 213387964545 343 23668855311 344 2391637423 345 228348147 346 21125638 347 1938903 348 182307 349 18547 350 2213 351 326 352 352 353 2405 354 20308 355 201473 356 2167713 357 23968390 358 264072735 359 2837922775 360 29127474816 361 277480181632 362 2339959031659 363 15942304637782 364 71660057925134 365 133489812361806 366 71660057925134 367 15942304637782 368 2339959031659 369 277480181632 370 29127474816 371 2837922775 372 264072735 373 23968390 374 2167713 375 201473 376 20308 377 2405 378 352 379 379 380 2605 381 22149 382 221599 383 2409323 384 26991366 385 302410571 386 3322776063 387 35162090225 388 350249094186 389 3168951492098 390 24414529282159 391 140202658359483 392 436485783911939 393 436485783911939 394 140202658359483 395 24414529282159 396 3168951492098 397 350249094186 398 35162090225 399 3322776063 400 302410571 401 26991366 402 2409323 403 221599 404 22149 405 2605 406 379 407 407 408 2813 409 24070 410 242685 411 2663733 412 30194566 413 343361655 414 3846197287 415 41772701538 416 431694710996 417 4129506387695 418 34882863073746 419 237559093558846 420 1066463516847160 421 1985873221687284 422 1066463516847160 423 237559093558846 424 34882863073746 425 4129506387695 426 431694710996 427 41772701538 428 3846197287 429 343361655 430 30194566 431 2663733 432 242685 433 24070 434 2813 435 407 436 436 437 3029 438 26071 439 264731 440 2930943 441 33577990 442 386925987 443 4408186447 444 48959308755 445 521817032062 446 5221632633488 447 47354771924898 448 364928342002273 449 2093165246310803 450 6510530255469877 451 6510530255469877 452 2093165246310803 453 364928342002273 454 47354771924898 455 5221632633488 456 521817032062 457 48959308755 458 4408186447 459 386925987 460 33577990 461 2930943 462 264731 463 26071 464 3029 465 436 466 466 467 3253 468 28152 469 287737 470 3210953 471 37141638 472 433103567 473 5008743543 474 56721911876 475 620616057384 476 6445331016934 477 61832010877178 478 522790828240018 479 3557584539730824 480 15950145167519640 481 29689739907869581 482 15950145167519640 483 3557584539730824 484 522790828240018 485 61832010877178 486 6445331016934 487 620616057384 488 56721911876 489 5008743543 490 433103567 491 37141638 492 3210953 493 287737 494 28152 495 3253 496 466 497 497 498 3485 499 30313 500 311703 501 3503763 502 40885510 503 481894395 504 5647868575 505 65060510901 506 728091786962 507 7800601571132 508 78314893327439 509 711306088996923 510 5480408603998002 511 31394121017749533 512 97559489731183338 513 97559489731183338 514 31394121017749533 515 5480408603998002 516 711306088996923 517 78314893327439 518 7800601571132 519 728091786962 520 65060510901 521 5647868575 522 481894395 523 40885510 524 3503763 525 311703 526 30313 527 3485 528 497 529 529 530 3725 531 32554 532 336629 533 3809373 534 44809606 535 533298471 536 6325561543 537 73975105830 538 844244220796 539 9287444296082 540 96803459226208 541 930517248969030 542 7870537522283108 543 53506436620273496 544 239582292328224425 545 445797648515664064 546 239582292328224425 547 53506436620273496 548 7870537522283108 549 930517248969030 550 96803459226208 551 9287444296082 552 844244220796 553 73975105830 554 6325561543 555 533298471 556 44809606 557 3809373 558 336629 559 32554 560 3725 561 529 562 562 563 3973 564 34875 565 362515 566 4127783 567 48913926 568 587315795 569 7041822447 570 83465696663 571 969073358886 572 10905859191784 573 117297711812172 574 1180433555869243 575 10731203993762706 576 82638517327849359 577 472754831286476697 578 1467845880160405142 579 1467845880160405142 580 472754831286476697 581 82638517327849359 582 10731203993762706 583 1180433555869243 584 117297711812172 585 10905859191784 586 969073358886 587 83465696663 588 7041822447 589 587315795 590 48913926 591 4127783 592 362515 593 34875 594 3973 595 562 596 596 597 4229 598 37276 599 389361 600 4458993 601 53198470 602 643946367 603 7796651287 604 93532283400 605 1102579201232 606 12655846258238 607 139797651210808 608 1461056523277330 609 14063386218433284 610 118950981054362265 611 807768824329731921 612 3612345143303186828 613 6719243690952576928 614 3612345143303186828 615 807768824329731921 616 118950981054362265 617 14063386218433284 618 1461056523277330 619 139797651210808 620 12655846258238 621 1102579201232 622 93532283400 623 7796651287 624 643946367 625 53198470 626 4458993 627 389361 628 37276 629 4229 630 596 631 631 632 4493 633 39757 634 417167 635 4803003 636 57663238 637 703190187 638 8590048063 639 104174866041 640 1244761747834 641 14537405495444 642 164303277422116 643 1772386328805857 644 17867326286849938 645 162506739030217965 646 1250521883193448618 647 7144280790953581874 648 22163785131858042464 649 22163785131858042464 650 7144280790953581874 651 1250521883193448618 652 162506739030217965 653 17867326286849938 654 1772386328805857 655 164303277422116 656 14537405495444 657 1244761747834 658 104174866041 659 8590048063 660 703190187 661 57663238 662 4803003 663 417167 664 39757 665 4493 666 631 667 667 668 4765 669 42318 670 445933 671 5159813 672 62308230 673 765047255 674 9422012775 675 115393444586 676 1395620998692 677 16550536903402 678 190814590446096 679 2114422985761727 680 22143071935064824 681 213326693661598467 682 1803853783866099419 683 12235034918217547048 684 54648788400216829912 685 101617229522091242276 686 54648788400216829912 687 12235034918217547048 688 1803853783866099419 689 213326693661598467 690 22143071935064824 691 2114422985761727 692 190814590446096 693 16550536903402 694 1395620998692 695 115393444586 696 9422012775 697 765047255 698 62308230 699 5159813 700 445933 701 42318 702 4765 703 667 704 704 705 5045 706 44959 707 475659 708 5529423 709 67133446 710 829517571 711 10292545423 712 127188019035 713 1555156953806 714 18695240482112 715 219331590282748 716 2487166494623133 717 26890630375727867 718 271416655635995835 719 2468950914177598377 720 18982628769907428426 721 108303820749354046348 722 335728950976923551284 723 335728950976923551284 724 108303820749354046348 725 18982628769907428426 726 2468950914177598377 727 271416655635995835 728 26890630375727867 729 2487166494623133 730 219331590282748 731 18695240482112 732 1555156953806 733 127188019035 734 10292545423 735 829517571 736 67133446 737 5529423 738 475659 739 44959 740 5045 741 704 742 742 743 5333 744 47680 745 506345 746 5911833 747 72138886 748 896601135 749 11201646007 750 139558589388 751 1723369613176 752 20971516231574 753 249854276932072 754 2890616855390075 755 32110002393024366 756 336777951308867846 757 3246239865009580151 758 27436456080054583216 759 185866268423916727928 760 829223491584368158240 761 1541423048634562372900 762 829223491584368158240 763 185866268423916727928 764 27436456080054583216 765 3246239865009580151 766 336777951308867846 767 32110002393024366 768 2890616855390075 769 249854276932072 770 20971516231574 771 1723369613176 772 139558589388 773 11201646007 774 896601135 775 72138886 776 5911833 777 506345 778 47680 779 5333 780 742 781 781 782 5629 783 50481 784 537991 785 6307043 786 77324550 787 966297947 788 12149314527 789 152505155645 790 1900258976802 791 23379364151788 792 282382650394068 793 3324774068062553 794 37801188041571938 795 409410822775087443 796 4135851265497696132 797 37618337601132353408 798 288952675325806766014 799 1646445956960970469946 800 5100007469620149879826 801 5100007469620149879826 802 1646445956960970469946 803 288952675325806766014 804 37618337601132353408 805 4135851265497696132 806 409410822775087443 807 37801188041571938 808 3324774068062553 809 282382650394068 810 23379364151788 811 1900258976802 812 152505155645 813 12149314527 814 966297947 815 77324550 816 6307043 817 537991 818 50481 819 5629 820 781 821 821 822 5933 823 53362 824 570597 825 6715053 826 82690438 827 1038608007 828 13135550983 829 166027717806 830 2085825044684 831 25918784242754 832 316916710668736 833 3789638132640567 834 43964187323200854 835 489315304008438960 836 5137818705051297909 837 49536670046053613678 838 418410885704048303380 839 2830996255907042913226 840 12616232060752224419348 841 23445043369786171596304 842 12616232060752224419348 843 2830996255907042913226 844 418410885704048303380 845 49536670046053613678 846 5137818705051297909 847 489315304008438960 848 43964187323200854 849 3789638132640567 850 316916710668736 851 25918784242754 852 2085825044684 853 166027717806 854 13135550983 855 1038608007 856 82690438 857 6715053 858 570597 859 53362 860 5933 861 821 862 862 863 6245 864 56323 865 604163 866 7135863 867 88236550 868 1113531315 869 14160355375 870 180126275871 871 2280067816822 872 28589776504472 873 353456457756076 874 4285209049124117 875 50599000237911114 876 576491398450225223 877 6252149299319658463 878 63194244406778574404 879 574634220329714479388 880 4409366070871309622944 881 25092701704765366431598 882 77672500575482038191344 883 77672500575482038191344 884 25092701704765366431598 885 4409366070871309622944 886 574634220329714479388 887 63194244406778574404 888 6252149299319658463 889 576491398450225223 890 50599000237911114 891 4285209049124117 892 353456457756076 893 28589776504472 894 2280067816822 895 180126275871 896 14160355375 897 1113531315 898 88236550 899 7135863 900 604163 901 56323 902 6245 903 862 904 904 905 6565 906 59364 907 638689 908 7569473 909 93962886 910 1191067871 911 15223727703 912 194800829840 913 2482987293216 914 31392340936942 915 392001891656088 916 4811486817513203 917 57705626785702718 918 670939106324391091 919 7478844257399141209 920 78591853360488353494 921 757783221346771971952 922 6395951932638564651080 923 43222308876711578646472 924 192416133622181885302612 925 357471463810438256236844 926 192416133622181885302612 927 43222308876711578646472 928 6395951932638564651080 929 757783221346771971952 930 78591853360488353494 931 7478844257399141209 932 670939106324391091 933 57705626785702718 934 4811486817513203 935 392001891656088 936 31392340936942 937 2482987293216 938 194800829840 939 15223727703 940 1191067871 941 93962886 942 7569473 943 638689 944 59364 945 6565 946 904 947 947 948 6893 949 62485 950 674175 951 8015883 952 99869446 953 1271217675 954 16325667967 955 210051379713 956 2694583473866 957 34326477540164 958 432553012368772 959 5368471437807825 960 65284066966575666 961 772658427637967135 962 8817903737700735392 963 95729686536179500976 964 967915157155144050112 965 8797727281307325594952 966 67436948894279240195288 967 383300293915916549086894 968 1185694907448866770499902 969 1185694907448866770499902 970 383300293915916549086894 971 67436948894279240195288 972 8797727281307325594952 973 967915157155144050112 974 95729686536179500976 975 8817903737700735392 976 772658427637967135 977 65284066966575666 978 5368471437807825 979 432553012368772 980 34326477540164 981 2694583473866 982 210051379713 983 16325667967 984 1271217675 985 99869446 986 8015883 987 674175 988 62485 989 6893 990 947 991 991 992 7229 993 65686 994 710621 995 8475093 996 105956230 997 1353980727 998 17466176167 999 225877925490 1000 2914856358772 1001 37392186314138 1002 475109819894128 1003 5956162910007983 1004 73334320780529958 1005 881649362390953355 1006 10269327755245145887 1007 114607781414227502906 1008 1205047728202774801008 1009 11617689751882499243132 1010 97978896458756914320540 1011 661316903359004522039754 1012 2941098667398882474542688 1013 5462545208610686344468712 1014 2941098667398882474542688 1015 661316903359004522039754 1016 97978896458756914320540 1017 11617689751882499243132 1018 1205047728202774801008 1019 114607781414227502906 1020 10269327755245145887 1021 881649362390953355 1022 73334320780529958 1023 5956162910007983 1024 475109819894128 1025 37392186314138 1026 2914856358772 1027 225877925490 1028 17466176167 1029 1353980727 1030 105956230 1031 8475093 1032 710621 1033 65686 1034 7229 1035 991 1036 1036 1037 7573 1038 68967 1039 748027 1040 8947103 1041 112223238 1042 1439357027 1043 18645252303 1044 242280467171 1045 3143805947934 1046 40589467258864 1047 519672314232156 1048 6574561234113677 1049 81856388227565594 1050 997911910583349751 1051 11833116310949686455 1052 135226143952527930064 1053 1469185622399112600380 1054 14856976586645075951276 1055 134970106978507506313352 1056 1033477010395001871620290 1057 5867223508134512940431236 1058 18138310236987024678564930 1059 18138310236987024678564930 1060 5867223508134512940431236 1061 1033477010395001871620290 1062 134970106978507506313352 1063 14856976586645075951276 1064 1469185622399112600380 1065 135226143952527930064 1066 11833116310949686455 1067 997911910583349751 1068 81856388227565594 1069 6574561234113677 1070 519672314232156 1071 40589467258864 1072 3143805947934 1073 242280467171 1074 18645252303 1075 1439357027 1076 112223238 1077 8947103 1078 748027 1079 68967 1080 7573 1081 1036 1082 1082 1083 7925 1084 72328 1085 786393 1086 9431913 1087 118670470 1088 1527346575 1089 19862896375 1090 259259004756 1091 3381432241352 1092 43918320374342 1093 566240495382856 1094 7223666410124907 1095 90850269307682574 1096 1121446072215156323 1097 13509269404841445967 1098 157584774883127801706 1099 1760329888311504332448 1100 18515965919461185229224 1101 178465466839524360926340 1102 1503827374436551329839098 1103 10138195661806749592248580 1104 45045306115073567411437806 1105 83642530796839406767181186 1106 45045306115073567411437806 1107 10138195661806749592248580 1108 1503827374436551329839098 1109 178465466839524360926340 1110 18515965919461185229224 1111 1760329888311504332448 1112 157584774883127801706 1113 13509269404841445967 1114 1121446072215156323 1115 90850269307682574 1116 7223666410124907 1117 566240495382856 1118 43918320374342 1119 3381432241352 1120 259259004756 1121 19862896375 1122 1527346575 1123 118670470 1124 9431913 1125 786393 1126 72328 1127 7925 1128 1082 1129 1129 1130 8285 1131 75769 1132 825719 1133 9929523 1134 125297926 1135 1617949371