2 4
3 9
4 90
5 25
6 300
7 49
8 735
9 1770
10 7644
11 121
12 2541
13 169
14 5187
15 6710
16 8463
17 289
18 10982
19 361
20 11913
21 13202
22 24339
23 529
24 18515
25 19513
26 37851
27 20723
28 43239
29 841
30 35322
31 961
32 43215
33 20705
34 146595
35 270470
36 110823
37 1369
38 62835
39 46535
40 632316
41 1681
42 106074
43 1849
44 94695
45 86549
46 189846
47 2209
48 143585
49 216858
50 157899
51 53934
52 263703
53 2809
54 219102
55 111943
56 177855
57 57065
58 463539
59 3481
60 268037
61 3721
62 428259
63 293567
64 384879
65 618977
66 582156
67 4489
68 588471
69 186989
70 337395
71 5041
72 458731
73 5329
74 789051
75 218867
76 574167
77 363653
78 975204
79 6241
80 374415
81 300228
82 447858
83 6889
84 888681
85 638740
86 499155
87 640823
88 801471
89 7921
90 757659
91 1147468
92 1770999
93 435714
94 668451
95 353814
96 1065030
97 9409
98 565035
99 213035
100 1679799
101 10201
102 2009139
103 10609
104 803103
105 257514
106 958266
107 11449
108 1522717
109 11881
110 2162342
111 634908
112 3440559
113 12769
114 1412310
115 379614
116 1030071
117 1318253
118 756435
119 897959
120 7766335
121 376201
122 2969691
123 437315
124 2965287
125 1295429
126 3087843
127 16129
128 1364559
129 1390289
130 3125739
131 17161
132 2564646
133 1851517
134 1256382
135 746630
136 1668639
137 18769
138 2705436
139 19321
140 4115373
141 393845
142 3935950
143 549647
144 7092159
145 709914
146 2200626
147 1020876
148 2614359
149 22201
150 1930515
151 22801
152 3855039
153 1138596
154 1345395
155 697571
156 9510599
157 24649
158 1400235
159 487535
160 1986159
161 776058
162 3710315
163 26569
164 5447319
165 2138333
166 7439346
167 27889
168 3329007
169 666282
170 2777019
171 1330430
172 5584359
173 29929
174 5794563
175 1638559
176 3034479
177 2265233
178 13061451
179 32041
180 4578455
181 32761
182 4553211
183 2197607
184 3882207
185 3677514
186 3909270
187 3636163
188 9778263
189 2120258
190 3275139
191 36481
192 8062301
193 37249
194 10129899
195 2562830
196 6424743
197 38809
198 6663348
199 39601
200 11677359
201 1902948
202 8278779
203 3650387
204 4034919
205 695109
206 3928323
207 4035263
208 18902271
209 3943649
210 6147756
211 44521
212 5931015
213 8372957
214 6971166
215 2130887
216 12265055
217 9881353
218 5286939
219 4336835
220 2754615
221 5513381
222 7927115
223 49729
224 4630479
225 8510657
226 8502123
227 51529
228 6149670
229 52441
230 22680100
231 5031494
232 9640479
233 54289
234 7955676
235 1290414
236 16893543
237 2155490
238 7116483
239 57121
240 4783359
241 58081
242 11686539
243 12236027
244 7215879
245 3447917
246 6513843
247 844023
248 11547039
249 1471434
250 6987099
251 63001
252 18963301
253 10802917
254 7923363
255 3046614
256 45205510
257 66049
258 10264932
259 3292939
260 8433159
261 4198541
262 5518998
263 69169
264 10152879
265 10473337
266 27322491
267 1819715
268 5798919
269 72361
270 29089122
271 73441
272 12408591
273 3397210
274 53697468
275 1812894
276 13153110
277 76729
278 8850294
279 1859478
280 13249119
281 78961
282 13093452
283 80089
284 14871207
285 8183474
286 7369686
287 4964063
288 33326735
289 4663009
290 34215700
291 11354171
292 28356519
293 85849
294 8224542
295 7022140
296 27860127
297 5862372
298 6430035
299 8958419
300 25858679
301 26940421
302 27350979
303 1908815
304 20023887
305 6435281
306 13707756
307 94249
308 11799735
309 4600308
310 18505299
311 96721
312 27501551
313 97969
314 29086707
315 36920003
316 25414140
317 100489
318 14817636
319 1980399
320 19754799
321 3270714
322 23451339
323 2959115
324 19645863
325 8396461
326 7609806
327 6755783
328 13330911
329 7228169
330 15643116
331 109561
332 26040615
333 21562997
334 8131086
335 9319439
336 31911855
337 113569
338 8457714
339 3041195
340 53898519
341 5050194
342 17305715
343 1457607
344 10592799
345 9255497
346 20675739
347 120409
348 38845239
349 121801
350 9897699
351 7388822
352 31437039
353 124609
354 19864779
355 39663244
356 7862055
357 11097293
358 44382963
359 128881
360 51939043
361 8315562
362 10720059
363 29775756
364 15092679
365 9094709
366 19169316
367 134689
368 13158159
369 8944529
370 16627395
371 3862878
372 18727415
373 139129
374 9969822
375 4029414
376 18521679
377 4307513
378 14419635
379 143641
380 19069239
381 19879874
382 15424758
383 146689
384 17191110
385 9771969
386 23875683
387 10553243
388 9314535
389 151321
390 22384116
391 3610758
392 8974815
393 15901817
394 9114195
395 17313260
396 50954519
397 157609
398 45706659
399 23213174
400 23703519
401 160801
402 23567724
403 32208427
404 24249927
405 5954514
406 11260155
407 5212055
408 33572735
409 167281
410 16079259
411 19610970
412 78211430
413 8774597
414 12964662
415 5547414
416 29554863
417 7892753
418 67447011
419 175561
420 61735895
421 177241
422 51303219
423 11030726
424 37862319
425 19122281
426 36667419
427 76281996
428 23039511
429 23633670
430 88534900
431 185761
432 35919366
433 187489
434 59939331
435 30771374
436 57553510
437 22783348
438 22857270
439 192721
440 75201279
441 21996761
442 67950939
443 196249
444 64747878
445 34258069
446 16793763
447 36973103
448 53012271
449 201601
450 29877516
451 7581531
452 21443079
453 13881266
454 14733666
455 5073414
456 24193110
457 208849
458 33208851
459 18567038
460 73436439
461 212521
462 30647670
463 214369
464 18135327
465 13525130
466 27957963
467 218089
468 115264919
469 20347309
470 87091300
471 5477478
472 109053759
473 40573817
474 18417819
475 19160620
476 39081783
477 13597490
478 132277180
479 229441
480 48345935
481 12146682
482 48345099
483 26227214
484 29629479
485 23250557
486 35662482
487 237169
488 34136223
489 12086628
490 20826939
491 241081
492 32696615
493 28781157
494 52164291
495 35975327
496 94138959
497 17883473
498 36649836
499 249001
500 22536759
501 28882322
502 35233779
503 253009
504 96417663
505 18317881
506 36436827
507 10135390
508 41415735
509 259081
510 44402070
511 32005551
512 165734463
513 38589377
514 52673259
515 13556699
516 89661207
517 59903668
518 41239731
519 29240198
520 223580559
521 271441
522 40295196
523 273529
524 41257047
525 13452197
526 54521650
527 7691663
528 55635270
529 67597489
530 112393700
531 29979851
532 82827430
533 11293037
534 42182676
535 3506439
536 37430655
537 13234490
538 118865050
539 21238979
540 59786070
541 292681
542 67371459
543 27229334
544 59398527
545 10330481
546 24517227
547 299209
548 49147959
549 37929458
550 26358195
551 40668311
552 109494815
553 56198377
554 25157307
555 13698707
556 76571607
557 310249
558 61508931
559 51213439
560 44509839
561 61534481
562 26083659
563 316969
564 109827991
565 50633620
566 170068539
567 46305446
568 84037791
569 323761
570 47127996
571 326041
572 171633110
573 18327554
574 24509286
575 38091839
576 64827903
577 332929
578 56898219
579 33952334
580 213192039
581 25218546
582 171187891
583 4094247
584 157538559
585 14987930
586 48180186
587 344569
588 115594135
589 9730722
590 136947700
591 53017334
592 74989839
593 351649
594 144769065
595 80002891
596 54358359
597 64885714
598 39631035
599 358801
600 92364294
601 361201
602 62948379
603 53284766
604 216250342
605 20172677
606 59236203
607 368449
608 47167791
609 39354449
610 151414300
611 17871054
612 176357559
613 375769
614 100741587
615 16405367
616 50167551
617 380689
618 66579372
619 383161
620 142428039
621 18310164
622 307548156
623 53183567
624 54282095
625 79220737
626 109337270
627 81339054
628 148546119
629 9119885
630 65258259
631 398161
632 41146959
633 36081034
634 326262459
635 64502339
636 119459879
637 156473173
638 163784067
639 33931478
640 186961404
641 410881
642 29843115
643 413449
644 34591431
645 27324797
646 196765910
647 418609
648 212872079
649 26820138
650 110866299
651 65268690
652 86721879
653 426409
654 71944278
655 11228214
656 101245020
657 121942874
658 151562379
659 434281
660 121292070
661 436921
662 67578771
663 22614647
664 36341823
665 13262154
666 65796156
667 128092483
668 26314935
669 37708674
670 80528259
671 191955830
672 165010415
673 452929
674 63167979
675 45818510
676 58508967
677 458329
678 123483035
679 101486044
680 275856879
681 18970026
682 32534715
683 466489
684 74569287
685 11526114
686 39665283
687 11488415
688 39156159
689 113259089
690 64976555
691 477481
692 75462231
693 89008116
694 36747306
695 25332359
696 488879951
697 187560073
698 36826035
699 48754958
700 47354295
701 491401
702 68614254
703 25055407
704 128697279
705 45181930
706 43411179
707 69408443
708 73619735
709 502681
710 303303434
711 44897478
712 99188319
713 143889257
714 274767227
715 182360892
716 43145319
717 40927586
718 178905891
719 516961
720 182847119
721 148538881
722 94009539
723 48669755
724 173589447
725 22770077
726 70352403
727 528529
728 136122783
729 74279738
730 126314139
731 28573571
732 226264119
733 537289
734 35001195
735 54003839
736 497186463
737 18432113
738 97820532
739 546121
740 191163639
741 26116404
742 107873139
743 552049
744 132622527
745 10967529
746 55472922
747 61668563
748 276729591
749 149011589
750 134824356
751 564001
752 57187599
753 11859665
754 145351740
755 128393963
756 182345943
757 573049
758 166035219
759 29772070
760 283561599
761 579121
762 88105932
763 98810947
764 59632503
765 81813314
766 152050620
767 43775663
768 78980847
769 591361
770 51616299
771 32420364
772 379418439
773 597529
774 180634902
775 21783414
776 85853823
777 51855914
778 281000019
779 21580782
780 438856422
781 215105941
782 44321814
783 173303087
784 148782351
785 44121137
786 97984476
787 619369
788 411706263
789 51292178
790 154792659
791 69083644
792 51730959
793 210538660
794 301880499
795 180892643
796 100700391
797 635209
798 438218385
799 9573519
800 131511039
801 40061882
802 324983019
803 17959115
804 495684791
805 173548477
806 53660019
807 25784390
808 264856719
809 654481
810 58971795
811 657721
812 370487559
813 45837797
814 95133726
815 84844079
816 155431110
817 78171553
818 40071435
819 84034284
820 175782999
821 674041
822 135736596
823 677329
824 52804095
825 85711434
826 188095323
827 683929
828 243334407
829 687241
830 201300470
831 75852374
832 183679311
833 117031937
834 92949270
835 9287643
836 57833223
837 362261453
838 42754035
839 703921
840 52192095
841 183411172
842 75655419
843 130783934
844 410308167
845 30043554
846 153303755
847 17655663
848 518555679
849 43763268
850 115896459
851 77608331
852 212602119
853 727609
854 47892795
855 468353894
856 357166623
857 734449
858 109474236
859 737881
860 353706519
861 64049282
862 112221219
863 744769
864 294106902
865 49478689
866 73235883
867 117821003
868 51574935
869 22995485
870 86192115
871 106993351
872 185022591
873 77669354
874 54794106
875 61696211
876 156609510
877 769129
878 679552707
879 69884879
880 680499759
881 776161
882 244714788
883 779689
884 65745687
885 303433997
886 239774710
887 786769
888 280297535
889 35542218
890 235286619
891 136297571
892 106319415
893 97378037
894 152709123
895 62621103
896 108920031
897 40771716
898 77017899
899 52172219
900 400524519
901 51153661
902 138096918
903 152688407
904 223575420
905 71643140
906 296893051
907 822649
908 556229660
909 59406485
910 405458499
911 829921
912 335268479
913 136214497
914 237899787
915 127607070
916 210128007
917 374178756
918 125391636
919 844561
920 322275039
921 37148441
922 684478844
923 49489187
924 117277895
925 11138709
926 57917355
927 76797023
928 71523039
929 863041
930 55348395
931 21596286
932 720011030
933 220172765
934 181905627
935 52944359
936 487774662
937 877969
938 118131387
939 22290035
940 484872220
941 885481
942 468798006
943 442346812
944 149191887
945 53845274
946 398546390
947 896809
948 426463751
949 41799709
950 102531219
951 47865191
952 332567679
953 908209
954 120078870
955 29579619
956 103106199
957 48129492
958 182925550
959 112678079
960 131791359
961 209086401
962 88166379
963 103204427
964 213632679
965 66942557
966 142058163
967 935089
968 89929119
969 94855289
970 184868859
971 942841
972 572544119
973 152801317
974 87658179
975 170438927
976 466658319
977 954529
978 143350251
979 26362398
980 82581639
981 26542445
982 68990058
983 966289
984 137920470
985 348496804
986 330701403
987 64065806
988 126194871
989 52010309
990 141662916
991 982081
992 326644719
993 132600497
994 208693026
995 67313771
996 132875430
997 994009
998 294202131
999 64071366
1000 255593919