1 1 2 2 3 1 4 3 5 1 6 1 7 5 8 2 9 1 10 1 11 8 12 3 13 1 14 1 15 1 16 13 17 5 18 3 19 1 20 1 21 1 22 21 23 8 24 4 25 2 26 1 27 1 28 1 29 34 30 13 31 6 32 4 33 2 34 1 35 1 36 1 37 55 38 21 39 11 40 6 41 3 42 2 43 1 44 1 45 1 46 89 47 34 48 17 49 9 50 6 51 3 52 2 53 1 54 1 55 1 56 144 57 55 58 27 59 15 60 9 61 5 62 3 63 2 64 1 65 1 66 1 67 233 68 89 69 45 70 25 71 14 72 9 73 5 74 3 75 2 76 1 77 1 78 1 79 377 80 144 81 72 82 40 83 23 84 14 85 8 86 5 87 3 88 2 89 1 90 1 91 1 92 610 93 233 94 116 95 64 96 37 97 22 98 14 99 8 100 5 101 3 102 2 103 1 104 1 105 1 106 987 107 377 108 189 109 104 110 61 111 36 112 22 113 13 114 8 115 5 116 3 117 2 118 1 119 1 120 1 121 1597 122 610 123 305 124 169 125 98 126 58 127 35 128 22 129 13 130 8 131 5 132 3 133 2 134 1 135 1 136 1 137 2584 138 987 139 493 140 273 141 158 142 94 143 57 144 35 145 21 146 13 147 8 148 5 149 3 150 2 151 1 152 1 153 1 154 4181 155 1597 156 799 157 441 158 256 159 153 160 92 161 56 162 35 163 21 164 13 165 8 166 5 167 3 168 2 169 1 170 1 171 1 172 6765 173 2584 174 1292 175 714 176 414 177 247 178 149 179 91 180 56 181 34 182 21 183 13 184 8 185 5 186 3 187 2 188 1 189 1 190 1 191 10946 192 4181 193 2090 194 1156 195 671 196 399 197 241 198 147 199 90 200 56 201 34 202 21 203 13 204 8 205 5 206 3 207 2 208 1 209 1 210 1 211 17711 212 6765 213 3383 214 1870 215 1085 216 646 217 391 218 238 219 146 220 90 221 55 222 34 223 21 224 13 225 8 226 5 227 3 228 2 229 1 230 1 231 1 232 28657 233 10946 234 5473 235 3025 236 1755 237 1045 238 632 239 385 240 236 241 145 242 90 243 55 244 34 245 21 246 13 247 8 248 5 249 3 250 2 251 1 252 1 253 1 254 46368 255 17711 256 8855 257 4895 258 2840 259 1691 260 1022 261 623 262 382 263 235 264 145 265 89 266 55 267 34 268 21 269 13 270 8 271 5 272 3 273 2 274 1 275 1 276 1 277 75025 278 28657 279 14329 280 7921 281 4595 282 2737 283 1654 284 1009 285 618 286 380 287 234 288 145 289 89 290 55 291 34 292 21 293 13 294 8 295 5 296 3 297 2 298 1 299 1 300 1 301 121393 302 46368 303 23184 304 12816 305 7436 306 4428 307 2676 308 1632 309 1000 310 615 311 379 312 234 313 144 314 89 315 55 316 34 317 21 318 13 319 8 320 5 321 3 322 2 323 1 324 1 325 1 326 196418 327 75025 328 37512 329 20736 330 12031 331 7164 332 4330 333 2640 334 1618 335 995 336 613 337 378 338 234 339 144 340 89 341 55 342 34 343 21 344 13 345 8 346 5 347 3 348 2 349 1 350 1 351 1 352 317811 353 121393 354 60697 355 33552 356 19466 357 11592 358 7006 359 4272 360 2619 361 1610 362 992 363 612 364 378 365 233 366 144 367 89 368 55 369 34 370 21 371 13 372 8 373 5 374 3 375 2 376 1 377 1 378 1 379 514229 380 196418 381 98209 382 54289 383 31497 384 18756 385 11337 386 6912 387 4237 388 2605 389 1605 390 990 391 611 392 378 393 233 394 144 395 89 396 55 397 34 398 21 399 13 400 8 401 5 402 3 403 2 404 1 405 1 406 1 407 832040 408 317811 409 158905 410 87841 411 50963 412 30348 413 18343 414 11184 415 6855 416 4215 417 2597 418 1602 419 989 420 611 421 377 422 233 423 144 424 89 425 55 426 34 427 21 428 13 429 8 430 5 431 3 432 2 433 1 434 1 435 1 436 1346269 437 514229 438 257115 439 142129 440 82461 441 49105 442 29679 443 18096 444 11092 445 6821 446 4202 447 2592 448 1600 449 988 450 611 451 377 452 233 453 144 454 89 455 55 456 34 457 21 458 13 459 8 460 5 461 3 462 2 463 1 464 1 465 1 466 2178309 467 832040 468 416020 469 229970 470 133424 471 79453 472 48022 473 29280 474 17947 475 11036 476 6799 477 4194 478 2589 479 1599 480 988 481 610 482 377 483 233 484 144 485 89 486 55 487 34 488 21 489 13 490 8 491 5 492 3 493 2 494 1 495 1 496 1 497 3524578 498 1346269 499 673134 500 372100 501 215884 502 128557 503 77701 504 47377 505 29039 506 17856 507 11001 508 6786 509 4189 510 2587 511 1598 512 988 513 610 514 377 515 233 516 144 517 89 518 55 519 34 520 21 521 13 522 8 523 5 524 3 525 2 526 1 527 1 528 1 529 5702887 530 2178309 531 1089155 532 602070 533 349308 534 208010 535 125723 536 76657 537 46986 538 28892 539 17801 540 10980 541 6778 542 4186 543 2586 544 1598 545 987 546 610 547 377 548 233 549 144 550 89 551 55 552 34 553 21 554 13 555 8 556 5 557 3 558 2 559 1 560 1 561 1 562 9227465 563 3524578 564 1762289 565 974169 566 565192 567 336567 568 203424 569 124033 570 76025 571 46748 572 28802 573 17766 574 10967 575 6773 576 4184 577 2585 578 1598 579 987 580 610 581 377 582 233 583 144 584 89 585 55 586 34 587 21 588 13 589 8 590 5 591 3 592 2 593 1 594 1 595 1 596 14930352 597 5702887 598 2851443 599 1576239 600 914501 601 544577 602 329148 603 200690 604 123011 605 75640 606 46602 607 28746 608 17745 609 10959 610 6770 611 4183 612 2585 613 1597 614 987 615 610 616 377 617 233 618 144 619 89 620 55 621 34 622 21 623 13 624 8 625 5 626 3 627 2 628 1 629 1 630 1 631 24157817 632 9227465 633 4613733 634 2550409 635 1479693 636 881145 637 532572 638 324723 639 199037 640 122388 641 75404 642 46513 643 28712 644 17732 645 10954 646 6768 647 4182 648 2585 649 1597 650 987 651 610 652 377 653 233 654 144 655 89 656 55 657 34 658 21 659 13 660 8 661 5 662 3 663 2 664 1 665 1 666 1 667 39088169 668 14930352 669 7465176 670 4126648 671 2394193 672 1425722 673 861719 674 525413 675 322048 676 198028 677 122006 678 75259 679 46457 680 28691 681 17724 682 10951 683 6767 684 4182 685 2584 686 1597 687 987 688 610 689 377 690 233 691 144 692 89 693 55 694 34 695 21 696 13 697 8 698 5 699 3 700 2 701 1 702 1 703 1 704 63245986 705 24157817 706 12078908 707 6677056 708 3873886 709 2306866 710 1394291 711 850136 712 521084 713 320416 714 197410 715 121771 716 75169 717 46423 718 28678 719 17719 720 10949 721 6766 722 4182 723 2584 724 1597 725 987 726 610 727 377 728 233 729 144 730 89 731 55 732 34 733 21 734 13 735 8 736 5 737 3 738 2 739 1 740 1 741 1 742 102334155 743 39088169 744 19544085 745 10803704 746 6268079 747 3732588 748 2256010 749 1375549 750 843132 751 518444 752 319416 753 197030 754 121627 755 75114 756 46402 757 28670 758 17716 759 10948 760 6766 761 4181 762 2584 763 1597 764 987 765 610 766 377 767 233 768 144 769 89 770 55 771 34 772 21 773 13 774 8 775 5 776 3 777 2 778 1 779 1 780 1 781 165580141 782 63245986 783 31622993 784 17480761 785 10141966 786 6039454 787 3650301 788 2225686 789 1364216 790 838861 791 516826 792 318801 793 196796 794 121537 795 75080 796 46389 797 28665 798 17714 799 10947 800 6766 801 4181 802 2584 803 1597 804 987 805 610 806 377 807 233 808 144 809 89 810 55 811 34 812 21 813 13 814 8 815 5 816 3 817 2 818 1 819 1 820 1 821 267914296 822 102334155 823 51167077 824 28284465 825 16410045 826 9772042 827 5906311 828 3601235 829 2207348 830 1357305 831 836242 832 515831 833 318422 834 196651 835 121482 836 75059 837 46381 838 28662 839 17713 840 10947 841 6765 842 4181 843 2584 844 1597 845 987 846 610 847 377 848 233 849 144 850 89 851 55 852 34 853 21 854 13 855 8 856 5 857 3 858 2 859 1 860 1 861 1 862 433494437 863 165580141 864 82790071 865 45765225 866 26552010 867 15811497 868 9556613 869 5826920 870 3571564 871 2196165 872 1353068 873 834632 874 515218 875 318189 876 196562 877 121448 878 75046 879 46376 880 28660 881 17712 882 10947 883 6765 884 4181 885 2584 886 1597 887 987 888 610 889 377 890 233 891 144 892 89 893 55 894 34 895 21 896 13 897 8 898 5 899 3 900 2 901 1 902 1 903 1 904 701408733 905 267914296 906 133957148 907 74049690 908 42962055 909 25583539 910 15462924 911 9428155 912 5778912 913 3553470 914 2189310 915 1350463 916 833640 917 514840 918 318044 919 196507 920 121427 921 75038 922 46373 923 28659 924 17712 925 10946 926 6765 927 4181 928 2584 929 1597 930 987 931 610 932 377 933 233 934 144 935 89 936 55 937 34 938 21 939 13 940 8 941 5 942 3 943 2 944 1 945 1 946 1 947 1134903170 948 433494437 949 216747218 950 119814916 951 69514065 952 41395035 953 25019536 954 15255075 955 9350476 956 5749635 957 3542379 958 2185095 959 1348858 960 833028 961 514606 962 317955 963 196473 964 121414 965 75033 966 46371 967 28658 968 17712 969 10946 970 6765 971 4181 972 2584 973 1597 974 987 975 610 976 377 977 233 978 144 979 89 980 55 981 34 982 21 983 13 984 8 985 5 986 3 987 2 988 1 989 1 990 1 991 1836311903 992 701408733 993 350704367 994 193864606 995 112476121 996 66978574 997 40482460 998 24683230 999 15129389 1000 9303105 1001 5731689 1002 3535558 1003 2182498 1004 1347868 1005 832651 1006 514462 1007 317900 1008 196452 1009 121406 1010 75030 1011 46370 1012 28658 1013 17711 1014 10946 1015 6765 1016 4181 1017 2584 1018 1597 1019 987 1020 610 1021 377 1022 233 1023 144 1024 89 1025 55 1026 34 1027 21 1028 13 1029 8 1030 5 1031 3 1032 2 1033 1 1034 1 1035 1 1036 2971215073 1037 1134903170 1038 567451585 1039 313679521 1040 181990186 1041 108373609 1042 65501996 1043 39938305 1044 24479865 1045 15052740 1046 9274067 1047 5720653 1048 3531356 1049 2180896 1050 1347257 1051 832417 1052 514373 1053 317866 1054 196439 1055 121401 1056 75028 1057 46369 1058 28658 1059 17711 1060 10946 1061 6765 1062 4181 1063 2584 1064 1597 1065 987 1066 610 1067 377 1068 233 1069 144 1070 89 1071 55 1072 34 1073 21 1074 13 1075 8 1076 5 1077 3 1078 2 1079 1 1080 1 1081 1 1082 4807526976 1083 1836311903 1084 918155951 1085 507544127 1086 294466306 1087 175352183 1088 105984456 1089 64621535 1090 39609253 1091 24355845 1092 15005756 1093 9256211 1094 5713854 1095 3528764 1096 2179907 1097 1346879 1098 832273 1099 514318 1100 317845 1101 196431 1102 121398 1103 75027 1104 46369 1105 28657 1106 17711 1107 10946 1108 6765 1109 4181 1110 2584 1111 1597 1112 987 1113 610 1114 377 1115 233 1116 144 1117 89 1118 55 1119 34 1120 21 1121 13 1122 8 1123 5 1124 3 1125 2 1126 1 1127 1 1128 1 1129 7778742049 1130 2971215073 1131 1485607537 1132 821223649 1133 476456492 1134 283725793 1135 171486452 1136 104559841 1137 64089118 1138 39408585 1139 24279823 1140 14976865 1141 9245210 1142 5709660 1143 3527164 1144 2179297 1145 1346646 1146 832184 1147 514284 1148 317832 1149 196426 1150 121396 1151 75026 1152 46369 1153 28657 1154 17711 1155 10946 1156 6765 1157 4181 1158 2584 1159 1597 1160 987 1161 610 1162 377 1163 233 1164 144 1165 89 1166 55 1167 34 1168 21 1169 13 1170 8 1171 5 1172 3 1173 2 1174 1 1175 1 1176 1 1177 12586269025 1178 4807526976 1179 2403763488 1180 1328767776 1181 770922798 1182 459077976 1183 277470909 1184 169181376 1185 103698371 1186 63764430 1187 39285579 1188 24233076 1189 14959064 1190 9238424 1191 5707071 1192 3526176 1193 2178919 1194 1346502 1195 832129 1196 514263 1197 317824 1198 196423 1199 121395 1200 75026 1201 46368 1202 28657 1203 17711 1204 10946 1205 6765 1206 4181 1207 2584 1208 1597 1209 987 1210 610 1211 377 1212 233 1213 144 1214 89 1215 55 1216 34 1217 21 1218 13 1219 8 1220 5 1221 3 1222 2 1223 1 1224 1 1225 1 1226 20365011074 1227 7778742049 1228 3889371024 1229 2149991424 1230 1247379291 1231 742803768 1232 448957361 1233 273741216 1234 167787489 1235 103173016 1236 63565402 1237 39209940 1238 24204274 1239 14948084 1240 9234235 1241 5705472 1242 3525565 1243 2178686 1244 1346413 1245 832095 1246 514250 1247 317819 1248 196421 1249 121394 1250 75026 1251 46368 1252 28657 1253 17711 1254 10946 1255 6765 1256 4181 1257 2584 1258 1597 1259 987 1260 610 1261 377 1262 233 1263 144 1264 89 1265 55 1266 34 1267 21 1268 13 1269 8 1270 5 1271 3 1272 2 1273 1 1274 1 1275 1