1 1
2 5
3 6
4 15
5 29
6 21
7 35
8 85
9 99
10 56
11 70
12 195
13 285
14 259
15 126
16 126
17 385
18 645
19 735
20 574
21 252
22 210
23 686
24 1260
25 1645
26 1610
27 1134
28 462
29 330
30 1134
31 2226
32 3185
33 3570
34 3150
35 2058
36 792
37 495
38 1770
39 3654
40 5586
41 6860
42 6930
43 5670
44 3498
45 1287
46 715
47 2640
48 5670
49 9114
50 11956
51 13230
52 12390
53 9570
54 5643
55 2002
56 1001
57 3795
58 8415
59 14070
60 19404
61 22932
62 23520
63 20790
64 15345
65 8723
66 3003
67 1365
68 5291
69 12045
70 20790
71 29820
72 37044
73 40572
74 39270
75 33165
76 23595
77 13013
78 4368
79 1820
80 7189
81 16731
82 29645
83 43890
84 56700
85 65268
86 67452
87 62370
88 50765
89 35035
90 18837
91 6188
92 2380
93 9555
94 22659
95 41041
96 62370
97 83160
98 99540
99 108108
100 106722
101 95095
102 75075
103 50505
104 26572
105 8568
106 3060
107 12460
108 30030
109 55419
110 86086
111 117810
112 145530
113 164340
114 170478
115 162162
116 140140
117 107835
118 70980
119 36652
120 11628
121 3876
122 15980
123 39060
124 73255
125 115934
126 162162
127 205590
128 239580
129 258390
130 258258
131 238238
132 200655
133 151060
134 97580
135 49572
136 15504
137 4845
138 20196
139 49980
140 95060
141 152880
142 217854
143 282282
144 337590
145 375705
146 390390
147 378378
148 340158
149 280280
150 207060
151 131580
152 65892
153 20349
154 5985
155 25194
156 63036
157 121380
158 197960
159 286650
160 378378
161 462462
162 528165
163 566280
164 570570
165 538902
166 473928
167 383180
168 278460
169 174420
170 86241
171 26334
172 7315
173 31065
174 78489
175 152796
176 252280
177 370440
178 496860
179 618618
180 722007
181 794365
182 825825
183 810810
184 749112
185 646408
186 514080
187 368220
188 227715
189 111321
190 33649
191 8855
192 37905
193 96615
194 189924
195 317016
196 471240
197 640920
198 810810
199 963963
200 1083797
201 1156155
202 1171170
203 1124760
204 1019592
205 865368
206 678300
207 479655
208 293265
209 141911
210 42504
211 10626
212 45815
213 117705
214 233415
215 393414
216 591192
217 813960
218 1044120
219 1261260
220 1444443
221 1574573
222 1636635
223 1621620
224 1527960
225 1362312
226 1139544
227 881790
228 616455
229 373065
230 178871
231 53130
232 12650
233 54901
234 142065
235 283955
236 482790
237 732564
238 1019592
239 1323960
240 1621620
241 1886885
242 2095093
243 2225223
244 2262260
245 2199120
246 2037960
247 1790712
248 1478694
249 1131165
250 782705
251 469315
252 223146
253 65780
254 14950
255 65274
256 170016
257 342265
258 586530
259 897750
260 1261638
261 1656072
262 2053260
263 2422420
264 2732730
265 2956317
266 3071068
267 3063060
268 2928420
269 2674440
270 2319786
271 1893654
272 1433740
273 982905
274 584430
275 275770
276 80730
277 17550
278 77050
279 201894
280 409101
281 706090
282 1089270
283 1544130
284 2046528
285 2564892
286 3063060
287 3503500
288 3850665
289 4074252
290 4152148
291 4072860
292 3837240
293 3459330
294 2966166
295 2396394
296 1797565
297 1221990
298 721050
299 337870
300 98280
301 20475
302 90350
303 238050
304 485254
305 842996
306 1309770
307 1871310
308 2501730
309 3165723
310 3821532
311 4424420
312 4930380
313 5299840
314 5501132
315 5513508
316 5329500
317 4956435
318 4416930
319 3748206
320 3000074
321 2231460
322 1505350
323 882050
324 410670
325 118755
326 23751
327 105300
328 278850
329 571550
330 998844
331 1562022
332 2247630
333 3028410
334 3865455
335 4711278
336 5513508
337 6218940
338 6777680
339 7147140
340 7295652
341 7205484
342 6875055
343 6320160
344 5574030
345 4686066
346 3719100
347 2745050
348 1838850
349 1070550
350 495495
351 142506
352 27405
353 122031
354 324675
355 668850
356 1175300
357 1848924
358 2677752
359 3633630
360 4674285
361 5746455
362 6789783
363 7741188
364 8539440
365 9129680
366 9467640
367 9523332
368 9283989
369 8756055
370 7966035
371 6960030
372 5801796
373 4569180
374 3348800
375 2228850
376 1289925
377 593775
378 169911
379 31465
380 140679
381 375921
382 778050
383 1374100
384 2173500
385 3166548
386 4324782
387 5602905
388 6941935
389 8273265
390 9523332
391 10618608
392 11490640
393 12080880
394 12345060
395 12256881
396 11810799
397 11023705
398 9935310
399 8607060
400 7119420
401 5567380
402 4054050
403 2682225
404 1543815
405 707049
406 201376
407 35960
408 161385
409 432999
410 900081
411 1597050
412 2538900
413 3719100
414 5109588
415 6662502
416 8313305
417 9984975
418 11592945
419 13050492
420 14274288
421 15189840
422 15736560
423 15872220
424 15576561
425 14853839
426 13734105
427 12273030
428 10550100
429 8665020
430 6732180
431 4873050
432 3206385
433 1836135
434 836969
435 237336
436 40920
437 184295
438 496335
439 1035909
440 1846026
441 2948400
442 4340700
443 5996100
444 7864758
445 9876867
446 11946935
447 13978965
448 15872220
449 17527272
450 18852048
451 19767600
452 20213340
453 20151495
454 19570551
455 18487469
456 16948470
457 15028200
458 12827100
459 10466820
460 8083530
461 5818995
462 3809295
463 2171085
464 985304
465 278256
466 46376
467 209560
468 566370
469 1186535
470 2122974
471 3405402
472 5036850
473 6992700
474 9221850
475 11649638
476 14182168
477 16711695
478 19122740
479 21298620
480 23128092
481 24511824
482 25368420
483 25639740
484 25295270
485 24335311
486 22792770
487 20733350
488 18253950
489 15479100
490 12555270
491 9642906
492 6906060
493 4499495
494 2553160
495 1153944
496 324632
497 52360
498 237336
499 643560
500 1352995
501 2429910
502 3913434
503 5813262
504 8108100
505 10746450
506 13649350
507 16714698
508 19822803
509 22842820
510 25639740
511 28081620
512 30046752
513 31430484
514 32151420
515 32156740
516 31426395
517 29975946
518 27857830
519 25160850
520 22007700
521 18550350
522 14963130
523 11433366
524 8149435
525 5286120
526 2987160
527 1344904
528 376992
529 58905
530 267784
531 728376
532 1536360
533 2768920
534 4476150
535 6675858
536 9351342
537 12451725
538 15894450
539 19569550
540 23345322
541 27075048
542 30604420
543 33779340
544 36453780
545 38497401
546 39802644
547 40291020
548 39918340
549 38678640
550 36606570
551 33778030
552 30308850
553 26351325
554 22088430
555 17725554
556 13479606
557 9565360
558 6178920
559 3478200
560 1560328
561 435897
562 66045
563 301070
564 821304
565 1737736
566 3142160
567 5097330
568 7630770
569 10731798
570 14351337
571 18404100
572 22772750
573 27313650
574 31863832
575 36248828
576 40291020
577 43818180
578 46671885
579 48715506
580 49841484
581 49977620
582 49092120
583 47197150
584 44350670
585 40656330
586 36261225
587 31351320
588 26144370
589 20880174
590 15808016
591 11171160
592 7188280
593 4031720
594 1802493
595 501942
596 73815
597 337365
598 922845
599 1958264
600 3551856
601 5780880
602 8684340
603 12259170
604 16459443
605 21198177
606 26351325
607 31763550
608 37255400
609 42631512
610 47689488
611 52229100
612 56061495
613 59018085
614 60958821
615 61779564
616 61418280
617 59859800
618 57138900
619 53341470
620 48603555
621 43108065
622 37078965
623 30772770
624 24467184
625 18446736
626 12985280
627 8325240
628 4653495
629 2073813
630 575757
631 82251
632 376845
633 1033515
634 2199120
635 4000304
636 6530832
637 9843120
638 13943490
639 18790695
640 24297273
641 30333303
642 36732150
643 43297800
644 49813400
645 56050632
646 61779564
647 66778635
648 70844445
649 73801035
650 75508356
651 75869640
652 74837400
653 72417800
654 68673150
655 63722295
656 57738681
657 50945895
658 43610490
659 36031920
660 28529424
661 21425712
662 15027320
663 9601515
664 5349645
665 2376843
666 658008
667 91390
668 419691
669 1153845
670 2461515
671 4489870
672 7351344
673 11113872
674 15795120
675 21360240
676 27722695
677 34747713
678 42257943
679 50040900
680 57857800
681 65453400
682 72566472
683 78940554
684 84334635
685 88533445
686 91357035
687 92669346
688 92385480
689 90477400
690 86977800
691 81981900
692 75646935
693 68189121
694 59877895
695 51027240
696 41983920
697 33112464
698 24776752
699 17318070
700 11029515
701 6126645
702 2714283
703 749398
704 101270
705 466089
706 1284381
707 2746695
708 5022990
709 8246700
710 12503568
711 17824752
712 24183720
713 31496465
714 39624585
715 48380787
716 57536388
717 66830400
718 75979800
719 84690600
720 92669346
721 99634689
722 105328685
723 109527495
724 112051170
725 112772220
726 111622680
727 108599400
728 103767300
729 97260345
730 89280009
731 80091011
732 70014120
733 59415840
734 48694800
735 38264688
736 28533582
737 19879545
738 12622365
739 6991335
740 3088982
741 850668
742 111930
743 516230
744 1425684
745 3055941
746 5602170
747 9221310
748 14019390
749 20043408
750 27277272
751 35641320
752 44994950
753 55141905
754 65837772
755 76799268
756 87714900
757 98256600
758 108091950
759 116896626
760 124366704
761 130230485
762 134259510
763 136278450
764 136173570
765 133899480
766 129483900
767 123030180
768 114717330
769 104797329
770 93589496
771 81471720
772 68868360
773 56234640
774 44037378
775 32731902
776 22735020
777 14393925
778 7950930
779 3503942
780 962598
781 123410
782 570310
783 1578330
784 3390569
785 6229986
786 10279710
787 15668730
788 22462440
789 30657528
790 40180712
791 50890840
792 62583885
793 75000380
794 87834852
795 100746828
796 113373000
797 125340150
798 136278450
799 145834766
800 153685609
801 159549390
802 163197650
803 164464950
804 163257120
805 159557580
806 153431460
807 145027260
808 134575805
809 122386264
810 108839016
811 94375160
812 79482480
813 64677690
814 50484798
815 37409442
816 25909065
817 16358810
818 9013030
819 3962322
820 1086008
821 135751
822 628530
823 1742910
824 3751930
825 6909084
826 11426562
827 17459190
828 25093530
829 34341615
830 45138808
831 57345288
832 70750680
833 85081360
834 100009980
835 115166772
836 130152204
837 144550575
838 157944150
839 169927450
840 180121326
841 188186460
842 193835950
843 196846650
844 197068950
845 194434695
846 188962956
847 180763380
848 170036860
849 157073280
850 142246104
851 126003592
852 108856440
853 91361655
854 74102490
855 57664278
856 42606018
857 29427580
858 18532410
859 10185630
860 4467442
861 1221759
862 148995
863 691096
864 1920030
865 4141410
866 7642180
867 12666654
868 19398582
869 27948690
870 38347155
871 50540490
872 64392328
873 79687608
874 96139680
875 113399860
876 131068980
877 148710492
878 165864699
879 182063700
880 196846650
881 209774950
882 220446996
883 228512130
884 233683450
885 235749150
886 234582075
887 230147190
888 222506676
889 211822380
890 198355360
891 182462280
892 164588424
893 145257112
894 125055315
895 104615280
896 84591990
897 65636298
898 48363588
899 33317830
900 20930910
901 11477130
902 5022787
903 1370754
904 163185
905 758219
906 2110311
907 4560430
908 8432060
909 14004900
910 21494928
911 31040262
912 42692265
913 56411355
914 72066995
915 89441352
916 108236128
917 128082080
918 148550760
919 169168020
920 189428841
921 208813059
922 226801575
923 242892650
924 256617900
925 267557620
926 275355080
927 279729450
928 280487025
929 277530435
930 270865539
931 260605716
932 246973280
933 230297760
934 211010800
935 189637448
936 166783617
937 143119515
938 119358855
939 96233670
940 74464572
941 54726308
942 37608480
943 23571310
944 12896345
945 5632011
946 1533939
947 178365
948 830115
949 2314389
950 5010446
951 9281580
952 15446340
953 23756460
954 34380918
955 47395557
956 62777715
957 80405325
958 100059960
959 121433312
960 144136608
961 167712480
962 191648820
963 215394165
964 238374171
965 260008749
966 279729450
967 296996700
968 311316500
969 322256220
970 329459130
971 332657325
972 331682715
973 326475765
974 317091684
975 303703776
976 286603680
977 266198240
978 243002760
979 217630413
980 190777587
981 163204965
982 135714150
983 109119660
984 84216132
985 61740588
986 42329630
987 26471445
988 14452515
989 6298941
990 1712304
991 194580
992 907005
993 2532915
994 5492949
995 10193666
996 16996140
997 26191620
998 37983660
999 52476138
1000 69666597
1001 89444355
1002 111592845
1003 135795660
1004 161645792
1005 188657568
1006 216280800
1007 243916680
1008 270934965
1009 296692011
1010 320549229
1011 341891550
1012 360145500
1013 374796500
1014 385405020
1015 391621230
1016 393197805
1017 390000555
1018 382016565
1019 369359544
1020 352272096
1021 331124640
1022 306410720
1023 278738460
1024 248817933
1025 217444227
1026 185476005
1027 153809370
1028 123346860
1029 94961412
1030 69455148
1031 47512850
1032 29650005
1033 16155315
1034 7027581
1035 1906884
1036 211876
1037 989115
1038 2766555
1039 6009465
1040 11171314
1041 18659592
1042 28809060
1043 41861820
1044 57953610
1045 77105743
1046 99222123
1047 124090785
1048 151389420
1049 180694360
1050 211492512
1051 243195744
1052 275157240
1053 306689355
1054 337082515
1055 365624721
1056 391621230
1057 414414000
1058 433400500
1059 448051500
1060 457927470
1061 462693231
1062 462130515
1063 456148105
1064 444789240
1065 428235984
1066 406810272
1067 380971360
1068 351309420
1069 318535035
1070 283464363
1071 246999753
1072 210105610
1073 173779320
1074 139017060
1075 106774332
1076 77921074
1077 53191215
1078 33126555
1079 18014865
1080 7822116
1081 2118760
1082 230300
1083 1076676
1084 3015990
1085 6561555
1086 12217590
1087 20442114
1088 31617642
1089 46029060
1090 63848070
1091 85123610
1092 109777668
1093 137605923
1094 168282660
1095 201369420
1096 236326860
1097 272529312
1098 309281544
1099 345837240
1100 381418730
1101 415237515
1102 446515146
1103 474504030
1104 498507750
1105 517900500
1106 532145250
1107 540810270
1108 543583656
1109 540285515
1110 530877480
1111 515469240
1112 494321784
1113 467847072
1114 436603860
1115 401289420
1116 362726910
1117 321848163
1118 279671678
1119 237275610
1120 195765570
1121 156237060
1122 119732382
1123 87191874
1124 59399340
1125 36921555
1126 20041740
1127 8686916
1128 2349060
1129 249900
1130 1169924
1131 3281916
1132 7150815
1133 13335630
1134 22349250
1135 34626438
1136 50499372
1137 70180110
1138 93749370
1139 121151030
1140 152191767
1141 186545268
1142 223760460
1143 263273220
1144 304421040
1145 346460136
1146 388584504
1147 429946440
1148 469678055
1149 506913330
1150 540810270
1151 570572730
1152 595471500
1153 614864250
1154 628213950
1155 635105394
1156 635259471
1157 628544840
1158 614986680
1159 594772200
1160 568252608
1161 535941252
1162 498507660
1163 456767220
1164 411666255
1165 364262262
1166 315699098
1167 267176910
1168 219916620
1169 175118790
1170 133916706
1171 97323534
1172 66173415
1173 41056380
1174 22246980
1175 9626540
1176 2598960
1177 270725
1178 1269100
1179 3565044
1180 7778876
1181 14528640
1182 24386670
1183 37844730
1184 55287078
1185 76970817
1186 103012910
1187 133383250
1188 167903190
1189 206248952
1190 247959348
1191 292447260
1192 339014340
1193 386868405
1194 435143016
1195 482918744
1196 529245640
1197 573166440
1198 613740050
1199 650064870
1200 681301530
1201 706694625
1202 725593050
1203 737468550
1204 741932114
1205 738747856
1206 727844040
1207 709320920
1208 683455080
1209 650699973
1210 611682372
1211 567194460
1212 518181300
1213 465723440
1214 411014422
1215 355332978
1216 300009710
1217 246388065
1218 195779430
1219 149412186
1220 108374574
1221 73551240
1222 45553340
1223 24642100
1224 10645740
1225 2869685
1226 292825
1227 1374450
1228 3866100
1229 8447404
1230 15799896
1231 26560170
1232 41282010
1233 60406830
1234 84241773
1235 112944832
1236 146516370
1237 184796430
1238 227467240
1239 274060332
1240 323967708
1241 376456500
1242 430686585
1243 485730630
1244 540596056
1245 594248424
1246 645635760
1247 693713350
1248 737468550
1249 775945170
1250 808267005
1251 833660100
1252 851473350
1253 861197050
1254 862479024
1255 855137976
1256 839173720
1257 814773960
1258 782317305
1259 742372218
1260 695691612
1261 643202820
1262 585992680
1263 525287490
1264 462427602
1265 398836438
1266 335983725
1267 275342760
1268 218341530
1269 166307526
1270 120406104
1271 81572260
1272 50435700
1273 27239100
1274 11749465
1275 3162510