1 1
2 7
3 19
4 44
5 61
6 133
7 127
8 256
9 297
10 427
11 331
12 836
13 469
14 889
15 1159
16 1408
17 817
18 2079
19 1027
20 2684
21 2413
22 2317
23 1519
24 4864
25 2825
26 3283
27 4131
28 5588
29 2437
30 8113
31 2791
32 7424
33 6289
34 5719
35 7747
36 13068
37 3997
38 7189
39 8911
40 15616
41 4921
42 16891
43 5419
44 14564
45 18117
46 10633
47 6487
48 26752
49 11809
50 19775
51 15523
52 20636
53 8269
54 28917
55 20191
56 32512
57 19513
58 17059
59 10267
60 50996
61 10981
62 19537
63 37719
64 37888
65 28609
66 44023
67 13267
68 35948
69 28861
70 54229
71 14911
72 76032
73 15769
74 27979
75 53675
76 45188
77 42037
78 62377
79 18487
80 85888
81 53217
82 34447
83 20419
84 106172
85 49837
86 37933
87 46303
88 84736
89 23497
90 126819
91 59563
92 66836
93 53029
94 45409
95 62647
96 141056
97 27937
98 82663
99 98307
100 124300
101 30301
102 108661
103 31519
104 120064
105 147193
106 57883
107 34027
108 181764
109 35317
110 141337
111 75943
112 178816
113 37969
114 136591
115 92659
116 107228
117 139293
118 71869
119 103759
120 296704
121 77561
122 76867
123 93499
124 122804
125 113125
126 264033
127 48007
128 188416
129 102961
130 200263
131 51091
132 276716
133 130429
134 92869
135 251991
136 209152
137 55897
138 202027
139 57547
140 340868
141 123253
142 104377
143 155239
144 418176
145 148657
146 110383
147 224371
148 175868
149 66157
150 375725
151 67951
152 262912
153 242649
154 294259
155 170251
156 392084
157 73477
158 129409
159 157111
160 452864
161 192913
162 372519
163 79219
164 216524
165 383629
166 142933
167 83167
168 617728
169 154297
170 348859
171 305019
172 238436
173 89269
174 324121
175 358775
176 466048
177 195073
178 164479
179 95587
180 797148
181 97741
182 416941
183 208639
184 388864
185 243817
186 371203
187 270427
188 285428
189 524637
190 438529
191 108871
192 719872
193 111169
194 195559
195 543571
196 519596
197 115837
198 688149
199 118207
200 723200
201 252073
202 212107
203 309499
204 683012
205 300181
206 220633
207 451143
208 660352
209 339937
210 1030351
211 132931
212 363836
213 283309
214 238189
215 330559
216 1057536
217 354457
218 247219
219 299611
220 888404
221 383173
222 531601
223 148519
224 942848
225 839025
226 265783
227 153907
228 858572
229 156637
230 648613
231 798703
232 623872
233 162169
234 975051
235 395707
236 451748
237 351253
238 726313
239 170647
240 1631872
241 173521
242 542927
243 649539
244 483164
245 720349
246 654493
247 481663
248 714496
249 387961
250 791875
251 188251
252 1659636
253 502789
254 336049
255 946903
256 917504
257 197377
258 720727
259 507619
260 1258796
261 723789
262 357637
263 206719
264 1609984
265 504409
266 913003
267 446443
268 583748
269 216277
270 1763937
271 219511
272 1150336
273 1131697
274 391279
275 935075
276 1269884
277 229357
278 402829
279 828927
280 1983232
281 236041
282 862771
283 239419
284 656084
285 1190293
286 1086673
287 624967
288 2204928
289 462689
290 1040599
291 530803
292 693836
293 256669
294 1570597
295 626287
296 1023232
297 1367361
298 463099
299 712411
300 2361700
301 688213
302 475657
303 575719
304 1446016
305 669841
306 1698543
307 281827
308 1849628
309 598861
310 1191757
311 289231
312 2281216
313 292969
314 514339
315 2300859
316 813428
317 300517
318 1099777
319 806647
320 2311168
321 646513
322 1350391
323 839059
324 2341548
325 1324925
326 554533
327 671023
328 1259776
329 823849
330 2685403
331 327691
332 898436
333 1187109
334 582169
335 809287
336 3397504
337 339697
338 1080079
339 721411
340 2192828
341 923821
342 2135133
343 938791
344 1387264
345 1760521
346 624883
347 360187
348 2037332
349 364357
350 2511425
351 1937439
352 2457344
353 372769
354 1365511
355 909571
356 1033868
357 1971421
358 669109
359 385567
360 4637952
361 728137
362 684187
363 1473659
364 2620772
365 961909
366 1460473
367 402967
368 2138752
369 1461537
370 1706719
371 1050163
372 2333276
373 416269
374 1892989
375 2149375
376 1660672
377 1142953
378 3672459
379 429787
380 2756468
381 912133
382 762097
383 438919
384 3579904
385 2564257
386 778183
387 1609443
388 1229228
389 452797
390 3804997
391 1241023
392 3023104
393 970729
394 810859
395 1127707
396 4325508
397 471637
398 827449
399 2478151
400 3977600
401 481201
402 1764511
403 1308979
404 1333244
405 3246237
406 2166493
407 1323007
408 3973888
409 500617
410 2101267
411 1062043
412 1386836
413 1303909
414 3158001
415 1245559
416 3481856
417 1093393
418 2379559
419 525427
420 6476492
421 530461
422 930517
423 1926639
424 2116864
425 2308025
426 1983163
427 1394587
428 1497188
429 2949541
430 2313913
431 555991
432 5816448
433 561169
434 2481199
435 2824483
436 1553948
437 1560013
438 2097277
439 576847
440 5168896
441 3507273
442 2682211
443 587419
444 3341492
445 1433317
446 1039633
447 1256983
448 4811776
449 603457
450 5873175
451 1628851
452 1670636
453 1291069
454 1077349
455 3633343
456 4995328
457 625177
458 1096459
459 3375027
460 4076996
461 636181
462 5590921
463 641719
464 3431296
465 3234769
466 1135183
467 652867
468 6128892
469 1684909
470 2769949
471 1396063
472 2628352
473 1793689
474 2458771
475 2901275
476 4565396
477 2455893
478 1194529
479 686887
480 8604416
481 1874593
482 1214647
483 3665347
484 3412684
485 1704157
486 4546773
487 710047
488 2811136
489 1505161
490 5042443
491 721771
492 4113956
493 1991029
494 3371641
495 5996727
496 3929728
497 1893697
498 2715727
499 745507
500 4977500
501 1580173
502 1317757
503 757519
504 9656064
505 1848361
506 3519523
507 2931643
508 2112308
509 775717
510 6628321
511 2002663
512 4390912
513 4242537
514 1381639
515 1922659
516 4530284
517 2147197
518 3553333
519 1696111
520 7323904
521 812761
522 5066523
523 819019
524 2248004
525 6816725
526 1447033
527 2280247
528 8854912
529 1583297
530 3530863
531 3049299
532 5738876
533 2307949
534 3125101
535 2075647
536 3396352
537 1816153
538 1513939
539 3908779
540 11087604
541 876421
542 1536577
543 1857079
544 6065408
545 2154337
546 7921879
547 895987
548 2459468
549 3261357
550 6545525
551 2502799
552 7388416
553 2347849
554 1605499
555 4632523
556 2532068
557 929077
558 5802489
559 2541511
560 10907776
561 5138113
562 1652287
563 949219
564 5423132
565 2316109
566 1675933
567 6758559
568 3817216
569 969577
570 8332051
571 976411
572 6830516
573 2068549
574 4374769
575 4291175
576 11252736
577 997057
578 3238823
579 2112211
580 6540908
581 2593213
582 3715621
583 2737039
584 4036864
585 8496873
586 1796683
587 1031947
588 9872324
589 2866357
590 4384009
591 2200903
592 5627776
593 1053169
594 9571527
595 6329299
596 2910908
597 2245933
598 4986877
599 1074607
600 13740800
601 1081801
602 4817491
603 3940299
604 2989844
605 4731221
606 4030033
607 1103527
608 7624448
609 5880481
610 4688887
611 3042403
612 10676556
613 1125469
614 1972789
615 5703439
616 10761472
617 1140217
618 4192027
619 1147627
620 7491044
621 6274989
622 2024617
623 2984119
624 12546688
625 4140625
626 2050783
627 6458803
628 3232988
629 3265549
630 16106013
631 1192591
632 4732672
633 2525689
634 2103619
635 2928427
636 6912884
637 5538421
638 5646529
639 4428567
640 11493376
641 1230721
642 4525591
643 1238419
644 8488172
645 6280621
646 5873413
647 1253887
648 13623552
649 3398377
650 9274475
651 6734683
652 3485636
653 1277269
654 4697161
655 3116551
656 6928768
657 4683393
658 5766943
659 1300867
660 16879676
661 1308781
662 2293837
663 7280287
664 5227264
665 7956169
666 8309763
667 3701803
668 3659348
669 2821861
670 5665009
671 3634711
672 17914112
673 1356769
674 2377879
675 11670075
676 6789068
677 1372957
678 5049877
679 3547999
680 12758272
681 2924233
682 6466747
683 1397419
684 13420836
685 3409717
686 6571537
687 2976103
688 7629952
689 3878161
690 12323647
691 1430371
692 3927836
693 12484989
694 2521309
695 3510367
696 11853568
697 4020457
698 2550499
699 3081211
700 15786100
701 1472101
702 13562073
703 4104919
704 12540928
705 7518433
706 2609383
707 3848227
708 8583212
709 1505917
710 6366997
711 5490639
712 6015232
713 4239529
714 13799947
715 9469579
716 4205828
717 3242293
718 2698969
719 1548727
720 25508736
721 4002913
722 5096959
723 3296899
724 4300604
725 6884525
726 10315613
727 1583407
728 15248128
729 7617321
730 6733363
731 4427323
732 9180116
733 1609669
734 2820769
735 13686631
736 11277056
737 4391377
738 10230759
739 1636147
740 10727948
741 9151597
742 7351141
743 1653919
744 13575424
745 4035577
746 2913883
747 6064443
748 11898788
749 4321429
750 15045625
751 1689751
752 9133696
753 3576769
754 8000671
755 4145011
756 23084028
757 1716877
758 3008509
759 9552991
760 16037632
761 1735081
762 6384931
763 4485259
764 4790324
765 14801589
766 3072433
767 4815223
768 17432576
769 1771777
770 17949799
771 3750163
772 4891436
773 1790269
774 11266101
775 7884575
776 7151872
777 9644761
778 3169579
779 5053867
780 23917124
781 4935541
782 8687161
783 10067247
784 16627072
785 4482097
786 6795103
787 1855747
788 5096828
789 3927661
790 7893949
791 4822063
792 25166592
793 5150089
794 3301459
795 9583771
796 5201108
797 1903237
798 17347057
799 5299879
800 20972800
801 6978609
802 3368407
803 5219539
804 11091212
805 11767693
806 9162853
807 4109263
808 7757056
809 1961017
810 22723659
811 1970731
812 13617956
813 4170709
814 9261049
815 4832359
816 21856384
817 5565313
818 3504319
819 17690211
820 13207964
821 2019661
822 7434301
823 2029519
824 8068864
825 17766425
826 9127363
827 2049307
828 19850292
829 2059237
830 8718913
831 4357783
832 17769472
833 9647953
834 7653751
835 5073187
836 14957228
837 11529621
838 3677989
839 2109247
840 37681408
841 4051097
842 3713227
843 4484779
844 5848964
845 9412117
846 13486473
847 9850247
848 11642752
849 4548961
850 16156175
851 6071443
852 12465596
853 2180269
854 9762109
855 18606159
856 8710912
857 2200777
858 20646787
859 2211067
860 14544596
861 11874373
862 3891937
863 2231719
864 30668544
865 5445409
866 3928183
867 8791091
868 15596108
869 6119197
870 19771381
871 6222223
872 9041152
873 8297289
874 10920091
875 14366875
876 13182884
877 2304757
878 4037929
879 4876711
880 28428928
881 2325841
882 24550911
883 2336419
884 16859612
885 11899453
886 4111933
887 2357647
888 19441408
889 6096889
890 10033219
891 17614827
892 6534836
893 6662149
894 8798881
895 5830807
896 23928832
897 13535809
898 4224199
899 6801667
900 36917100
901 6755773
902 11401957
903 13076047
904 9720064
905 5962201
906 9037483
907 2465227
908 6771908
909 8999397
910 25433401
911 2487031
912 27474304
913 6758689
914 4376239
915 12726979
916 6892028
917 6488557
918 23625189
919 2530927
920 23720704
921 5354713
922 4453267
923 6993259
924 35142932
925 11291525
926 4492033
927 9361143
928 18092288
929 2586337
930 22643383
931 12127843
932 7135436
933 5495389
934 4570069
935 16496047
936 35659008
937 2631097
938 11794363
939 5566411
940 17411108
941 2653621
942 9772441
943 7474999
944 14455936
945 32002857
946 12555823
947 2687587
948 15455132
949 7395661
950 20308925
951 5709823
952 26562304
953 2721769
954 17191251
955 6641131
956 7508468
957 15326293
958 4808209
959 7098919
960 43912192
961 5305681
962 13122151
963 10106019
964 7634924
965 6781309
966 25657429
967 2802367
968 19855616
969 15942121
970 11929099
971 2825611
972 28579716
973 7308469
974 4970329
975 25173575
976 15461248
977 2860657
978 10536127
979 7777507
980 31695356
981 10489149
982 5052397
983 2895919
984 23935744
985 7066057
986 13937203
987 15653131
988 21193172
989 8231461
990 41977089
991 2943271
992 20720384
993 6226129
994 13255879
995 7210627
996 17070284
997 2979037
998 5218549
999 16511607
1000 28960000