0 2
1 0
2 8
3 50
4 132
5 414
6 171
7 659
8 96
9 361
10 12311
11 7224
12 5896
13 2954
14 5804
15 72387
16 12756
17 1292
18 4332
19 3715
20 2704
21 1887
22 5780
23 9837
24 11721
25 1094
26 70067
27 32610
28 57658
29 26146
30 167389
31 94957
32 36588
33 19663
34 35588
35 9627
36 108296
37 51653
38 38147
39 54788
40 81871
41 15502
42 142576
43 60392
44 191260
45 140588
46 12006
47 57876
48 22309
49 161849
50 213717
51 69486
52 88482
53 102904
54 409811
55 9155
56 79042
57 210341
58 141585
59 441444
60 45047
61 122709
62 56600
63 132904
64 806
65 26006
66 614066
67 216441
68 33639
69 888513
70 151853
71 179878
72 85239
73 255590
74 48394
75 20611
76 187404
77 184695
78 91671
79 443105
80 257494
81 816242
82 163117
83 133392
84 138425
85 176049
86 253434
87 107777
88 583263
89 424124
90 49919
91 762047
92 73055
93 87519
94 848820
95 1321593
96 505166
97 64173
98 164101
99 701998
100 1072
101 911208
102 151416
103 662495
104 52709
105 1628914
106 1012296
107 1720570
108 53837
109 289371
110 711491
111 948075
112 2930
113 2606599
114 192719
115 1518504
116 19357
117 478828
118 149626
119 31512
120 283586
121 253212
122 729939
123 2702997
124 636827
125 1390221
126 568548
127 989824
128 1207752
129 439710
130 566067
131 130210
132 671081
133 727984
134 1719070
135 1978249
136 583184
137 400139
138 1296206
139 1436
140 972964
141 1138482
142 95876
143 2454766
144 577820
145 419309
146 3843188
147 2826401
148 5775642
149 1328767
150 619441
151 152815
152 10557064
153 1030310
154 22166
155 11852405
156 4796605
157 1475107
158 190116
159 468236
160 8487485
161 411590
162 2489884
163 2936135
164 2371768
165 5978290
166 464414
167 1860470
168 11042351
169 25073
170 916481
171 845594
172 473139
173 1156887
174 699027
175 560671
176 1179803
177 996960
178 2015073
179 2919369
180 2664246
181 444518
182 9577643
183 80326
184 1193876
185 2033039
186 1586576
187 1010789
188 222278
189 2513519
190 1136011
191 1782901
192 272879
193 29348
194 2745063
195 19077
196 1689457
197 4341791
198 11596401
199 547757
200 1699675
201 2247580
202 3961787
203 8224695
204 457400
205 4279727
206 5492775
207 1205677
208 286337
209 752150
210 3006874
211 2728597
212 4640544
213 4791677
214 579723
215 3942661
216 2431533
217 3388786
218 1944606
219 2692552
220 4233768
221 14013382
222 2209253
223 1192857
224 963989
225 290644
226 16846441
227 799145
228 430794
229 10404301
230 5410219
231 3586443
232 1154049
233 1828350
234 6608859
235 10823714
236 396641
237 2395969
238 5019699
239 10285274
240 9429037
241 11263506
242 690829
243 842366
244 6681502
245 866516
246 3119679
247 490657
248 2726786
249 3586425
250 2165864
251 6023651
252 12238296
253 2039554
254 2285407
255 1115468
256 39739
257 890104
258 8297166
259 9962836
260 12812739
261 2532183
262 91119
263 1638264
264 576754
265 1802417
266 84269
267 10149164
268 4276679
269 5369304
270 5212723
271 2577680
272 2121779
273 372875
274 5503970
275 767052
276 8839144
277 26895063
278 3683556
279 4366983
280 15167473
281 12207270
282 10803120
283 8239584
284 4766284
285 11125001
286 506845
287 15797375
288 13230442
289 19304420
290 9156713
291 6060502
292 4124472
293 19375220
294 2012458
295 754846
296 17331
297 2210840
298 4717150
299 984593
300 3260474
301 15587819
302 169924
303 5423604
304 6672253
305 5418268
306 8566501
307 1630727
308 4872804
309 335631
310 3242229
311 4478147
312 14357452
313 34054678
314 2728779
315 13528975
316 14150256
317 3656434
318 3315691
319 12450914
320 25995140
321 1173253
322 2409299
323 2307933
324 16534269
325 2400044
326 771932
327 352713
328 510653
329 36180782
330 151012
331 8195980
332 4733507
333 4923921
334 1587364
335 163594
336 728119
337 40003953
338 3695620
339 15130002
340 647312
341 217687
342 21593071
343 10981113
344 1192704
345 9774357
346 5755690
347 874225
348 14709738
349 18271704
350 7450925
351 4453563
352 1302695
353 27788558
354 24928235
355 9370111
356 9804474
357 24862052
358 4533823
359 117236
360 16139942
361 2083046
362 2089559
363 15122727
364 215585
365 22536985
366 318846
367 25288987
368 26732174
369 11120438
370 28552850
371 5600444
372 19293212
373 8890545
374 2831133
375 86834546
376 7942283
377 6803945
378 1479714
379 42415990
380 8102074
381 6194095
382 4513157
383 17425235
384 12401134
385 5961589
386 20702085
387 24979967
388 338332
389 5762837
390 2708123
391 49840082
392 1542034
393 8285079
394 5183643
395 30140127
396 6772774
397 9688200
398 4182248
399 1776226
400 23544761
401 13274309
402 15294859
403 3133936
404 899303
405 1139153
406 8711167
407 6336081
408 1990894
409 27877836
410 1719264
411 9388896
412 3420275
413 5464495
414 134687
415 1601559
416 34389604
417 65736995
418 453943
419 29317501
420 22735
421 36997345
422 14082930
423 3953687
424 779607
425 2650198
426 17160308
427 12156039
428 2101432
429 35002630
430 11923012
431 7222314
432 10211477
433 7435148
434 22337764
435 18083605
436 21374395
437 57813671
438 16848764
439 82888054
440 359152
441 11273660
442 13511905
443 9700554
444 17207749
445 1512393
446 21232098
447 18614292
448 6250797
449 2702550
450 9275592
451 7362739
452 6001467
453 13983582
454 17516999
455 3857676
456 10265532
457 3290041
458 9951102
459 3844096
460 7961143
461 36636719
462 15280821
463 36015485
464 47669785
465 93276101
466 882127
467 3802957
468 6323100
469 9992488
470 23695596
471 24013939
472 50681673
473 7149567
474 5777803
475 9208736
476 3256658
477 18898467
478 32435710
479 2550406
480 85285264
481 4650303
482 28688680
483 565139
484 48785826
485 9013449
486 8341336
487 15761377
488 1768542
489 40077287
490 37491772
491 50004028
492 9209687
493 43779496
494 34287751
495 8410905
496 2032392
497 12802509
498 922712
499 4075001
500 14655991
501 5487045
502 676270
503 218333
504 30774002
505 43312556
506 7541971
507 17532410
508 4505459
509 36792144
510 4557801
511 4819095
512 35800545
513 12236860
514 1168932
515 2575029
516 8358862
517 3150594
518 14289
519 44817891
520 24713822
521 22602599
522 48409943
523 2083119
524 37181476
525 31377691
526 1359709
527 434627
528 25993150
529 15423383
530 18612939
531 3324837
532 76519048
533 50567460
534 99234391
535 14766681
536 8226713
537 32180761
538 7045970
539 24358832
540 15587984
541 8775608
542 12531245
543 9726241
544 12280025
545 1984878
546 25233812
547 3242721
548 15536388
549 56775235
550 75605324
551 7021652
552 30166038
553 4124688
554 56205248
555 6869272
556 19144627
557 24287092
558 39737999
559 34490264
560 184613999
561 10646518
562 14231735
563 2765744
564 2514380
565 27193367
566 21948945
567 39321340
568 16209308
569 37626128
570 2766441
571 9974783
572 42229245
573 20585979
574 34391590
575 66149005
576 26141054
577 18075362
578 2878520
579 11020702
580 62938944
581 27451791
582 15002975
583 7064523
584 1885752
585 6178657
586 81925441
587 42665545
588 6842948
589 14466422
590 79427963
591 7472965
592 2178097
593 6560334
594 42811800
595 7725035
596 30012754
597 147307318
598 688423
599 79619324
600 22674483
601 19325164
602 4831871
603 5555330
604 43284630
605 39570781
606 26756176
607 3770593
608 29135122
609 61179322
610 277912
611 11908411
612 16207114
613 13227171
614 851557
615 36595421
616 46011445
617 9647677
618 10500904
619 39300562
620 58183795
621 104256
622 202463929
623 58011699
624 8564212
625 15381217
626 12421683
627 20652667
628 59705636
629 70165693
630 38323122
631 12249210
632 34423495
633 92875897
634 92715409
635 65826543
636 19335979
637 95748924
638 18003760
639 2478510
640 4977993
641 11899333
642 15649723
643 8461795
644 57312692
645 178957679
646 6032378
647 6656643
648 6703632
649 8556135
650 9697354
651 42779721
652 129474880
653 89572718
654 9328955
655 37910886
656 14971918
657 54412666
658 42829405
659 12034318
660 8668248
661 67683758
662 36475611
663 11483450
664 15335418
665 47038781
666 17108516
667 42243767
668 32021523
669 119254534
670 55652052
671 9317339
672 510865
673 8378945
674 41559383
675 21432525
676 16381569
677 13784168
678 47662187
679 95299190
680 2947953
681 140545770
682 31026924
683 17931782
684 12925515
685 52179122
686 70937652
687 22885290
688 20081340
689 4866485
690 50837490
691 18199391
692 43986601
693 16452974
694 212906216
695 22040684
696 5256661
697 16033965
698 1566311
699 11727329
700 14542433
701 86328865
702 107948143
703 130543312
704 63359830
705 48739802
706 16669072
707 35599933
708 49285331
709 49051862
710 33039651
711 95543073
712 93279672
713 96103820
714 67281987
715 74157075
716 5090076
717 3332088
718 40248300
719 43301379
720 24917249
721 104088701
722 74422569
723 21591386
724 115238373
725 17130474
726 8806328
727 30897163
728 14929800
729 246370
730 106272848
731 11390593
732 62986269
733 8839366
734 1546485
735 31314374
736 44349161
737 138761910
738 24333454
739 8362642
740 4747443
741 89419214
742 29803017
743 86301331
744 60006980
745 11390576
746 11515377
747 22946240
748 122431036
749 8872545
750 55419809
751 58225430
752 29129385
753 23121799
754 61432939
755 811720
756 8081827
757 99010890
758 2159020
759 14836396
760 12948794
761 112279671
762 36718870
763 34581642
764 2611246
765 292448598
766 98589185
767 42756445
768 23701885
769 117152019
770 56362036
771 12085278
772 121885369
773 40861763
774 51087691
775 60307140
776 35812137
777 14012731
778 27820441
779 57268861
780 31360750
781 40206391
782 92816591
783 9547975
784 79850824
785 82634296
786 47374537
787 41509348
788 87967695
789 12339223
790 59648319
791 69490330
792 7423134
793 44572736
794 10433533
795 104125915
796 80697639
797 30245392
798 21766703
799 47793895
800 86770653
801 72035839
802 9771847
803 40611477
804 30862010
805 102316871
806 6076485
807 30397186
808 7110131
809 59723537
810 44579587
811 40566022
812 4239992
813 65863467
814 34371303
815 4694724
816 23701667
817 18416119
818 112397240
819 113093258
820 1622680
821 68160188
822 57239837
823 13968444
824 95126383
825 118454704
826 84166095
827 13646160
828 42968092
829 45681288
830 92137668
831 11788291
832 144354719
833 50108924
834 70622668
835 136807921
836 1810797
837 60380090
838 98454561
839 60107600
840 262922968
841 16045517
842 61783383
843 7505401
844 66931281
845 20882150
846 22350549
847 15265358
848 12960056
849 256272926
850 8765113
851 15083463
852 5297146
853 79270180
854 81715431
855 7532225
856 13476522
857 12701843
858 23972617
859 51311626
860 51612166
861 22896014
862 174567236
863 28300435
864 70130733
865 6050666
866 40986722
867 6346302
868 126382701
869 144263377
870 25074903
871 175884361
872 35533078
873 19379256
874 28380559
875 204110397
876 6600499
877 14294906
878 62701323
879 39268853
880 19919590
881 91966832
882 31287168
883 218989229
884 117993501
885 64270427
886 30452439
887 22054157
888 28180791
889 15320773
890 18459657
891 8885255
892 30665692
893 59097026
894 250454931
895 290156937
896 22420673
897 170600867
898 130951609
899 57628489
900 82825923
901 45009960
902 35732506
903 18266300
904 451993799
905 122200421
906 53235258
907 54248587
908 270097554
909 32531879
910 51549872
911 17060111
912 81921909
913 139491445
914 142657632
915 9409608
916 72753590
917 5053286
918 15408071
919 37950403
920 361411145
921 23277884
922 42982263
923 220098998
924 174266868
925 109626148
926 39861710
927 3481601
928 15779307
929 64338426
930 37470470
931 13457077
932 140264095
933 166578030
934 243589682
935 49869539
936 32587858
937 33942496
938 101772587
939 153507639
940 148572707
941 98116524
942 45575225
943 63598011
944 43874122
945 20613064
946 49706958
947 55015262
948 114137709
949 87350268
950 78680157
951 30644084
952 26852545
953 36611470
954 34149335
955 100499832
956 8431823
957 126725887
958 33169233
959 24431874
960 159557784
961 16302026
962 57766922
963 172005940
964 4697500
965 44022653
966 80731599
967 80678785
968 25088355
969 101674016
970 158493694
971 34316964
972 230293337
973 4927658
974 89331253
975 3727520
976 288759050
977 95532618
978 164020080
979 40798715
980 123155
981 97403069
982 23025697
983 30428311
984 36476101
985 100342510
986 14392431
987 83783287
988 209599923
989 600637582
990 19292364
991 39209760
992 662150301
993 196954889
994 372636529
995 91736138
996 8193274
997 171208148
998 103671138
999 137310491