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