1 0
2 105
3 385
4 1365
5 1785
6 2805
7 3135
8 10353
9 6545
10 12155
11 21385
12 11165
13 21505
14 10465
15 16555
16 19285
17 37961
18 35105
19 18445
20 24395
21 23205
22 53669
23 11305
24 28595
25 17255
26 36465
27 20615
28 42315
29 123585
30 31535
31 49335
32 39585
33 61295
34 35805
35 72709
36 54285
37 130515
38 45885
39 55335
40 33495
41 49665
42 115005
43 172159
44 99671
45 58695
46 91245
47 64515
48 86955
49 33915
50 76755
51 88179
52 141015
53 51765
54 93093
55 150195
56 111435
57 190905
58 147345
59 26565
60 99015
61 95095
62 219945
63 72105
64 150423
65 148665
66 219219
67 85085
68 141491
69 156009
70 188309
71 286143
72 47355
73 103845
74 198645
75 139965
76 242535
77 119595
78 378885
79 227715
80 240465
81 363165
82 151249
83 218085
84 155595
85 194649
86 217005
87 218595
88 167739
89 168245
90 383061
91 124845
92 399855
93 529023
94 253605
95 140415
96 124355
97 270655
98 87087
99 250305
100 248235
101 242165
102 138567
103 192907
104 247665
105 355395
106 313131
107 304095
108 711645
109 424473
110 212135
111 245157
112 323609
113 434343
114 126555
115 437437
116 431585
117 347415
118 770847
119 293227
120 177045
121 141141
122 150535
123 295295
124 257439
125 137085
126 245427
127 363545
128 372099
129 243165
130 651035
131 113685
132 198835
133 595815
134 226005
135 565915
136 754985
137 130845
138 107445
139 428127
140 250705
141 256785
142 553267
143 265265
144 565565
145 79365
146 196365
147 196707
148 343805
149 307515
150 281435
151 376805
152 210045
153 480909
154 280995
155 338793
156 335445
157 386155
158 260205
159 561085
160 818961
161 155155
162 335335
163 767949
164 274505
165 236379
166 352495
167 92235
168 494715
169 602085
170 445445
171 312455
172 115115
173 548709
174 611065
175 146965
176 467115
177 166155
178 794703
179 650845
180 1129645
181 808197
182 489335
183 239785
184 699335
185 457765
186 312169
187 316635
188 638365
189 324415
190 353073
191 90915
192 491205
193 292929
194 620103
195 115995
196 62205
197 205205
198 1171555
199 644215
200 184965
201 860405
202 700077
203 524433
204 1386957
205 421135
206 599955
207 852397
208 874055
209 191235
210 443555
211 471835
212 509795
213 540995
214 657685
215 723045
216 314545
217 260015
218 1122539
219 737373
220 469315
221 472719
222 858935
223 567987
224 231495
225 817817
226 226765
227 515185
228 310947
229 1175405
230 682689
231 418285
232 1680679
233 533577
234 1003255
235 232323
236 1242241
237 606515
238 801515
239 323323
240 865865
241 424235
242 299915
243 646737
244 456365
245 1386385
246 363055
247 460317
248 199563
249 1291677
250 387205
251 622167
252 245973
253 914277
254 230945
255 1329055
256 474747
257 393965
258 1361815
259 669515
260 1274405
261 305305
262 1723205
263 682465
264 685685
265 627095
266 218127
267 540155
268 1802185
269 303485
270 1427127
271 449735
272 975821
273 1726235
274 429065
275 847385
276 631085
277 1100757
278 235235
279 385917
280 921417
281 970255
282 1471015
283 1208305
284 824619
285 1133445
286 820105
287 134805
288 936663
289 1299155
290 865469
291 1861145
292 940355
293 1069453
294 474145
295 450177
296 748055
297 933317
298 1114971
299 762755
300 1165945
301 418605
302 2033395
303 1352065
304 1071289
305 1265667
306 1121285
307 521157
308 256795
309 1338117
310 2012615
311 354445
312 662935
313 1752905
314 1346345
315 1081115
316 1764763
317 843115
318 1342671
319 1212365
320 703703
321 802655
322 2492455
323 1890655
324 2208437
325 1590699
326 920227
327 319865
328 303807
329 1151495
330 1082081
331 1269543
332 409045
333 911183
334 1097215
335 709527
336 1388387
337 1968685
338 2429679
339 1404455
340 215215
341 2637985
342 902451
343 531335
344 902785
345 504339
346 1473745
347 485485
348 480095
349 380765
350 942865
351 989989
352 1644909
353 1176791
354 1097679
355 1547799
356 743015
357 1551935
358 2626715
359 40755
360 458367
361 2094235
362 2994761
363 638435
364 1116115
365 1072445
366 3358515
367 2220295
368 1432795
369 1205435
370 2478021
371 1261645
372 560945
373 1151403
374 701155
375 689605
376 876785
377 2703415
378 1564745
379 371735
380 521885
381 1324015
382 1003145
383 1127665
384 145145
385 1982695
386 1784915
387 1176385
388 1165197
389 1526855
390 617435
391 572033
392 416185
393 2100813
394 2339155
395 2061059
396 1452815
397 106743
398 2007445
399 1095185
400 885003
401 1216285
402 1010735
403 1166795
404 1852405
405 910195
406 269997
407 267995
408 713713
409 1593865
410 2203355
411 1777555
412 1629485
413 1560845
414 550137
415 1018045
416 667667
417 2872415
418 1288105
419 894355
420 2148545
421 1860565
422 1543685
423 1074073
424 1300915
425 1009855
426 1959685
427 1332695
428 1846285
429 2375659
430 1816705
431 1728335
432 976745
433 2802063
434 171717
435 1122121
436 1563065
437 579215
438 3468621
439 1817255
440 787865
441 2311595
442 2517235
443 1087541
444 2262995
445 1092845
446 1043119
447 1182545
448 1113915
449 1392985
450 1167595
451 2479015
452 2223515
453 1768085
454 919555
455 1512885
456 1480955
457 1342915
458 2234427
459 1275681
460 2431765
461 974545
462 2430065
463 924715
464 721259
465 1502501
466 2985455
467 2520245
468 931385
469 510055
470 747565
471 1834595
472 2415985
473 1981265
474 2087435
475 1436001
476 1137955
477 1193465
478 5675015
479 4097555
480 1026069
481 1246355
482 524755
483 1471379
484 1439305
485 2371369
486 449995
487 725305
488 2221765
489 1905085
490 1174745
491 1962961
492 2323915
493 1381471
494 1261715
495 3416665
496 1261315
497 1595671
498 1540045
499 1923635
500 2683655
501 4130885
502 676039
503 988715
504 2317107
505 916895
506 2370633
507 1856435
508 1740739
509 1556401
510 1458821
511 1307735
512 2428855
513 5693597
514 2456245
515 2483195
516 1646255
517 2493985
518 1992445
519 3937465
520 2150687
521 2701895
522 2709035
523 2881585
524 1125145
525 1245013
526 1298885
527 1705865
528 2099279
529 4536543
530 1881607
531 2382501
532 255255
533 2866435
534 1194655
535 1958349
536 3834061
537 2785685
538 657305
539 2197559
540 741455
541 795685
542 578305
543 2142085
544 4538555
545 2260405
546 1906555
547 779779
548 2238985
549 3850483
550 3738385
551 608399
552 1184365
553 1929109
554 3539263
555 1385615
556 891605
557 2209235
558 5355343
559 6716255
560 926695
561 851851
562 2883965
563 3805795
564 2304757
565 2378545
566 4432505
567 2868943
568 1696695
569 3936779
570 4380393
571 1621477
572 1842335
573 1839695
574 2135067
575 682341
576 3438743
577 2619435
578 1598799
579 2920379
580 960245
581 4228835
582 1456455
583 1194505
584 4383205
585 279565
586 1869049
587 1490645
588 1179035
589 1678061
590 1897805
591 2220995
592 826735
593 2692235
594 3506335
595 1654015
596 2792867
597 776815
598 1487585
599 1898195
600 771001
601 1578577
602 2258815
603 705705
604 881705
605 1067605
606 682955
607 1990345
608 2074345
609 3593681
610 2200055
611 1112735
612 3295705
613 2775773
614 3112105
615 885885
616 2289815
617 1569685
618 451605
619 1868555
620 4306939
621 2129335
622 2579665
623 5563415
624 2425787
625 1864265
626 2399199
627 2478245
628 2456377
629 2299115
630 2700565
631 1232777
632 4575805
633 1592591
634 2703701
635 2601599
636 3083487
637 1554371
638 1998535
639 4800341
640 3058895
641 4114145
642 2175745
643 707135
644 1422785
645 1467389
646 498355
647 3203837
648 2174113
649 3696055
650 3169285
651 2932941
652 1268795
653 2446535
654 3752903
655 2412487
656 2439619
657 1601985
658 1966965
659 3185273
660 2007785
661 804895
662 2630355
663 2247035
664 863005
665 3876665
666 1708993
667 2355177
668 2346253
669 2593367
670 4481015
671 4010997
672 5127965
673 799799
674 1994069
675 2731135
676 2581865
677 2181865
678 4818205
679 3446665
680 922845
681 4726345
682 1693835
683 1458457
684 3158617
685 3506165
686 859677
687 3433507
688 3432759
689 5037851
690 2724995
691 3705779
692 567385
693 2460563
694 902615
695 4447795
696 1012035
697 3776003
698 3017105
699 2239699
700 4313309
701 1081795
702 943943
703 1804465
704 3402091
705 2498881
706 3334177
707 6491065
708 805035
709 1279915
710 2921721
711 3758105
712 4473469
713 5460961
714 6969599
715 2671669
716 3021865
717 5846015
718 3581123
719 3229135
720 4800103
721 5113185
722 5019365
723 2382567
724 1569799
725 2602565
726 1875445
727 3166735
728 2671305
729 4096495
730 1042015
731 2576945
732 976885
733 1720355
734 2495935
735 3746171
736 2956723
737 2044263
738 3657621
739 3578245
740 2129855
741 6567995
742 5843915
743 938315
744 1063335
745 1227655
746 3823589
747 3116399
748 4350385
749 1600655
750 1531257
751 3388099
752 2147665
753 2248631
754 2895865
755 6102915
756 3445585
757 4216135
758 6481239
759 4153695
760 4880435
761 2189845
762 4204865
763 2622165
764 1407805
765 4891733
766 4457635
767 1006005
768 4297205
769 613795
770 1709981
771 3976895
772 3862045
773 4231997
774 2579269
775 2902835
776 2749747
777 1200485
778 755755
779 5403827
780 834785
781 2629627
782 5299385
783 504735
784 8211147
785 5057585
786 1431859
787 1096095
788 4066855
789 2543387
790 3609905
791 1689545
792 3896893
793 4699695
794 5104505
795 615615
796 5375195
797 3424655
798 1218945
799 620823
800 4273555
801 2673471
802 3810499
803 2139995
804 4673095
805 2392115
806 1742585
807 6173635
808 3212065
809 1985515
810 1364363
811 2606015
812 4373369
813 672945
814 2915341
815 1124193
816 3493105
817 6091865
818 3240523
819 620165
820 3872365
821 2556785
822 5603455
823 4639355
824 1928927
825 2837555
826 2416227
827 3730531
828 1066065
829 2197811
830 1547455
831 4674865
832 522665
833 1650649
834 5480995
835 2456619
836 3879295
837 3256505
838 6046271
839 4320505
840 10444551
841 908765
842 1040655
843 2446773
844 2503193
845 2698465
846 2693735
847 554645
848 5771535
849 2968693
850 2149945
851 6682949
852 2850033
853 4989413
854 3577701
855 6834289
856 1248555
857 5291405
858 1186185
859 2651165
860 3644465
861 2724505
862 674245
863 5802115
864 1288599
865 2267265
866 2013715
867 5704699
868 2842609
869 3592589
870 2965735
871 3595823
872 4241237
873 5028107
874 3105245
875 3573349
876 2623985
877 3880301
878 2482935
879 5300603
880 2023595
881 1941995
882 3513917
883 3468595
884 1924111
885 1926015
886 5816965
887 5987485
888 1947295
889 9959105
890 3123219
891 1747515
892 1774885
893 4159155
894 2065245
895 3951395
896 1903265
897 8849995
898 2108561
899 7399721
900 5005429
901 4295915
902 3942085
903 2465255
904 6647207
905 5735093
906 3732911
907 8531887
908 6156095
909 2225685
910 1839383
911 4515863
912 3030181
913 7478427
914 5798343
915 6024137
916 458185
917 1751035
918 3459755
919 951405
920 1238705
921 4397393
922 2732345
923 3031457
924 3263915
925 5583565
926 3999215
927 2706145
928 5567653
929 4478565
930 2296945
931 3407565
932 6567253
933 4570951
934 2308215
935 6167447
936 6915265
937 1422435
938 3494309
939 4120611
940 4628267
941 5014405
942 5552183
943 3814573
944 4191187
945 3037895
946 4856033
947 3064165
948 2657473
949 2750041
950 6308071
951 1873235
952 4617795
953 1560685
954 7316491
955 2707215
956 3321409
957 4069065
958 2372435
959 3243345
960 7355985
961 1824361
962 3398549
963 2873045
964 3686969
965 5164523
966 4791059
967 4615985
968 8073989
969 6364715
970 3399745
971 4412435
972 5059795
973 5034029
974 3377101
975 5682495
976 555555
977 2997015
978 7679287
979 5264441
980 2030435
981 3406795
982 4665089
983 7439795
984 3503955
985 5942163
986 1516515
987 1567335
988 1246245
989 7844935
990 3278015
991 4417127
992 4585555
993 2393335
994 5472929
995 4574801
996 3080735
997 4592357
998 5541445
999 2331329
1000 5802049