1 1
2 5
3 6
4 16
5 29
6 21
7 41
8 89
9 99
10 56
11 91
12 219
13 295
14 259
15 126
16 182
17 469
18 705
19 755
20 574
21 252
22 336
23 910
24 1470
25 1765
26 1645
27 1134
28 462
29 582
30 1638
31 2786
32 3605
33 3780
34 3206
35 2058
36 792
37 957
38 2778
39 4914
40 6706
41 7595
42 7266
43 5754
44 3498
45 1287
46 1507
47 4488
48 8190
49 11634
50 13916
51 14406
52 12894
53 9690
54 5643
55 2002
56 2288
57 6963
58 13035
59 19110
60 23814
61 26068
62 25284
63 21510
64 15510
65 8723
66 3003
67 3367
68 10439
69 19965
70 30030
71 38640
72 44100
73 45276
74 41790
75 34155
76 23815
77 13013
78 4368
79 4823
80 15197
81 29601
82 45485
83 60060
84 70812
85 75852
86 74172
87 65835
88 52085
89 35321
90 18837
91 6188
92 6748
93 21567
94 42679
95 66781
96 90090
97 109032
98 120708
99 123228
100 115962
101 99715
102 76791
103 50869
104 26572
105 8568
106 9248
107 29932
108 60060
109 95459
110 131131
111 162162
112 184338
113 194580
114 191268
115 174482
116 146146
117 110019
118 71435
119 36652
120 11628
121 12444
122 40732
123 82740
124 133315
125 186004
126 234234
127 272118
128 295020
129 299970
130 285978
131 254254
132 208299
133 153790
134 98140
135 49572
136 15504
137 16473
138 54468
139 111860
140 182420
141 257985
142 329966
143 390390
144 432630
145 451935
146 445830
147 414414
148 360542
149 289835
150 210420
151 132260
152 65892
153 20349
154 21489
155 71706
156 148716
157 245140
158 350840
159 454818
160 546546
161 616902
162 658845
163 667920
164 642642
165 584766
166 499408
167 394940
168 282540
169 175236
170 86241
171 26334
172 27664
173 93081
174 194769
175 324156
176 468860
177 615048
178 749112
179 858858
180 934362
181 968605
182 957957
183 902538
184 806442
185 677768
186 528360
187 373116
188 228684
189 111321
190 33649
191 35189
192 119301
193 251655
194 422484
195 616896
196 817768
197 1007832
198 1171170
199 1294293
200 1366937
201 1382667
202 1339338
203 1239420
204 1090152
205 903448
206 695436
207 485469
208 294405
209 141911
210 42504
211 44275
212 151151
213 321195
214 543495
215 800394
216 1071000
217 1333752
218 1568280
219 1756755
220 1884883
221 1942655
222 1924923
223 1831830
224 1669080
225 1447992
226 1185240
227 902139
228 623295
229 374395
230 178871
231 53130
232 55154
233 189497
234 405405
235 690935
236 1025430
237 1383732
238 1739304
239 2066520
240 2342340
241 2547545
242 2667665
243 2693691
244 2622620
245 2457840
246 2209320
247 1893528
248 1532958
249 1155105
250 790685
251 470855
252 223146
253 65780
254 68080
255 235290
256 506506
257 868945
258 1298745
259 1765974
260 2238390
261 2684232
262 3074280
263 3383380
264 3591588
265 3685045
266 3656653
267 3506580
268 3242580
269 2880072
270 2441880
271 1957494
272 1461670
273 992145
274 586201
275 275770
276 80730
277 83330
278 289570
279 626934
280 1082081
281 1627780
282 2228814
283 2846466
284 3441888
285 3978612
286 4424420
287 4752748
288 4943757
289 4985162
290 4872868
291 4611420
292 4214232
293 3703518
294 3109806
295 2470874
296 1829905
297 1232616
298 723074
299 337870
300 98280
301 101205
302 353470
303 769350
304 1335334
305 2020711
306 2784474
307 3580626
308 4362210
309 5084343
310 5706492
311 6194188
312 6520332
313 6666205
314 6622252
315 6388668
316 5975772
317 5404113
318 4704210
319 3915786
320 3086314
321 2268651
322 1517494
323 884350
324 410670
325 118755
326 122031
327 428220
328 936650
329 1634150
330 2486484
331 3446366
332 4459686
333 5470290
334 6423615
335 7269438
336 7963956
337 8471372
338 8765120
339 8828820
340 8657012
341 8255676
342 7642503
343 6846840
344 5909190
345 4880106
346 3818276
347 2787554
348 1852650
349 1073150
350 495495
351 142506
352 146160
353 515151
354 1131975
355 1984450
356 3034850
357 4229148
358 5504268
359 6793710
360 8031870
361 9157335
362 10115391
363 10859940
364 11354980
365 11575760
366 11509680
367 11156964
368 10531092
369 9658935
370 8580495
371 7348110
372 6024942
373 4682524
374 3397100
375 2244450
376 1292850
377 593775
378 169911
379 173971
380 615699
381 1358721
382 2392650
383 3676400
384 5148780
385 6736884
386 8362662
387 9948015
388 11418715
389 12707409
390 13755924
391 14517048
392 14955920
393 15051120
394 14795508
395 14196819
396 13277979
397 12077065
398 10646790
399 9053352
400 7374444
401 5696180
402 4108650
403 2699775
404 1547091
405 707049
406 201376
407 205871
408 731409
409 1620549
410 2865681
411 4422600
412 6222580
413 8182020
414 10210068
415 12214587
416 14106785
417 15804789
418 17236401
419 18341232
420 19072368
421 19397680
422 19300848
423 18782127
424 17858841
425 16565549
426 14953785
427 13091232
428 11060148
429 8954820
430 6877780
431 4934475
432 3226041
433 1839789
434 836969
435 237336
436 242296
437 863939
438 1921395
439 3411009
440 5285826
441 7469280
442 9866220
443 12371700
444 14877918
445 17279647
446 19478459
447 21386001
448 22926540
449 24038952
450 24678288
451 24817008
452 24445932
453 23574915
454 22233211
455 20469449
456 18351102
457 15963288
458 13406700
459 10794420
460 8247330
461 5887791
462 3831219
463 2175145
464 985304
465 278256
466 283712
467 1015064
468 2265480
469 4036655
470 6279399
471 8909082
472 11818170
473 14886300
474 17988300
475 21000518
476 23805782
477 26297271
478 28381535
479 29980860
480 31035132
481 31503312
482 31364592
483 30619260
484 29289260
485 27418391
486 25072047
487 22336358
488 19316550
489 16134300
490 12923820
491 9826362
492 6982794
493 4523855
494 2557655
495 1153944
496 324632
497 330616
498 1186680
499 2657320
500 4751215
501 7417620
502 10563714
503 14068782
504 17795700
505 21600150
506 25337950
507 28870842
508 32071039
509 34824790
510 37035180
511 38624340
512 39535200
513 39732876
514 39205740
515 37966180
516 36051015
517 33521488
518 30462718
519 26982450
520 23208900
521 19287450
522 15375906
523 11637990
524 8234695
525 5313090
526 2992120
527 1344904
528 376992
529 383537
530 1380808
531 3101736
532 5563880
533 8715805
534 12456486
535 16651278
536 21144942
537 25772175
538 30366050
539 34764730
540 38816778
541 42385343
542 45351460
543 47616660
544 49105044
545 49764933
546 49570164
547 48521060
548 46645060
549 43996953
550 40658618
551 36738130
552 32368050
553 27702675
554 22913982
555 18185958
556 13706966
557 9659755
558 6208680
559 3483656
560 1560328
561 435897
562 443037
563 1599598
564 3603864
565 6484456
566 10190320
567 14612346
568 19601274
569 24982398
570 30567537
571 36164700
572 41585830
573 46652970
574 51203152
575 55092268
576 58198140
577 60422964
578 61695261
579 61971426
580 61236924
581 59507140
582 56827848
583 53275222
584 48955270
585 44002530
586 38577825
587 32864832
588 27065178
589 21391734
590 16059736
591 11275320
592 7221016
593 4037704
594 1802493
595 501942
596 509712
597 1845333
598 4169165
599 7523384
600 11858616
601 17057936
602 22956864
603 29359890
604 36054018
605 42819777
606 49440105
607 55707470
608 61429550
609 66433752
610 70570808
611 73717644
612 75779676
613 76692645
614 76424061
615 74974284
616 72377228
617 68700632
618 64045800
619 58546670
620 52368030
621 45702657
622 38767113
623 31795890
624 25033554
625 18724496
626 13099856
627 8361144
628 4660040
629 2073813
630 575757
631 584193
632 2120433
633 4803435
634 8691760
635 13739264
636 19821648
637 26758704
638 34332810
639 42304185
640 50423373
641 58441383
642 66117870
643 73227700
644 79566200
645 84953352
646 89237148
647 92296281
648 94042305
649 94421355
650 93415476
651 91043568
652 87361912
653 82464200
654 76480950
655 69578145
656 61954893
657 53839863
658 45486210
659 37164660
660 29154384
661 21731248
662 15152984
663 9640785
664 5356785
665 2376843
666 658008
667 667147
668 2427459
669 5512815
670 10001355
671 15851990
672 22933680
673 31050096
674 39960240
675 49395555
676 59074015
677 68711643
678 78031863
679 86773050
680 94694600
681 101581800
682 107249736
683 111546435
684 114355395
685 115597615
686 115233195
687 113262534
688 109727112
689 104709800
690 98334600
691 90765675
692 82205487
693 72891819
694 63093415
695 53103930
696 43233840
697 33799920
698 25111856
699 17455515
700 11072355
701 6134415
702 2714283
703 749398
704 759278
705 2769117
706 6303801
707 11464635
708 18217710
709 26426092
710 35877072
711 46305072
712 57410760
713 68876885
714 80381301
715 91607607
716 102253788
717 112039200
718 120710200
719 128044680
720 133855722
721 137994549
722 140352905
723 140864955
724 139508754
725 136307292
726 131329080
727 124688200
728 116543700
729 107098173
730 96595317
731 85316231
732 73574160
733 61707360
734 50069712
735 39018672
736 28900102
737 20029485
738 12668985
739 6999771
740 3088982
741 850668
742 861328
743 3148262
744 7183254
745 13094781
746 20858565
747 30332862
748 41288478
749 53434128
750 66437712
751 79944040
752 93589496
753 107014089
754 119871297
755 131836068
756 142611300
757 151933080
758 159574920
759 165351186
760 169119874
761 170784845
762 170297589
763 167658546
764 162917970
765 156176280
766 147583800
767 137339748
768 125690292
769 112925449
770 99374561
771 85400040
772 71389032
773 57742608
774 44862048
775 33131742
776 22898190
777 14444541
778 7960069
779 3503942
780 962598
781 974078
782 3567902
783 8158410
784 14905709
785 23797956
786 34689942
787 47336058
788 61418280
789 76569768
790 92394632
791 108484376
792 124431489
793 139840610
794 154337652
795 167577228
796 179248680
797 189080970
798 196846650
799 202365086
800 205505069
801 206186904
802 204384026
803 200124150
804 193489920
805 184618980
806 173703348
807 160987932
808 146767985
809 131385254
810 115222536
811 98696312
812 82247088
813 66327030
814 51384438
815 37844562
816 26086221
817 16413644
818 9022910
819 3962322
820 1086008
821 1098349
822 4031202
823 9236890
824 16912090
825 27060579
826 39535314
827 54074538
828 70332570
829 87905895
830 106355128
831 125223384
832 144051544
833 162390865
834 179813340
835 195920172
836 210348684
837 222777945
838 232933350
839 240590350
840 245577486
841 247778839
842 247135966
843 243649350
844 237379350
845 228446595
846 217031724
847 203374332
848 187770940
849 170571765
850 152176024
851 133025464
852 113595768
853 94385445
854 75901770
855 58643298
856 43078434
857 29619499
858 18591690
859 10196290
860 4467442
861 1221759
862 1235003
863 4541488
864 10426710
865 19129370
866 30672460
867 44909046
868 61561710
869 80256330
870 100550835
871 121959530
872 143973544
873 166077912
874 187765760
875 208550020
876 227973060
877 245614572
878 261098019
879 274095900
880 284334050
881 291595150
882 295721580
883 296617706
884 294251650
885 288656550
886 279931275
887 268240518
888 253814148
889 236945660
890 217989520
891 197357160
892 175511336
893 152958520
894 130238955
895 107913960
896 86550030
897 66699234
898 48875372
899 33525310
900 20994870
901 11488610
902 5022787
903 1370754
904 1384944
905 5102251
906 11736291
907 21573790
908 34660990
909 50853348
910 69858516
911 91273302
912 114615270
913 139349595
914 164911747
915 190726536
916 216224008
917 240852640
918 264090240
919 285452916
920 304502436
921 320852259
922 334172475
923 344193850
924 350711130
925 353585716
926 352747780
927 348197850
928 340007850
929 328321539
930 313354251
931 295391796
932 274788340
933 251963040
934 227395168
935 201617416
936 175207032
937 148774395
938 122948595
939 98359542
940 75616086
941 55279588
942 37832340
943 23640190
944 12908686
945 5632011
946 1533939
947 1549119
948 5717151
949 13174469
950 24262406
951 39054960
952 57412628
953 79029132
954 103471758
955 130215987
956 158675055
957 188225037
958 218226008
959 248039792
960 277044768
961 304648160
962 330296196
963 353482479
964 373754871
965 390721149
966 404053650
967 413493080
968 418851620
969 420015420
970 416946530
971 409684275
972 398346039
973 383127381
974 364301364
975 342216936
976 317296160
977 290030048
978 260972712
979 230733503
980 199966767
981 169358805
982 139611582
983 111422688
984 85461012
985 62337548
986 42570710
987 26545491
988 14465759
989 6298941
990 1712304
991 1728519
992 6390021
993 14750505
994 27213109
995 43884596
996 64633548
997 89141052
998 116944620
999 147476043
1000 180093837
1001 214110897
1002 248817933
1003 283503220
1004 317469152
1005 350046048
1006 380603616
1007 408560439
1008 433391805
1009 454636161
1010 471900429
1011 484864380
1012 493284220
1013 496995500
1014 495915420
1015 490044555
1016 479467989
1017 464355801
1018 444962805
1019 421627404
1020 394769376
1021 364886368
1022 332548832
1023 298393095
1024 263112213
1025 227444217
1026 192157317
1027 158031588
1028 125836620
1029 96304572
1030 70098028
1031 47772011
1032 29729469
1033 16169505
1034 7027581
1035 1906884
1036 1924180
1037 7124871
1038 16474095
1039 30444645
1040 49181594
1041 72565080
1042 100265172
1043 131789580
1044 166524930
1045 203772283
1046 242777535
1047 282757293
1048 322920780
1049 362488280
1050 400706592
1051 436861920
1052 470290584
1053 500387895
1054 526615495
1055 548507421
1056 565675110
1057 577811520
1058 584694500
1059 586189500
1060 582251670
1061 572927355
1062 558354951
1063 538765045
1064 514479720
1065 485910864
1066 453557280
1067 418000352
1068 379897980
1069 339976455
1070 299019903
1071 257856885
1072 217343698
1073 178343880
1074 141703380
1075 108220812
1076 78612170
1077 53469339
1078 33211695
1079 18030045
1080 7822116
1081 2118760
1082 2137184
1083 7925892
1084 18355380
1085 33976635
1086 54979155
1087 81258562
1088 112475874
1089 148109220
1090 187498740
1091 229885370
1092 274444170
1093 320312811
1094 366615795
1095 412484940
1096 457076620
1097 499586208
1098 539260128
1099 575405880
1100 607400360
1101 634696755
1102 656830251
1103 673422750
1104 684186750
1105 688928500
1106 687550500
1107 680053374
1108 666537102
1109 647201555
1110 622346235
1111 592369080
1112 557764152
1113 519117984
1114 477104320
1115 432476940
1116 386060220
1117 338737035
1118 291433571
1119 245100570
1120 200690490
1121 159130020
1122 121287348
1123 87933538
1124 59697330
1125 37012635
1126 20057955
1127 8686916
1128 2349060
1129 2368660
1130 8797460
1131 20404956
1132 37829595
1133 61312020
1134 90767754
1135 125851110
1136 166011132
1137 210540330
1138 258616930
1139 309341318
1140 361767315
1141 414928878
1142 467862780
1143 519627780
1144 569320752
1145 616090200
1146 659147544
1147 697776520
1148 731340995
1149 759291456
1150 781170390
1151 796616730
1152 805369500
1153 807270750
1154 802267830
1155 790415010
1156 771874411
1157 746916170
1158 715917720
1159 679362024
1160 637834560
1161 592018812
1162 542689980
1163 490706580
1164 436999563
1165 382558540
1166 328414658
1167 275619630
1168 225220380
1169 178228722
1170 135585450
1171 98118174
1172 66492195
1173 41153670
1174 22264276
1175 9626540
1176 2598960
1177 2619785
1178 9744140
1179 22633884
1180 42024956
1181 68216505
1182 101148894
1183 140472486
1184 185608038
1185 235799487
1186 290159870
1187 347711078
1188 407418102
1189 468218387
1190 529046868
1191 588857220
1192 646639812
1193 701436813
1194 752354856
1195 798575624
1196 839364680
1197 874078821
1198 902172194
1199 923201370
1200 936829530
1201 942829875
1202 941088330
1203 931605570
1204 914498354
1205 890000111
1206 858460680
1207 820345064
1208 776231016
1209 726805233
1210 672857892
1211 615275220
1212 555029748
1213 493167857
1214 430794182
1215 369052398
1216 309101870
1217 252089607
1218 199116918
1219 151200126
1220 109224654
1221 73891755
1222 45657116
1223 24660524
1224 10645740
1225 2869685
1226 2891785
1227 10770690
1228 25053700
1229 46585084
1230 75730536
1231 112460754
1232 156425346
1233 207017910
1234 263433093
1235 324716392
1236 389807418
1237 457577302
1238 526860880
1239 596484252
1240 665288268
1241 732148452
1242 795991833
1243 855811110
1244 910676536
1245 959745864
1246 1002272656
1247 1037613214
1248 1065232350
1249 1084708170
1250 1095736005
1251 1098131580
1252 1091833470
1253 1076904850
1254 1053534504
1255 1022037016
1256 982852024
1257 936542376
1258 883790985
1259 825396138
1260 762264972
1261 695404788
1262 625911832
1263 554957130
1264 483768922
1265 413611198
1266 345757797
1267 281461488
1268 221917410
1269 168220206
1270 121314144
1271 81935476
1272 50546244
1273 27258700
1274 11749465
1275 3162510