1 8
2 24
3 63
4 80
5 275
6 252
7 1247
8 240
9 513
10 825
11 1541
12 455
13 4187
14 3277
15 1891
16 1040
17 14111
18 819
19 43739
20 2200
21 2107
22 4623
23 6533
24 1365
25 15251
26 8321
27 8829
28 6235
29 13747
30 2387
31 116003
32 2720
33 13333
34 42333
35 14981
36 3276
37 33227
38 131217
39 12403
40 4400
41 61337
42 6321
43 74563
44 10235
45 49051
46 19599
47 186497
48 3640
49 67571
50 8525
51 31621
52 20935
53 79501
54 3591
55 40051
56 16385
57 82669
58 41241
59 586343
60 7161
61 358559
62 348009
63 48133
64 5440
65 68251
66 10787
67 540959
68 39593
69 38503
70 22649
71 727751
72 4095
73 128627
74 88357
75 90751
76 218695
77 285671
78 26533
79 451091
80 13200
81 39609
82 184011
83 83333
84 16211
85 1910291
86 178709
87 182527
88 30705
89 191351
90 13237
91 498317
92 52264
93 358453
94 559491
95 109061
96 7280
97 377719
98 88537
99 79003
100 11275
101 491063
102 94863
103 638189
104 41605
105 88831
106 238503
107 551051
108 9139
109 2617309
110 69575
111 305287
112 49155
113 359341
114 104653
115 318551
116 68735
117 1097227
118 837329
119 227767
120 19096
121 967637
122 716141
123 909709
124 580015
125 156875
126 18963
127 1164083
128 16320
129 1333603
130 76373
131 206981
132 32361
133 4674419
134 432821
135 146611
136 118779
137 902831
138 45731
139 1394171
140 51475
141 319507
142 485357
143 1720577
144 13104
145 2526191
146 256961
147 302869
148 166135
149 2489791
150 20801
151 1370477
152 656085
153 188191
154 308821
155 298871
156 54431
157 5921099
158 701521
159 11130319
160 32800
161 1246463
162 18981
163 4896847
164 340715
165 218791
166 249999
167 11720729
168 43645
169 2517763
170 1389581
171 741133
172 372815
173 360533
174 144137
175 736751
176 65504
177 753667
178 574053
179 514447
180 21483
181 1968557
182 1494951
183 269011
184 156792
185 3837271
186 416641
187 2101133
188 1331515
189 286903
190 327183
191 878219
192 21840
193 1492663
194 604117
195 2284621
196 140911
197 26556389
198 86963
199 2855651
200 33825
201 3235699
202 981317
203 2390963
204 183443
205 1010651
206 1914567
207 3089683
208 124815
209 1226413
210 94643
211 9801373
212 567635
213 1090987
214 1653153
215 556421
216 24605
217 11311343
218 7851927
219 385003
220 208725
221 587861
222 232589
223 20299691
224 55709
225 4054051
226 1078023
227 32165447
228 313959
229 13852211
230 238337
231 1069993
232 206205
233 653333
234 86821
235 2212291
236 2511987
237 3373933
238 683301
239 916327
240 43615
241 3488717
242 137149
243 355023
244 1792795
245 722261
246 429359
247 10257911
248 1740045
249 497503
250 167761
251 2273057
252 75852
253 535877
254 1551941
255 1563151
256 70720
257 15070481
258 1563401
259 8055419
260 173575
261 819541
262 620943
263 8307119
264 86296
265 8436011
266 3400013
267 2855299
268 1298463
269 8110351
270 106609
271 4410797
272 197965
273 597871
274 2708493
275 12712151
276 137193
277 1844267
278 929633
279 3117547
280 113245
281 1898999
282 958521
283 16349477
284 1293337
285 1302451
286 1047121
287 3957731
288 32760
289 22059371
290 941699
291 8135779
292 643135
293 1032533
294 61103
295 7665871
296 441785
297 4238191
298 2134277
299 1433407
300 47275
301 5567339
302 4111431
303 736291
304 1738885
305 4469471
306 221347
307 6792683
308 411539
309 765703
310 896613
311 11614607
312 108173
313 9411911
314 16572293
315 1590751
316 2104563
317 78399173
318 2382569
319 4074907
320 72160
321 2477479
322 1318021
323 2508419
324 44289
325 2538251
326 1703677
327 8560207
328 1022145
329 1735147
330 236003
331 10525139
332 666664
333 2736631
334 35162187
335 9433601
336 81055
337 18179803
338 548497
339 9199783
340 1538647
341 1863907
342 578683
343 3296573
344 893545
345 954271
346 1081599
347 5784491
348 267683
349 29244107
350 164791
351 27115453
352 163760
353 157044053
354 2008597
355 10742371
356 956755
357 3062347
358 1543341
359 7744349
360 61061
361 113907413
362 5905671
363 1056331
364 840739
365 62365361
366 807033
367 8087213
368 520760
369 2182267
370 3289301
371 2205967
372 1249923
373 3342827
374 3538573
375 1690501
376 3994545
377 39808939
378 103759
379 72412499
380 726755
381 6973063
382 2634657
383 109164959
384 99008
385 8899661
386 2387797
387 8394031
388 1812351
389 138028871
390 320819
391 9179117
392 422733
393 3093697
394 40995701
395 13114001
396 97083
397 15139199
398 1904033
399 14020063
400 90200
401 23165771
402 3786713
403 14302471
404 2455315
405 1314631
406 2049517
407 39771227
408 392231
409 6696967
410 749573
411 2030341
412 5105512
413 4099439
414 269521
415 144693071
416 332840
417 4177507
418 1840667
419 4922413
420 235081
421 28369507
422 29404119
423 4298527
424 1702905
425 21686051
426 2181121
427 7299139
428 2755255
429 2948947
430 820193
431 2976487
432 45695
433 25514959
434 11751757
435 10604431
436 14275735
437 68765447
438 900389
439 80965649
440 441529
441 2337301
442 1763583
443 2358533
444 431951
445 11888621
446 31045169
447 4799887
448 167127
449 22589191
450 285541
451 26861561
452 2874728
453 2466133
454 96496341
455 2487941
456 523265
457 288246353
458 25183589
459 3375487
460 541675
461 25514507
462 457907
463 180107927
464 439904
465 1788421
466 1959999
467 26182823
468 161239
469 8805007
470 2929333
471 124267699
472 4186645
473 8959567
474 3157637
475 5419751
476 949547
477 121070233
478 2748981
479 33051959
480 130845
481 38885003
482 10466151
483 1869211
484 411447
485 3768451
486 167751
487 9493579
488 3580705
489 86102143
490 434449
491 3862207
492 1288077
493 9728863
494 15012409
495 2944261
496 4640120
497 35080319
498 583331
499 21925063
500 138875
501 40173187
502 6819171
503 21262817
504 113477
505 40817131
506 1095053
507 18518683
508 4655823
509 4150387
510 1156793
511 34482281
512 211072
513 6321187
514 45211443
515 7434541
516 1250963
517 10698799
518 16600537
519 4314967
520 381865
521 538587919
522 586283
523 32834987
524 1379435
525 4415251
526 24921357
527 13338371
528 258888
529 154484399
530 1248797
531 3387781
532 8845783
533 88656023
534 1339457
535 11456491
536 2164105
537 59999011
538 6952037
539 48821543
540 119133
541 115923317
542 13232391
543 3542533
544 593895
545 3568661
546 1246613
547 47887663
548 4514155
549 75970621
550 1001275
551 3647621
552 365848
553 7344947
554 5532801
555 7398151
556 2788899
557 14899751
558 2509171
559 12507067
560 334109
561 7561159
562 5696997
563 88770463
564 1597535
565 19162541
566 49048431
567 38597959
568 2426785
569 240920291
570 763427
571 52181407
572 3141363
573 39418963
574 4147261
575 17208601
576 65520
577 7996067
578 3372529
579 40241659
580 2567975
581 5406787
582 4757081
583 8163167
584 1284805
585 2741311
586 3097599
587 86850173
588 183309
589 30544363
590 4181921
591 16773763
592 1325355
593 4224533
594 253327
595 8502551
596 6402831
597 8559787
598 1492109
599 40198891
600 104005
601 21681677
602 16702017
603 61101991
604 10961095
605 4832861
606 2208873
607 75187877
608 3499120
609 14843767
610 9082961
611 5979247
612 547651
613 82688797
614 9056501
615 4543621
616 1234617
617 115757839
618 2297109
619 33734263
620 2390968
621 18519463
622 23222993
623 74544443
624 272155
625 35159375
626 28235733
627 55053109
628 29605495
629 9504191
630 281263
631 47793203
632 3507605
633 134655559
634 235197519
635 96798131
636 4424771
637 9744827
638 1732889
639 3270403
640 216480
641 4935701
642 3857357
643 168716771
644 1756907
645 8328241
646 7525257
647 117232519
648 63973
649 50558399
650 750761
651 5090821
652 5111031
653 5122133
654 19986029
655 10303151
656 2725720
657 21012247
658 5205441
659 6955087
660 525481
661 57692081
662 31575417
663 12318541
664 1999992
665 111461981
666 2137009
667 90784037
668 85946555
669 17911807
670 5950549
671 54046367
672 243165
673 97871699
674 50893741
675 60161401
676 1090051
677 51347743
678 4310957
679 101450749
680 2051027
681 81642367
682 4885499
683 5603333
684 732571
685 11268251
686 4159261
687 18888379
688 2680635
689 73548047
690 1006787
691 57312923
692 2884264
693 97998517
694 17353473
695 173915411
696 720685
697 19442119
698 87732321
699 3913003
700 494373
701 283082027
702 1406437
703 65255273
704 327520
705 23867071
706 471132159
707 24002651
708 3768335
709 36208631
710 13337929
711 8095447
712 2870265
713 26455153
714 1058531
715 20459011
716 2572235
717 57593743
718 23233047
719 12417131
720 122915
721 31201997
722 18326641
723 6278533
724 15745195
725 8417251
726 306659
727 12691967
728 1679941
729 3190833
730 21178333
731 76966991
732 1345055
733 118227037
734 24261639
735 8650951
736 1041520
737 26082431
738 1165403
739 65559647
740 2427359
741 6594901
742 2305529
743 28727353
744 2083205
745 66619391
746 10028481
747 46887697
748 10615719
749 15720013
750 472781
751 236937497
752 10652120
753 54449431
754 16507433
755 20536001
756 246519
757 165063851
758 48278537
759 23053867
760 2180265
761 6955541
762 8148581
763 153718559
764 4391095
765 4686391
766 267623549
767 49431617
768 247520
769 141952787
770 3773863
771 21415297
772 7163391
773 71723579
774 9335221
775 57677051
776 3020585
777 14497267
778 159821429
779 14575091
780 796873
781 214735951
782 15112333
783 14725099
784 704555
785 14800391
786 1448867
787 104080751
788 74533769
789 17443213
790 8267677
791 10018807
792 388332
793 60386951
794 45417597
795 25292131
796 5712099
797 53373497
798 7648033
799 421386209
800 180400
801 77009743
802 15444917
803 18067501
804 3029747
805 15560651
806 10402237
807 36484471
808 4906585
809 10479787
810 680481
811 78944363
812 4169707
813 5292631
814 16705153
815 74411131
816 728429
817 40062413
818 8036033
819 53675623
820 1703575
821 97083251
822 6091023
823 162586943
824 15316536
825 16343251
826 12298317
827 172376573
828 411579
829 82487159
830 21347777
831 8293381
832 665680
833 8333333
834 9759197
835 92057081
836 5522001
837 58864537
838 14767239
839 321029927
840 705243
841 186750779
842 79422493
843 17064007
844 78410984
845 79989391
846 2236549
847 86117879
848 3086843
849 11541307
850 21013201
851 86926247
852 3397499
853 17471147
854 11677597
855 81893611
856 8265765
857 105782939
858 1560803
859 487046129
860 1864075
861 8902741
862 8929461
863 143028443
864 137085
865 65866291
866 9006401
867 54140683
868 35255271
869 344396867
870 3184289
871 100165001
872 36510641
873 15253057
874 70622059
875 85769251
876 1672151
877 221538971
878 242896947
879 6186403
880 923197
881 363282113
882 267589
883 31199923
884 3216623
885 43876531
886 7075599
887 122764349
888 1162945
889 57370853
890 5259199
891 9533701
892 93135507
893 22342861
894 14399661
895 32053531
896 278545
897 64384867
898 67767573
899 116404319
900 145607
901 48722477
902 5167663
903 6680437
904 8624184
905 9835541
906 7398399
907 167856677
908 69273137
909 33063967
910 3428093
911 43181401
912 1569795
913 230112521
914 864739059
915 6813151
916 69261055
917 100930523
918 600799
919 74345263
920 1191685
921 40728463
922 76543521
923 23868781
924 1373721
925 61625351
926 102921197
927 20633167
928 1099760
929 96681031
930 2092097
931 104031803
932 5226664
933 6969511
934 78548469
935 13996951
936 381017
937 52693133
938 21129389
939 17645689
940 6657575
941 42516263
942 21306157
943 53370029
944 12559935
945 128620171
946 3768113
947 43060091
948 5864183
949 36037327
950 1199671
951 144728887
952 2848641
953 21810359
954 13578407
955 36494371
956 4581635
957 76950457
958 22035917
959 220759883
960 317200
961 266006723
962 56351353
963 22266487
964 27909736
965 11182421
966 1954307
967 688285459
968 685745
969 52599259
970 4154909
971 113166167
972 132867
973 90907391
974 15188557
975 11415301
976 6095503
977 106928743
978 40238513
979 38351347
980 578579
981 116564491
982 11586621
983 270594343
984 3434872
985 116448671
986 11989921
987 58465933
988 45037227
989 58718909
990 687487
991 388943717
992 9280240
993 19732897
994 105240957
995 166350071
996 1749993
997 182947507
998 39862117
999 15978007
1000 349525