1 1
2 4
3 2
4 8
5 5
6 3
7 14
8 10
9 7
10 6
11 22
12 17
13 12
14 11
15 9
16 34
17 27
18 19
19 18
20 15
21 13
22 51
23 41
24 29
25 28
26 24
27 21
28 16
29 75
30 60
31 44
32 42
33 36
34 32
35 25
36 20
37 109
38 87
39 65
40 62
41 53
42 48
43 38
44 31
45 23
46 157
47 126
48 94
49 90
50 77
51 70
52 56
53 46
54 35
55 26
56 225
57 181
58 135
59 130
60 111
61 101
62 82
63 68
64 52
65 39
66 30
67 321
68 258
69 193
70 186
71 159
72 145
73 118
74 99
75 76
76 58
77 45
78 33
79 456
80 367
81 275
82 266
83 227
84 208
85 169
86 143
87 110
88 85
89 66
90 49
91 37
92 647
93 522
94 391
95 379
96 324
97 297
98 242
99 205
100 158
101 123
102 96
103 72
104 55
105 40
106 917
107 741
108 555
109 538
110 461
111 423
112 345
113 292
114 226
115 176
116 138
117 104
118 80
119 59
120 43
121 1299
122 1050
123 787
124 763
125 654
126 601
127 490
128 415
129 322
130 251
131 198
132 150
133 116
134 86
135 63
136 47
137 1840
138 1487
139 1115
140 1082
141 927
142 852
143 695
144 589
145 458
146 357
147 283
148 215
149 167
150 124
151 92
152 69
153 50
154 2605
155 2105
156 1579
157 1533
158 1313
159 1207
160 985
161 835
162 650
163 507
164 403
165 307
166 239
167 178
168 133
169 100
170 73
171 54
172 3687
173 2979
174 2236
175 2170
176 1859
177 1709
178 1396
179 1183
180 922
181 720
182 572
183 437
184 340
185 254
186 191
187 144
188 106
189 79
190 57
191 5217
192 4215
193 3165
194 3071
195 2632
196 2419
197 1977
198 1676
199 1306
200 1021
201 811
202 621
203 483
204 362
205 273
206 206
207 152
208 114
209 83
210 61
211 7380
212 5963
213 4478
214 4346
215 3725
216 3423
217 2798
218 2373
219 1849
220 1446
221 1149
222 881
223 686
224 514
225 389
226 294
227 217
228 164
229 120
230 89
231 64
232 10439
233 8435
234 6335
235 6149
236 5270
237 4843
238 3959
239 3358
240 2617
241 2047
242 1627
243 1248
244 973
245 729
246 553
247 418
248 309
249 234
250 172
251 128
252 93
253 67
254 14765
255 11931
256 8962
257 8698
258 7455
259 6852
260 5601
261 4751
262 3703
263 2897
264 2303
265 1767
266 1379
267 1033
268 785
269 594
270 439
271 333
272 246
273 184
274 134
275 97
276 71
277 20883
278 16875
279 12677
280 12303
281 10545
282 9693
283 7924
284 6721
285 5239
286 4099
287 3259
288 2501
289 1953
290 1463
291 1113
292 843
293 623
294 473
295 350
296 263
297 192
298 140
299 103
300 74
301 29536
302 23867
303 17930
304 17402
305 14915
306 13710
307 11209
308 9507
309 7412
310 5799
311 4611
312 3539
313 2764
314 2071
315 1577
316 1195
317 884
318 671
319 497
320 374
321 274
322 200
323 148
324 107
325 78
326 41773
327 33756
328 25359
329 24613
330 21095
331 19391
332 15854
333 13447
334 10485
335 8204
336 6523
337 5007
338 3911
339 2931
340 2233
341 1692
342 1253
343 951
344 705
345 531
346 390
347 285
348 212
349 154
350 113
351 81
352 59078
353 47741
354 35866
355 34811
356 29835
357 27426
358 22423
359 19019
360 14831
361 11605
362 9227
363 7083
364 5533
365 4148
366 3160
367 2395
368 1775
369 1347
370 1000
371 753
372 554
373 406
374 302
375 220
376 162
377 117
378 84
379 83551
380 67518
381 50725
382 49233
383 42196
384 38789
385 31713
386 26899
387 20977
388 16414
389 13051
390 10019
391 7827
392 5869
393 4471
394 3390
395 2513
396 1907
397 1417
398 1067
399 786
400 577
401 430
402 314
403 232
404 168
405 121
406 88
407 118161
408 95487
409 71738
410 69628
411 59677
412 54858
413 44851
414 38043
415 29668
416 23215
417 18459
418 14172
419 11072
420 8303
421 6325
422 4797
423 3556
424 2699
425 2006
426 1511
427 1114
428 819
429 611
430 447
431 331
432 240
433 174
434 127
435 91
436 167107
437 135042
438 101455
439 98471
440 84399
441 77583
442 63431
443 53803
444 41959
445 32833
446 26107
447 20045
448 15661
449 11745
450 8947
451 6786
452 5031
453 3819
454 2839
455 2139
456 1578
457 1161
458 867
459 635
460 471
461 342
462 249
463 182
464 131
465 95
466 236327
467 190981
468 143482
469 139262
470 119361
471 109721
472 89707
473 76091
474 59341
475 46435
476 36923
477 28350
478 22150
479 16612
480 12655
481 9599
482 7117
483 5403
484 4017
485 3028
486 2234
487 1644
488 1229
489 901
490 669
491 486
492 355
493 260
494 188
495 137
496 98
497 334219
498 270090
499 202917
500 196949
501 168804
502 155171
503 126867
504 107611
505 83923
506 65672
507 52220
508 40095
509 31327
510 23495
511 17899
512 13578
513 10067
514 7643
515 5683
516 4285
517 3162
518 2327
519 1741
520 1277
521 949
522 690
523 505
524 370
525 268
526 196
527 141
528 102
529 472660
530 381967
531 286970
532 278530
533 238727
534 219447
535 179420
536 152187
537 118688
538 92877
539 73853
540 56705
541 44306
542 33229
543 25316
544 19205
545 14239
546 10811
547 8039
548 6062
549 4474
550 3293
551 2465
552 1808
553 1345
554 978
555 717
556 526
557 382
558 280
559 202
560 147
561 105
562 668445
563 540185
564 405839
565 393903
566 337613
567 310347
568 253741
569 215227
570 167853
571 131350
572 104446
573 80195
574 62661
575 46995
576 35805
577 27162
578 20139
579 15292
580 11371
581 8575
582 6330
583 4660
584 3489
585 2559
586 1905
587 1386
588 1016
589 746
590 543
591 398
592 288
593 210
594 151
595 108
596 945326
597 763939
598 573946
599 557065
600 477459
601 438899
602 358846
603 304379
604 237382
605 185759
606 147711
607 113415
608 88619
609 66463
610 50638
611 38415
612 28483
613 21629
614 16084
615 12129
616 8954
617 6593
618 4937
619 3621
620 2697
621 1963
622 1439
623 1058
624 770
625 565
626 410
627 299
628 216
629 155
630 112
631 1336895
632 1080375
633 811685
634 787811
635 675231
636 620699
637 507487
638 430459
639 335711
640 262705
641 208897
642 160396
643 125329
644 93995
645 71615
646 54330
647 40284
648 30591
649 22749
650 17155
651 12665
652 9326
653 6984
654 5123
655 3817
656 2779
657 2038
658 1499
659 1091
660 802
661 582
662 425
663 308
664 222
665 161
666 115
667 1890658
668 1527883
669 1147898
670 1114136
671 954923
672 877803
673 717697
674 608763
675 474770
676 371523
677 295427
678 226837
679 177244
680 132932
681 101281
682 76837
683 56973
684 43265
685 32174
686 24263
687 17914
688 13191
689 9879
690 7248
691 5401
692 3933
693 2885
694 2122
695 1545
696 1137
697 826
698 604
699 438
700 316
701 230
702 165
703 119
704 2673797
705 2160755
706 1623375
707 1575629
708 1350468
709 1241403
710 1014979
711 860923
712 671429
713 525415
714 417799
715 320798
716 250663
717 187997
718 143235
719 108666
720 80574
721 61188
722 45503
723 34316
724 25337
725 18657
726 13974
727 10253
728 7641
729 5565
730 4083
731 3003
732 2187
733 1610
734 1171
735 857
736 622
737 449
738 328
739 236
740 171
741 122
742 3781322
743 3055772
744 2295801
745 2228278
746 1909853
747 1755611
748 1435400
749 1217531
750 949546
751 743052
752 590860
753 453679
754 354494
755 265870
756 202567
757 153679
758 113951
759 86535
760 64353
761 48533
762 35834
763 26387
764 19765
765 14502
766 10809
767 7873
768 5777
769 4249
770 3095
771 2279
772 1659
773 1214
774 882
775 637
776 466
777 336
778 244
779 175
780 125
781 5347599
782 4321517
783 3246755
784 3151263
785 2700943
786 2482811
787 2029965
788 1721851
789 1342863
790 1050837
791 835605
792 641601
793 501333
794 375999
795 286475
796 217337
797 161154
798 122381
799 91011
800 68639
801 50679
802 37319
803 27954
804 20511
805 15289
806 11137
807 8172
808 6011
809 4379
810 3225
811 2349
812 1719
813 1250
814 903
815 662
816 478
817 348
818 250
819 179
820 129
821 7562650
822 6111550
823 4591607
824 4456561
825 3819713
826 3511227
827 2870807
828 2435068
829 1899098
830 1486110
831 1181726
832 907363
833 708994
834 531745
835 405139
836 307363
837 227909
838 173075
839 128711
840 97073
841 71673
842 52780
843 39535
844 29009
845 21624
846 15753
847 11559
848 8503
849 6195
850 4563
851 3324
852 2434
853 1770
854 1280
855 939
856 678
857 495
858 356
859 256
860 185
861 132
862 10695205
863 8643039
864 6493515
865 6302532
866 5401892
867 4965627
868 4059937
869 3443709
870 2685733
871 2101679
872 1671215
873 1283208
874 1002671
875 752003
876 572956
877 434679
878 322314
879 244768
880 182027
881 137284
882 101363
883 74645
884 55913
885 41027
886 30583
887 22281
888 16349
889 12028
890 8764
891 6456
892 4703
893 3445
894 2506
895 1813
896 1330
897 961
898 703
899 506
900 365
901 264
902 189
903 136
904 15125306
905 12223105
906 9183219
907 8913129
908 7639431
909 7022460
910 5741620
911 4870142
912 3798203
913 2972225
914 2363457
915 1814733
916 1417993
917 1063495
918 810285
919 614731
920 455823
921 346157
922 257428
923 194151
924 143351
925 105566
926 79075
927 58023
928 43253
929 31513
930 23123
931 17013
932 12397
933 9133
934 6654
935 4874
936 3547
937 2566
938 1883
939 1362
940 997
941 718
942 519
943 376
944 270
945 195
946 139
947 21390415
948 17286083
949 12987035
950 12605070
951 10803789
952 9931261
953 8119879
954 6887423
955 5371473
956 4203363
957 3342435
958 2566423
959 2005347
960 1504012
961 1145919
962 869363
963 644634
964 489542
965 364061
966 274573
967 202731
968 149295
969 111831
970 82059
971 61171
972 44569
973 32703
974 24063
975 17535
976 12919
977 9413
978 6895
979 5019
980 3631
981 2665
982 1929
983 1412
984 1018
985 736
986 534
987 384
988 278
989 199
990 142
991 30250617
992 24446216
993 18366444
994 17826263
995 15278867
996 14044926
997 11483246
998 9740290
999 7596412
1000 5944455
1001 4726919
1002 3629473
1003 2835991
1004 2126997
1005 1620577
1006 1229467
1007 911653
1008 692319
1009 514863
1010 388307
1011 286707
1012 211138
1013 158155
1014 116051
1015 86511
1016 63033
1017 46252
1018 34033
1019 24801
1020 18273
1021 13314
1022 9754
1023 7100
1024 5138
1025 3771
1026 2731
1027 1999
1028 1442
1029 1043
1030 758
1031 546
1032 396
1033 284
1034 203
1035 146
1036 42780835
1037 34572173
1038 25974077
1039 25210145
1040 21607583
1041 19862527
1042 16239765
1043 13774853
1044 10742951
1045 8406731
1046 6684875
1047 5132852
1048 4010699
1049 3008031
1050 2291844
1051 1738731
1052 1289275
1053 979089
1054 728129
1055 549152
1056 405467
1057 298597
1058 223667
1059 164123
1060 122348
1061 89145
1062 65413
1063 48132
1064 35076
1065 25844
1066 18831
1067 13797
1068 10043
1069 7269
1070 5335
1071 3865
1072 2830
1073 2042
1074 1478
1075 1074
1076 775
1077 563
1078 404
1079 290
1080 209
1081 149
1082 60501240
1083 48892438
1084 36732894
1085 35652531
1086 30557739
1087 28089858
1088 22966498
1089 19480586
1090 15192830
1091 11888915
1092 9453843
1093 7258951
1094 5671987
1095 4254001
1096 3241159
1097 2458939
1098 1823313
1099 1384643
1100 1029732
1101 776621
1102 573419
1103 422282
1104 316315
1105 232107
1106 173029
1107 126073
1108 92510
1109 68071
1110 49607
1111 36551
1112 26634
1113 19514
1114 14205
1115 10282
1116 7547
1117 5468
1118 4005
1119 2890
1120 2093
1121 1521
1122 1099
1123 799
1124 574
1125 413
1126 298
1127 213
1128 153
1129 85561677
1130 69144351
1131 51948159
1132 50420295
1133 43215171
1134 39725061
1135 32479535
1136 27549711
1137 21485909
1138 16813467
1139 13369755
1140 10265709
1141 8021403
1142 6016068
1143 4583694
1144 3477467
1145 2578556
1146 1958183
1147 1456263
1148 1098310
1149 810939
1150 597199
1151 447339
1152 328251
1153 244702
1154 178297
1155 130831
1156 96269
1157 70157
1158 51693
1159 37669
1160 27599
1161 20091
1162 14543
1163 10676
1164 7735
1165 5666
1166 4090
1167 2962
1168 2154
1169 1557
1170 1132
1171 814
1172 587
1173 424
1174 304
1175 219
1176 156
1177 121002487
1178 97784881
1179 73465793
1180 71305068
1181 61115483
1182 56179723
1183 45933001
1184 38961177
1185 30385666
1186 23777836
1187 18907691
1188 14517907
1189 11343979
1190 8508007
1191 6482325
1192 4917883
1193 3646631
1194 2769291
1195 2059469
1196 1553247
1197 1146843
1198 844569
1199 632635
1200 464220
1201 346063
1202 252153
1203 185025
1204 136147
1205 99219
1206 73107
1207 53275
1208 39033
1209 28415
1210 20569
1211 15101
1212 10941
1213 8015
1214 5787
1215 4191
1216 3049
1217 2204
1218 1603
1219 1154
1220 833
1221 602
1222 432
1223 312
1224 223
1225 160
1226 171123361
1227 138288707
1228 103896323
1229 100840597
1230 86430347
1231 79450129
1232 64959075
1233 55099427
1234 42971823
1235 33626941
1236 26739516
1237 20531423
1238 16042811
1239 12032141
1240 9167394
1241 6954939
1242 5157118
1243 3916371
1244 2912531
1245 2196625
1246 1621883
1247 1194403
1248 894683
1249 656509
1250 489409
1251 356601
1252 261667
1253 192543
1254 140319
1255 103391
1256 75345
1257 55203
1258 40187
1259 29091
1260 21359
1261 15475
1262 11337
1263 8187
1264 5929
1265 4314
1266 3119
1267 2269
1268 1635
1269 1181
1270 854
1271 613
1272 444
1273 318
1274 229
1275 163