1 1 2 1 3 1 4 2 5 2 6 4 7 3 8 3 9 6 10 9 11 5 12 5 13 10 14 15 15 25 16 8 17 8 18 16 19 24 20 40 21 64 22 13 23 13 24 26 25 39 26 65 27 104 28 169 29 21 30 21 31 42 32 63 33 105 34 168 35 273 36 441 37 34 38 34 39 68 40 102 41 170 42 272 43 442 44 714 45 1156 46 55 47 55 48 110 49 165 50 275 51 440 52 715 53 1155 54 1870 55 3025 56 89 57 89 58 178 59 267 60 445 61 712 62 1157 63 1869 64 3026 65 4895 66 7921 67 144 68 144 69 288 70 432 71 720 72 1152 73 1872 74 3024 75 4896 76 7920 77 12816 78 20736 79 233 80 233 81 466 82 699 83 1165 84 1864 85 3029 86 4893 87 7922 88 12815 89 20737 90 33552 91 54289 92 377 93 377 94 754 95 1131 96 1885 97 3016 98 4901 99 7917 100 12818 101 20735 102 33553 103 54288 104 87841 105 142129 106 610 107 610 108 1220 109 1830 110 3050 111 4880 112 7930 113 12810 114 20740 115 33550 116 54290 117 87840 118 142130 119 229970 120 372100 121 987 122 987 123 1974 124 2961 125 4935 126 7896 127 12831 128 20727 129 33558 130 54285 131 87843 132 142128 133 229971 134 372099 135 602070 136 974169 137 1597 138 1597 139 3194 140 4791 141 7985 142 12776 143 20761 144 33537 145 54298 146 87835 147 142133 148 229968 149 372101 150 602069 151 974170 152 1576239 153 2550409 154 2584 155 2584 156 5168 157 7752 158 12920 159 20672 160 33592 161 54264 162 87856 163 142120 164 229976 165 372096 166 602072 167 974168 168 1576240 169 2550408 170 4126648 171 6677056 172 4181 173 4181 174 8362 175 12543 176 20905 177 33448 178 54353 179 87801 180 142154 181 229955 182 372109 183 602064 184 974173 185 1576237 186 2550410 187 4126647 188 6677057 189 10803704 190 17480761 191 6765 192 6765 193 13530 194 20295 195 33825 196 54120 197 87945 198 142065 199 230010 200 372075 201 602085 202 974160 203 1576245 204 2550405 205 4126650 206 6677055 207 10803705 208 17480760 209 28284465 210 45765225 211 10946 212 10946 213 21892 214 32838 215 54730 216 87568 217 142298 218 229866 219 372164 220 602030 221 974194 222 1576224 223 2550418 224 4126642 225 6677060 226 10803702 227 17480762 228 28284464 229 45765226 230 74049690 231 119814916 232 17711 233 17711 234 35422 235 53133 236 88555 237 141688 238 230243 239 371931 240 602174 241 974105 242 1576279 243 2550384 244 4126663 245 6677047 246 10803710 247 17480757 248 28284467 249 45765224 250 74049691 251 119814915 252 193864606 253 313679521 254 28657 255 28657 256 57314 257 85971 258 143285 259 229256 260 372541 261 601797 262 974338 263 1576135 264 2550473 265 4126608 266 6677081 267 10803689 268 17480770 269 28284459 270 45765229 271 74049688 272 119814917 273 193864605 274 313679522 275 507544127 276 821223649 277 46368 278 46368 279 92736 280 139104 281 231840 282 370944 283 602784 284 973728 285 1576512 286 2550240 287 4126752 288 6676992 289 10803744 290 17480736 291 28284480 292 45765216 293 74049696 294 119814912 295 193864608 296 313679520 297 507544128 298 821223648 299 1328767776 300 2149991424 301 75025 302 75025 303 150050 304 225075 305 375125 306 600200 307 975325 308 1575525 309 2550850 310 4126375 311 6677225 312 10803600 313 17480825 314 28284425 315 45765250 316 74049675 317 119814925 318 193864600 319 313679525 320 507544125 321 821223650 322 1328767775 323 2149991425 324 3478759200 325 5628750625 326 121393 327 121393 328 242786 329 364179 330 606965 331 971144 332 1578109 333 2549253 334 4127362 335 6676615 336 10803977 337 17480592 338 28284569 339 45765161 340 74049730 341 119814891 342 193864621 343 313679512 344 507544133 345 821223645 346 1328767778 347 2149991423 348 3478759201 349 5628750624 350 9107509825 351 14736260449 352 196418 353 196418 354 392836 355 589254 356 982090 357 1571344 358 2553434 359 4124778 360 6678212 361 10802990 362 17481202 363 28284192 364 45765394 365 74049586 366 119814980 367 193864566 368 313679546 369 507544112 370 821223658 371 1328767770 372 2149991428 373 3478759198 374 5628750626 375 9107509824 376 14736260450 377 23843770274 378 38580030724 379 317811 380 317811 381 635622 382 953433 383 1589055 384 2542488 385 4131543 386 6674031 387 10805574 388 17479605 389 28285179 390 45764784 391 74049963 392 119814747 393 193864710 394 313679457 395 507544167 396 821223624 397 1328767791 398 2149991415 399 3478759206 400 5628750621 401 9107509827 402 14736260448 403 23843770275 404 38580030723 405 62423800998 406 101003831721 407 514229 408 514229 409 1028458 410 1542687 411 2571145 412 4113832 413 6684977 414 10798809 415 17483786 416 28282595 417 45766381 418 74048976 419 119815357 420 193864333 421 313679690 422 507544023 423 821223713 424 1328767736 425 2149991449 426 3478759185 427 5628750634 428 9107509819 429 14736260453 430 23843770272 431 38580030725 432 62423800997 433 101003831722 434 163427632719 435 264431464441 436 832040 437 832040 438 1664080 439 2496120 440 4160200 441 6656320 442 10816520 443 17472840 444 28289360 445 45762200 446 74051560 447 119813760 448 193865320 449 313679080 450 507544400 451 821223480 452 1328767880 453 2149991360 454 3478759240 455 5628750600 456 9107509840 457 14736260440 458 23843770280 459 38580030720 460 62423801000 461 101003831720 462 163427632720 463 264431464440 464 427859097160 465 692290561600 466 1346269 467 1346269 468 2692538 469 4038807 470 6731345 471 10770152 472 17501497 473 28271649 474 45773146 475 74044795 476 119817941 477 193862736 478 313680677 479 507543413 480 821224090 481 1328767503 482 2149991593 483 3478759096 484 5628750689 485 9107509785 486 14736260474 487 23843770259 488 38580030733 489 62423800992 490 101003831725 491 163427632717 492 264431464442 493 427859097159 494 692290561601 495 1120149658760 496 1812440220361 497 2178309 498 2178309 499 4356618 500 6534927 501 10891545 502 17426472 503 28318017 504 45744489 505 74062506 506 119806995 507 193869501 508 313676496 509 507545997 510 821222493 511 1328768490 512 2149990983 513 3478759473 514 5628750456 515 9107509929 516 14736260385 517 23843770314 518 38580030699 519 62423801013 520 101003831712 521 163427632725 522 264431464437 523 427859097162 524 692290561599 525 1120149658761 526 1812440220360 527 2932589879121 528 4745030099481 529 3524578 530 3524578 531 7049156 532 10573734 533 17622890 534 28196624 535 45819514 536 74016138 537 119835652 538 193851790 539 313687442 540 507539232 541 821226674 542 1328765906 543 2149992580 544 3478758486 545 5628751066 546 9107509552 547 14736260618 548 23843770170 549 38580030788 550 62423800958 551 101003831746 552 163427632704 553 264431464450 554 427859097154 555 692290561604 556 1120149658758 557 1812440220362 558 2932589879120 559 4745030099482 560 7677619978602 561 12422650078084 562 5702887 563 5702887 564 11405774 565 17108661 566 28514435 567 45623096 568 74137531 569 119760627 570 193898158 571 313658785 572 507556943 573 821215728 574 1328772671 575 2149988399 576 3478761070 577 5628749469 578 9107510539 579 14736260008 580 23843770547 581 38580030555 582 62423801102 583 101003831657 584 163427632759 585 264431464416 586 427859097175 587 692290561591 588 1120149658766 589 1812440220357 590 2932589879123 591 4745030099480 592 7677619978603 593 12422650078083 594 20100270056686 595 32522920134769 596 9227465 597 9227465 598 18454930 599 27682395 600 46137325 601 73819720 602 119957045 603 193776765 604 313733810 605 507510575 606 821244385 607 1328754960 608 2149999345 609 3478754305 610 5628753650 611 9107507955 612 14736261605 613 23843769560 614 38580031165 615 62423800725 616 101003831890 617 163427632615 618 264431464505 619 427859097120 620 692290561625 621 1120149658745 622 1812440220370 623 2932589879115 624 4745030099485 625 7677619978600 626 12422650078085 627 20100270056685 628 32522920134770 629 52623190191455 630 85146110326225 631 14930352 632 14930352 633 29860704 634 44791056 635 74651760 636 119442816 637 194094576 638 313537392 639 507631968 640 821169360 641 1328801328 642 2149970688 643 3478772016 644 5628742704 645 9107514720 646 14736257424 647 23843772144 648 38580029568 649 62423801712 650 101003831280 651 163427632992 652 264431464272 653 427859097264 654 692290561536 655 1120149658800 656 1812440220336 657 2932589879136 658 4745030099472 659 7677619978608 660 12422650078080 661 20100270056688 662 32522920134768 663 52623190191456 664 85146110326224 665 137769300517680 666 222915410843904 667 24157817 668 24157817 669 48315634 670 72473451 671 120789085 672 193262536 673 314051621 674 507314157 675 821365778 676 1328679935 677 2150045713 678 3478725648 679 5628771361 680 9107497009 681 14736268370 682 23843765379 683 38580033749 684 62423799128 685 101003832877 686 163427632005 687 264431464882 688 427859096887 689 692290561769 690 1120149658656 691 1812440220425 692 2932589879081 693 4745030099506 694 7677619978587 695 12422650078093 696 20100270056680 697 32522920134773 698 52623190191453 699 85146110326226 700 137769300517679 701 222915410843905 702 360684711361584 703 583600122205489 704 39088169 705 39088169 706 78176338 707 117264507 708 195440845 709 312705352 710 508146197 711 820851549 712 1328997746 713 2149849295 714 3478847041 715 5628696336 716 9107543377 717 14736239713 718 23843783090 719 38580022803 720 62423805893 721 101003828696 722 163427634589 723 264431463285 724 427859097874 725 692290561159 726 1120149659033 727 1812440220192 728 2932589879225 729 4745030099417 730 7677619978642 731 12422650078059 732 20100270056701 733 32522920134760 734 52623190191461 735 85146110326221 736 137769300517682 737 222915410843903 738 360684711361585 739 583600122205488 740 944284833567073 741 1527884955772561 742 63245986 743 63245986 744 126491972 745 189737958 746 316229930 747 505967888 748 822197818 749 1328165706 750 2150363524 751 3478529230 752 5628892754 753 9107421984 754 14736314738 755 23843736722 756 38580051460 757 62423788182 758 101003839642 759 163427627824 760 264431467466 761 427859095290 762 692290562756 763 1120149658046 764 1812440220802 765 2932589878848 766 4745030099650 767 7677619978498 768 12422650078148 769 20100270056646 770 32522920134794 771 52623190191440 772 85146110326234 773 137769300517674 774 222915410843908 775 360684711361582 776 583600122205490 777 944284833567072 778 1527884955772562 779 2472169789339634 780 4000054745112196 781 102334155 782 102334155 783 204668310 784 307002465 785 511670775 786 818673240 787 1330344015 788 2149017255 789 3479361270 790 5628378525 791 9107739795 792 14736118320 793 23843858115 794 38579976435 795 62423834550 796 101003810985 797 163427645535 798 264431456520 799 427859102055 800 692290558575 801 1120149660630 802 1812440219205 803 2932589879835 804 4745030099040 805 7677619978875 806 12422650077915 807 20100270056790 808 32522920134705 809 52623190191495 810 85146110326200 811 137769300517695 812 222915410843895 813 360684711361590 814 583600122205485 815 944284833567075 816 1527884955772560 817 2472169789339635 818 4000054745112195 819 6472224534451830 820 10472279279564025 821 165580141 822 165580141 823 331160282 824 496740423 825 827900705 826 1324641128 827 2152541833 828 3477182961 829 5629724794 830 9106907755 831 14736632549 832 23843540304 833 38580172853 834 62423713157 835 101003886010 836 163427599167 837 264431485177 838 427859084344 839 692290569521 840 1120149653865 841 1812440223386 842 2932589877251 843 4745030100637 844 7677619977888 845 12422650078525 846 20100270056413 847 32522920134938 848 52623190191351 849 85146110326289 850 137769300517640 851 222915410843929 852 360684711361569 853 583600122205498 854 944284833567067 855 1527884955772565 856 2472169789339632 857 4000054745112197 858 6472224534451829 859 10472279279564026 860 16944503814015855 861 27416783093579881 862 267914296 863 267914296 864 535828592 865 803742888 866 1339571480 867 2143314368 868 3482885848 869 5626200216 870 9109086064 871 14735286280 872 23844372344 873 38579658624 874 62424030968 875 101003689592 876 163427720560 877 264431410152 878 427859130712 879 692290540864 880 1120149671576 881 1812440212440 882 2932589884016 883 4745030096456 884 7677619980472 885 12422650076928 886 20100270057400 887 32522920134328 888 52623190191728 889 85146110326056 890 137769300517784 891 222915410843840 892 360684711361624 893 583600122205464 894 944284833567088 895 1527884955772552 896 2472169789339640 897 4000054745112192 898 6472224534451832 899 10472279279564024 900 16944503814015856 901 27416783093579880 902 44361286907595736 903 71778070001175616 904 433494437 905 433494437 906 866988874 907 1300483311 908 2167472185 909 3467955496 910 5635427681 911 9103383177 912 14738810858 913 23842194035 914 38581004893 915 62423198928 916 101004203821 917 163427402749 918 264431606570 919 427859009319 920 692290615889 921 1120149625208 922 1812440241097 923 2932589866305 924 4745030107402 925 7677619973707 926 12422650081109 927 20100270054816 928 32522920135925 929 52623190190741 930 85146110326666 931 137769300517407 932 222915410844073 933 360684711361480 934 583600122205553 935 944284833567033 936 1527884955772586 937 2472169789339619 938 4000054745112205 939 6472224534451824 940 10472279279564029 941 16944503814015853 942 27416783093579882 943 44361286907595735 944 71778070001175617 945 116139356908771352 946 187917426909946969 947 701408733 948 701408733 949 1402817466 950 2104226199 951 3507043665 952 5611269864 953 9118313529 954 14729583393 955 23847896922 956 38577480315 957 62425377237 958 101002857552 959 163428234789 960 264431092341 961 427859327130 962 692290419471 963 1120149746601 964 1812440166072 965 2932589912673 966 4745030078745 967 7677619991418 968 12422650070163 969 20100270061581 970 32522920131744 971 52623190193325 972 85146110325069 973 137769300518394 974 222915410843463 975 360684711361857 976 583600122205320 977 944284833567177 978 1527884955772497 979 2472169789339674 980 4000054745112171 981 6472224534451845 982 10472279279564016 983 16944503814015861 984 27416783093579877 985 44361286907595738 986 71778070001175615 987 116139356908771353 988 187917426909946968 989 304056783818718321 990 491974210728665289 991 1134903170 992 1134903170 993 2269806340 994 3404709510 995 5674515850 996 9079225360 997 14753741210 998 23832966570 999 38586707780 1000 62419674350 1001 101006382130 1002 163426056480 1003 264432438610 1004 427858495090 1005 692290933700 1006 1120149428790 1007 1812440362490 1008 2932589791280 1009 4745030153770 1010 7677619945050 1011 12422650098820 1012 20100270043870 1013 32522920142690 1014 52623190186560 1015 85146110329250 1016 137769300515810 1017 222915410845060 1018 360684711360870 1019 583600122205930 1020 944284833566800 1021 1527884955772730 1022 2472169789339530 1023 4000054745112260 1024 6472224534451790 1025 10472279279564050 1026 16944503814015840 1027 27416783093579890 1028 44361286907595730 1029 71778070001175620 1030 116139356908771350 1031 187917426909946970 1032 304056783818718320 1033 491974210728665290 1034 796030994547383610 1035 1288005205276048900 1036 1836311903 1037 1836311903 1038 3672623806 1039 5508935709 1040 9181559515 1041 14690495224 1042 23872054739 1043 38562549963 1044 62434604702 1045 100997154665 1046 163431759367 1047 264428914032 1048 427860673399 1049 692289587431 1050 1120150260830 1051 1812439848261 1052 2932590109091 1053 4745029957352 1054 7677620066443 1055 12422650023795 1056 20100270090238 1057 32522920114033 1058 52623190204271 1059 85146110318304 1060 137769300522575 1061 222915410840879 1062 360684711363454 1063 583600122204333 1064 944284833567787 1065 1527884955772120 1066 2472169789339907 1067 4000054745112027 1068 6472224534451934 1069 10472279279563961 1070 16944503814015895 1071 27416783093579856 1072 44361286907595751 1073 71778070001175607 1074 116139356908771358 1075 187917426909946965 1076 304056783818718323 1077 491974210728665288 1078 796030994547383611 1079 1288005205276048899 1080 2084036199823432510 1081 3372041405099481409 1082 2971215073 1083 2971215073 1084 5942430146 1085 8913645219 1086 14856075365 1087 23769720584 1088 38625795949 1089 62395516533 1090 101021312482 1091 163416829015 1092 264438141497 1093 427854970512 1094 692293112009 1095 1120148082521 1096 1812441194530 1097 2932589277051 1098 4745030471581 1099 7677619748632 1100 12422650220213 1101 20100269968845 1102 32522920189058 1103 52623190157903 1104 85146110346961 1105 137769300504864 1106 222915410851825 1107 360684711356689 1108 583600122208514 1109 944284833565203 1110 1527884955773717 1111 2472169789338920 1112 4000054745112637 1113 6472224534451557 1114 10472279279564194 1115 16944503814015751 1116 27416783093579945 1117 44361286907595696 1118 71778070001175641 1119 116139356908771337 1120 187917426909946978 1121 304056783818718315 1122 491974210728665293 1123 796030994547383608 1124 1288005205276048901 1125 2084036199823432509 1126 3372041405099481410 1127 5456077604922913919 1128 8828119010022395329 1129 4807526976 1130 4807526976 1131 9615053952 1132 14422580928 1133 24037634880 1134 38460215808 1135 62497850688 1136 100958066496 1137 163455917184 1138 264413983680 1139 427869900864 1140 692283884544 1141 1120153785408 1142 1812437669952 1143 2932591455360 1144 4745029125312 1145 7677620580672 1146 12422649705984 1147 20100270286656 1148 32522919992640 1149 52623190279296 1150 85146110271936 1151 137769300551232 1152 222915410823168 1153 360684711374400 1154 583600122197568 1155 944284833571968 1156 1527884955769536 1157 2472169789341504 1158 4000054745111040 1159 6472224534452544 1160 10472279279563584 1161 16944503814016128 1162 27416783093579712 1163 44361286907595840 1164 71778070001175552 1165 116139356908771392 1166 187917426909946944 1167 304056783818718336 1168 491974210728665280 1169 796030994547383616 1170 1288005205276048896 1171 2084036199823432512 1172 3372041405099481408 1173 5456077604922913920 1174 8828119010022395328 1175 14284196614945309248 1176 23112315624967704576 1177 7778742049 1178 7778742049 1179 15557484098 1180 23336226147 1181 38893710245 1182 62229936392 1183 101123646637 1184 163353583029 1185 264477229666 1186 427830812695 1187 692308042361 1188 1120138855056 1189 1812446897417 1190 2932585752473 1191 4745032649890 1192 7677618402363 1193 12422651052253 1194 20100269454616 1195 32522920506869 1196 52623189961485 1197 85146110468354 1198 137769300429839 1199 222915410898193 1200 360684711328032 1201 583600122226225 1202 944284833554257 1203 1527884955780482 1204 2472169789334739 1205 4000054745115221 1206 6472224534449960 1207 10472279279565181 1208 16944503814015141 1209 27416783093580322 1210 44361286907595463 1211 71778070001175785 1212 116139356908771248 1213 187917426909947033 1214 304056783818718281 1215 491974210728665314 1216 796030994547383595 1217 1288005205276048909 1218 2084036199823432504 1219 3372041405099481413 1220 5456077604922913917 1221 8828119010022395330 1222 14284196614945309247 1223 23112315624967704577 1224 37396512239913013824 1225 60508827864880718401 1226 12586269025 1227 12586269025 1228 25172538050 1229 37758807075 1230 62931345125 1231 100690152200 1232 163621497325 1233 264311649525 1234 427933146850 1235 692244796375 1236 1120177943225 1237 1812422739600 1238 2932600682825 1239 4745023422425 1240 7677624105250 1241 12422647527675 1242 20100271632925 1243 32522919160600 1244 52623190793525 1245 85146109954125 1246 137769300747650 1247 222915410701775 1248 360684711449425 1249 583600122151200 1250 944284833600625 1251 1527884955751825 1252 2472169789352450 1253 4000054745104275 1254 6472224534456725 1255 10472279279561000 1256 16944503814017725 1257 27416783093578725 1258 44361286907596450 1259 71778070001175175 1260 116139356908771625 1261 187917426909946800 1262 304056783818718425 1263 491974210728665225 1264 796030994547383650 1265 1288005205276048875 1266 2084036199823432525 1267 3372041405099481400 1268 5456077604922913925 1269 8828119010022395325 1270 14284196614945309250 1271 23112315624967704575 1272 37396512239913013825 1273 60508827864880718400 1274 97905340104793732225 1275 158414167969674450625