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