1 1
2 3
3 2
4 7
5 5
6 4
7 16
8 12
9 10
10 6
11 37
12 28
13 23
14 14
15 8
16 84
17 64
18 53
19 32
20 19
21 9
22 191
23 146
24 121
25 73
26 44
27 21
28 11
29 434
30 332
31 275
32 166
33 100
34 48
35 25
36 13
37 985
38 753
39 624
40 377
41 227
42 109
43 57
44 30
45 15
46 2234
47 1708
48 1416
49 856
50 515
51 248
52 130
53 69
54 35
55 17
56 5067
57 3874
58 3212
59 1942
60 1168
61 563
62 295
63 157
64 80
65 39
66 18
67 11492
68 8787
69 7285
70 4405
71 2649
72 1277
73 670
74 357
75 182
76 89
77 41
78 20
79 26064
80 19929
81 16523
82 9991
83 6008
84 2897
85 1520
86 810
87 413
88 202
89 93
90 46
91 22
92 59112
93 45198
94 37474
95 22660
96 13626
97 6571
98 3448
99 1838
100 937
101 459
102 211
103 105
104 50
105 24
106 134064
107 102507
108 84990
109 51392
110 30904
111 14903
112 7820
113 4169
114 2126
115 1041
116 479
117 239
118 114
119 55
120 26
121 304051
122 232481
123 192754
124 116555
125 70089
126 33800
127 17736
128 9456
129 4822
130 2361
131 1087
132 543
133 259
134 125
135 59
136 27
137 689573
138 527256
139 437157
140 264341
141 158959
142 76657
143 40225
144 21446
145 10937
146 5355
147 2466
148 1232
149 588
150 284
151 134
152 62
153 29
154 1563917
155 1195790
156 991450
157 599512
158 360511
159 173855
160 91229
161 48639
162 24805
163 12145
164 5593
165 2795
166 1334
167 645
168 304
169 141
170 66
171 31
172 3546885
173 2711991
174 2248559
175 1359663
176 817621
177 394295
178 206903
179 110311
180 56257
181 27545
182 12685
183 6339
184 3026
185 1463
186 690
187 320
188 150
189 71
190 33
191 8044155
192 6150658
193 5099618
194 3083647
195 1854323
196 894242
197 469246
198 250180
199 127589
200 62471
201 28769
202 14377
203 6863
204 3319
205 1565
206 726
207 341
208 162
209 75
210 34
211 18243735
212 13949380
213 11565675
214 6993555
215 4205511
216 2028096
217 1064227
218 567396
219 289366
220 141682
221 65247
222 32607
223 15565
224 7528
225 3550
226 1647
227 774
228 368
229 171
230 78
231 36
232 41375865
233 31636486
234 26230364
235 15861028
236 9537886
237 4599619
238 2413613
239 1286826
240 656268
241 321328
242 147977
243 73952
244 35301
245 17074
246 8052
247 3736
248 1756
249 835
250 388
251 177
252 82
253 38
254 93838360
255 71749943
256 59489133
257 35972006
258 21631441
259 10431703
260 5473952
261 2918456
262 1488383
263 728756
264 335605
265 167720
266 80061
267 38723
268 18262
269 8474
270 3983
271 1894
272 880
273 402
274 186
275 87
276 40
277 212820633
278 162725226
279 134918332
280 81582682
281 49059010
282 23658573
283 12414646
284 6618910
285 3375578
286 1652782
287 761136
288 380381
289 181575
290 87822
291 41418
292 19219
293 9034
294 4296
295 1996
296 912
297 422
298 198
299 91
300 42
301 482666383
302 369052545
303 305987923
304 185025378
305 111263343
306 53656442
307 28155787
308 15011352
309 7655640
310 3748426
311 1726218
312 862685
313 411803
314 199176
315 93934
316 43588
317 20489
318 9744
319 4527
320 2069
321 958
322 450
323 207
324 96
325 43
326 1094662834
327 836992422
328 693965063
329 419628157
330 252339609
331 121690085
332 63855895
333 34044984
334 17362603
335 8501240
336 3914975
337 1956526
338 933949
339 451722
340 213038
341 98856
342 46469
343 22099
344 10268
345 4693
346 2173
347 1021
348 470
349 218
350 98
351 45
352 2482639691
353 1898256288
354 1573877505
355 951695340
356 572293413
357 275986931
358 144821926
359 77212294
360 39377502
361 19280381
362 8878965
363 4437302
364 2118149
365 1024483
366 483160
367 224201
368 105390
369 50120
370 23288
371 10644
372 4929
373 2316
374 1066
375 495
376 223
377 103
378 47
379 5630500683
380 4305148816
381 3569474217
382 2158396678
383 1297932384
384 625924338
385 328448771
386 175113560
387 89306174
388 43726925
389 20137042
390 10063576
391 4803855
392 2323476
393 1095783
394 508477
395 239020
396 113670
397 52817
398 24141
399 11179
400 5253
401 2418
402 1123
403 506
404 234
405 107
406 49
407 12769689477
408 9763858781
409 8095386168
410 4895134003
411 2943644703
412 1419564597
413 744905125
414 397148657
415 202541866
416 99170445
417 45669789
418 22823680
419 10894900
420 5269526
421 2485181
422 1153201
423 542086
424 257798
425 119787
426 54751
427 25354
428 11914
429 5484
430 2547
431 1148
432 531
433 243
434 112
435 51
436 28961006937
437 22143935638
438 18359924523
439 11101915209
440 6676036627
441 3219500382
442 1689406977
443 900712976
444 459354662
445 224913531
446 103576762
447 51762947
448 24709080
449 11951018
450 5636265
451 2615402
452 1229424
453 584673
454 271671
455 124173
456 57502
457 27021
458 12438
459 5777
460 2604
461 1205
462 552
463 255
464 116
465 52
466 65682092295
467 50221320948
468 41639375996
469 25178579633
470 15140911877
471 7301663292
472 3831489190
473 2042771267
474 1041793035
475 510092461
476 234906834
477 117395734
478 56038939
479 27104302
480 12782763
481 5931599
482 2788272
483 1326009
484 616137
485 281619
486 130412
487 61283
488 28209
489 13102
490 5906
491 2733
492 1252
493 579
494 264
495 118
496 54
497 148963648178
498 113899404287
499 94435989164
500 57103739346
501 34338818865
502 16559801367
503 8689622815
504 4632901446
505 2362733673
506 1156863785
507 532756765
508 266247561
509 127093467
510 61471180
511 28990658
512 13452566
513 6323660
514 3007322
515 1397368
516 638698
517 295768
518 138987
519 63977
520 29715
521 13395
522 6199
523 2840
524 1314
525 599
526 268
527 123
528 56
529 337841985587
530 258318061972
531 214176025361
532 129508379535
533 77878696514
534 37556788138
535 19707623046
536 10507185094
537 5358559926
538 2623708287
539 1208265275
540 603835941
541 288241526
542 139413514
543 65749340
544 30509737
545 14341740
546 6820454
547 3169160
548 1448535
549 670787
550 315216
551 145097
552 67393
553 30380
554 14060
555 6441
556 2981
557 1359
558 608
559 279
560 128
561 58
562 766208458382
563 585852240040
564 485740343756
565 293718424780
566 176624926867
567 85176887328
568 44695887772
569 23829761949
570 12152941657
571 5950437091
572 2740284255
573 1369469235
574 653717137
575 316182767
576 149116163
577 69194534
578 32526338
579 15468444
580 7187494
581 3285204
582 1521311
583 714894
584 329073
585 152844
586 68901
587 31888
588 14608
589 6761
590 3083
591 1379
592 633
593 291
594 132
595 60
596 1737721854422
597 1328683114683
598 1101634420353
599 666138464282
600 400576360252
601 193176852830
602 101368002578
603 54044689369
604 27562254217
605 13495288996
606 6214825464
607 3105886646
608 1482597253
609 717086452
610 338187882
611 156929688
612 73768082
613 35081646
614 16300872
615 7450676
616 3450257
617 1621344
618 746321
619 346643
620 156264
621 72321
622 33131
623 15334
624 6993
625 3128
626 1436
627 660
628 300
629 137
630 61
631 3941064876407
632 3013385796943
633 2498450893994
634 1510768192116
635 908486832741
636 438115287373
637 229897479586
638 122570609610
639 62509792194
640 30606629781
641 14094908393
642 7043993111
643 3362455243
644 1626315640
645 766992934
646 355908560
647 167302262
648 79563391
649 36969550
650 16897755
651 7825008
652 3677126
653 1692619
654 786169
655 354399
656 164021
657 75140
658 34777
659 15860
660 7095
661 3257
662 1497
663 681
664 311
665 139
666 63
667 8938134903766
668 6834205884661
669 5666359687363
670 3426345501261
671 2060401978650
672 993623212190
673 521395803170
674 277983915081
675 141769032726
676 69414281295
677 31966536108
678 15975418488
679 7625877653
680 3688401243
681 1739501006
682 807182532
683 379433030
684 180445729
685 83845062
686 38323250
687 17746721
688 8339535
689 3838774
690 1782992
691 803759
692 371992
693 170414
694 78873
695 35970
696 16092
697 7387
698 3396
699 1545
700 706
701 316
702 143
703 65
704 20271235836837
705 15499631717025
706 12851015876980
707 7770777512575
708 4672887003563
709 2253486961668
710 1182499190737
711 630453395717
712 321524963283
713 157428063207
714 72498479751
715 36231437459
716 17295103065
717 8365106621
718 3945099902
719 1830648972
720 860534834
721 409241746
722 190156341
723 86915184
724 40248662
725 18913642
726 8706145
727 4043736
728 1822885
729 843659
730 386491
731 178880
732 81579
733 36496
734 16754
735 7702
736 3504
737 1602
738 717
739 325
740 148
741 67
742 45974132945736
743 35152377235607
744 29145451080117
745 17623728584207
746 10597870306053
747 5110793934870
748 2681848084683
749 1429836269682
750 729202280825
751 357038848817
752 164422868604
753 82171059326
754 39224415030
755 18971636806
756 8947286137
757 4151818858
758 1951649282
759 928139488
760 431264921
761 197119222
762 91281921
763 42895180
764 19745095
765 9170988
766 4134211
767 1913376
768 876542
769 405691
770 185018
771 82772
772 37998
773 17468
774 7947
775 3634
776 1627
777 738
778 336
779 152
780 68
781 104266997687004
782 79723805563530
783 66100402240193
784 39969721010178
785 24035431402103
786 11591020977271
787 6082295197880
788 3242796013135
789 1653793723916
790 809745968842
791 372902712068
792 186359787640
793 88958980391
794 43026708374
795 20291990369
796 9416114227
797 4426241414
798 2104973203
799 978086930
800 447056381
801 207022760
802 97284089
803 44780873
804 20799335
805 9376181
806 4339440
807 1987953
808 920087
809 419612
810 187723
811 86178
812 39617
813 18024
814 8242
815 3690
816 1674
817 763
818 345
819 155
820 70
821 236472253201459
822 180809540445344
823 149912353880019
824 90649296486731
825 54511137238134
826 26287846664854
827 13794336482160
828 7354496599209
829 3750720140603
830 1836462716110
831 845724404690
832 422654529880
833 201754447738
834 97582388510
835 46021203171
836 21355268657
837 10038490641
838 4773972276
839 2218251464
840 1013901159
841 469517102
842 220635372
843 101560745
844 47171836
845 21264703
846 9841630
847 4508577
848 2086711
849 951659
850 425747
851 195448
852 89850
853 40878
854 18693
855 8369
856 3797
857 1731
858 783
859 352
860 159
861 72
862 536307055680617
863 410066851236861
864 339993601917638
865 205587998761531
866 123628489677729
867 59619500614309
868 31284854284838
869 16679624622914
870 8506442713916
871 4165004133932
872 1918059980636
873 958558999719
874 457568836817
875 221311899217
876 104373750567
877 48432664305
878 22766786743
879 10827126569
880 5030881617
881 2299476315
882 1064840933
883 500389814
884 230334610
885 106983328
886 48227266
887 22320317
888 10225224
889 4732555
890 2158315
891 965573
892 443267
893 203776
894 92710
895 42395
896 18981
897 8612
898 3926
899 1776
900 799
901 361
902 164
903 74
904 1216317153825969
905 930010784105413
906 771088214900856
907 466263135764745
908 280383133326085
909 135213998271369
910 70952460010624
911 37828541193593
912 19292179883488
913 9446017762024
914 4350062584118
915 2173963109311
916 1037742873941
917 501924143105
918 236714363310
919 109842821898
920 51633915609
921 24555372959
922 11409783901
923 5215095452
924 2415005135
925 1134858675
926 522387193
927 242632753
928 109376989
929 50621345
930 23190289
931 10733195
932 4894949
933 2189871
934 1005308
935 462154
936 210262
937 96150
938 43048
939 19532
940 8904
941 4028
942 1813
943 819
944 372
945 168
946 76
947 2758545506759729
948 2109217206764107
949 1748788894277553
950 1057461102218057
951 635894700798203
952 306658478184935
953 160916574382097
954 85793209450857
955 43753683786993
956 21423088355073
957 9865720924676
958 4930437878137
959 2353548112906
960 1138338455017
961 536856149106
962 249117939218
963 117103097208
964 55690338273
965 25876810185
966 11827571519
967 5477108946
968 2573801816
969 1184747613
970 550278757
971 248061454
972 114806639
973 52594398
974 24342341
975 11101496
976 4966517
977 2279988
978 1048142
979 476864
980 218064
981 97631
982 44298
983 20194
984 9136
985 4112
986 1858
987 844
988 382
989 173
990 77
991 6256241054340230
992 4783597460742485
993 3966164360509293
994 2398268052802768
995 1442176873146515
996 695485847951681
997 364950614918660
998 194574640090146
999 99231131810598
1000 48586475934269
1001 22374953803870
1002 11181982604053
1003 5337727542013
1004 2581693779770
1005 1217562469817
1006 564986829070
1007 265583874745
1008 126302857713
1009 58687290762
1010 26824331275
1011 12421804811
1012 5837251751
1013 2686947393
1014 1248004263
1015 562590775
1016 260375625
1017 119281423
1018 55207193
1019 25177629
1020 11263809
1021 5170897
1022 2377133
1023 1081504
1024 494559
1025 221423
1026 100466
1027 45799
1028 20720
1029 9326
1030 4214
1031 1915
1032 867
1033 393
1034 175
1035 79
1036 14188836846845361
1037 10848955998006489
1038 8995059258466152
1039 5439150093587399
1040 3270783874795481
1041 1577326567209290
1042 827689452382017
1043 441285397860023
1044 225051165253873
1045 110191658858200
1046 50745258410171
1047 25360168416641
1048 12105694868326
1049 5855150322934
1050 2761369820156
1051 1281361422724
1052 602330734251
1053 286448464152
1054 133099793690
1055 60836220453
1056 28172022190
1057 13238590395
1058 6093860171
1059 2830410261
1060 1275927294
1061 590518689
1062 270524207
1063 125207109
1064 57101584
1065 25545747
1066 11727332
1067 5391217
1068 2452797
1069 1121635
1070 502177
1071 227852
1072 103870
1073 46992
1074 21151
1075 9558
1076 4344
1077 1967
1078 892
1079 397
1080 180
1081 81
1082 32179561068339894
1083 24604880994399602
1084 20400337381108403
1085 12335716062263208
1086 7417971647459150
1087 3577296514302465
1088 1877157625113554
1089 1000812861708286
1090 510404608493205
1091 249909083720101
1092 115087667831056
1093 57515573480439
1094 27455100900438
1095 13279183446461
1096 6262646453627
1097 2906062603880
1098 1366055502322
1099 649650562947
1100 301863569612
1101 137973457047
1102 63892714975
1103 30024450396
1104 13820565254
1105 6419226666
1106 2893738277
1107 1339266384
1108 613535157
1109 283963362
1110 129503492
1111 57936457
1112 26596994
1113 12227007
1114 5562819
1115 2543812
1116 1138912
1117 516757
1118 235572
1119 106576
1120 47970
1121 21678
1122 9852
1123 4462
1124 2024
1125 901
1126 409
1127 184
1128 83
1129 72981609537729459
1130 55802619981112457
1131 46266928688807248
1132 27976777281469472
1133 16823582807331945
1134 8113126740698946
1135 4257298119942209
1136 2269792721485989
1137 1157571719645288
1138 566781104604205
1139 261012983316225
1140 130442398427175
1141 62266773915264
1142 30116513373546
1143 14203363966985
1144 6590802335624
1145 3098144473308
1146 1473374469599
1147 684611238926
1148 312916790487
1149 144905431330
1150 68093928029
1151 31344339807
1152 14558479934
1153 6562851389
1154 3037388115
1155 1391466564
1156 644014478
1157 293707341
1158 131396941
1159 60320632
1160 27730231
1161 12616191
1162 5769237
1163 2582995
1164 1171979
1165 534266
1166 241709
1167 108794
1168 49165
1169 22344
1170 10120
1171 4591
1172 2044
1173 928
1174 418
1175 189
1176 85
1177 165518582413417050
1178 126557506921704829
1179 104931043556048742
1180 63449909442334070
1181 38155031041686605
1182 18400159239659522
1183 9655335833061470
1184 5147774569680189
1185 2625313846750637
1186 1285430748472327
1187 591964184726071
1188 295836732171691
1189 141217879616415
1190 68302722184375
1191 32212507838729
1192 14947604834552
1193 7026434256274
1194 3341538438476
1195 1552663506452
1196 709679382284
1197 328638155964
1198 154433569083
1199 71087370153
1200 33017892810
1201 14884213508
1202 6888641923
1203 3155775471
1204 1460592116
1205 666113327
1206 298001587
1207 136804129
1208 62890756
1209 28612881
1210 13084337
1211 5858102
1212 2657989
1213 1211689
1214 548184
1215 246740
1216 111504
1217 50676
1218 22952
1219 10413
1220 4636
1221 2105
1222 949
1223 429
1224 193
1225 86
1226 375387735316853428
1227 287025995619176690
1228 237978275493895707
1229 143901170879569422
1230 86533671838177555
1231 41730626288189874
1232 21897811105243043
1233 11674891178123655
1234 5954078418616352
1235 2915291627923948
1236 1342544694697641
1237 670942677820249
1238 320274976032884
1239 154907103618901
1240 73056331139027
1241 33900408313302
1242 15935595897187
1243 7578439403020
1244 3521361945576
1245 1609516781937
1246 745334640421
1247 350247488287
1248 161222543731
1249 74882903335
1250 33756640006
1251 15623089887
1252 7157138431
1253 3312548710
1254 1510711183
1255 675852459
1256 310264814
1257 142633040
1258 64892561
1259 29674612
1260 13285878
1261 6028185
1262 2748050
1263 1243254
1264 559594
1265 252886
1266 114931
1267 52054
1268 23617
1269 10515
1270 4775
1271 2153
1272 973
1273 438
1274 196
1275 88