0 1
1 3
2 91
3 325
4 2093
5 1001
6 12025
7 1045
8 4945
9 6391
10 189
11 455
12 245
13 11825
14 128843
15 368809
16 273
17 1295
18 14495
19 37961
20 252263
21 91375
22 595
23 13013
24 46189
25 104951
26 63875
27 136345
28 42237
29 22253
30 192647
31 18655
32 8225
33 194545
34 200629
35 192907
36 27625
37 1911
38 464783
39 27797
40 13377
41 28985
42 79475
43 1495
44 3715673
45 250393
46 1925
47 14875
48 7475
49 514197
50 140833
51 676775
52 3591
53 61295
54 1181999
55 162279
56 107525
57 60095
58 2331
59 60697
60 457919
61 60249
62 453475
63 16445
64 40579
65 4209149
66 24955
67 98945
68 26125
69 2473211
70 143429
71 47905
72 307307
73 119133
74 624701
75 61523
76 705627
77 31664795
78 1929125
79 56721
80 83657
81 248105
82 29029
83 306475
84 14755039
85 86583
86 245905
87 238595
88 91195
89 24871
90 6178667
91 757405
92 34595
93 151525
94 2038071
95 4652557
96 12155
97 3028467
98 4492475
99 1331729
100 84847
101 111155
102 11725
103 294861
104 27357097
105 1791647
106 40205
107 1137895
108 241927
109 2070107
110 2389877
111 702185
112 257125
113 805475
114 893809
115 87381
116 1515125
117 6545
118 180895
119 15594953
120 7920283
121 150059
122 331925
123 296725
124 841841
125 18260957
126 1165835
127 409059
128 581581
129 2305897
130 1824361
131 209405
132 2021725
133 1414127
134 4569617
135 1239953
136 219505
137 247225
138 1133407
139 3101527
140 3149003
141 247775
142 593929
143 585599
144 5045579
145 644007
146 346775
147 3797035
148 370975
149 2533289
150 424879
151 23485
152 1721027
153 5039515
154 2325999
155 6269753
156 1293655
157 37107
158 2962795
159 5808439
160 4046601
161 239525
162 380545
163 1676125
164 6311879
165 2055781
166 28105
167 2251975
168 630025
169 2137233
170 14402531
171 1324505
172 244475
173 73645
174 12195359
175 6869811
176 226525
177 593725
178 154413
179 4614973
180 4821421
181 2437655
182 10824053
183 322465
184 4152897
185 10080371
186 2488577
187 5681091
188 1328195
189 1577719
190 7774151
191 33605
192 4561843
193 455975
194 11736851
195 18387557
196 4575805
197 8754421
198 12896387
199 383439
200 3298867
201 216755
202 2110295
203 13324795
204 6951967
205 1765233
206 1227655
207 1976095
208 56109809
209 66063751
210 18522283
211 60775
212 377377
213 82225
214 14210157
215 2788357
216 4436861
217 27353027
218 5342095
219 12461561
220 634809
221 39655
222 1056125
223 23319595
224 10652863
225 2623313
226 4767191
227 1862945
228 953095
229 1870113
230 95785859
231 2981375
232 754509
233 2325125
234 13449227
235 5647213
236 847385
237 3990701
238 486475
239 2611037
240 7897901
241 4975131
242 3715621
243 11707345
244 17156183
245 10693969
246 1768085
247 7865645
248 8959811
249 3473561
250 987753
251 1214525
252 77542933
253 1767171
254 11532521
255 3048227
256 1295525
257 2817529
258 574145
259 39477383
260 17742067
261 526955
262 1941933
263 3196921
264 6482287
265 16492619
266 146575
267 3294277
268 3031171
269 4003363
270 7771907
271 2506917
272 16708505
273 14597605
274 2609859
275 2198287
276 3987775
277 3903625
278 1755325
279 28114889
280 14088477
281 5318467
282 287287
283 20292321
284 46073489
285 16717477
286 59514327
287 1425875
288 33062755
289 19337773
290 4077647
291 2089555
292 2369851
293 153725
294 27432067
295 6468987
296 8127275
297 14482895
298 13667555
299 10491173
300 18741701
301 12871375
302 6212525
303 16640569
304 2956811
305 9607787
306 20629763
307 24101291
308 9210695
309 5113889
310 343343
311 12681949
312 39328225
313 2139995
314 37037407
315 2442583
316 2823951
317 16021327
318 28569749
319 41649957
320 5152819
321 4016155
322 185101713
323 888745
324 140765681
325 30764307
326 1369775
327 2316475
328 15819609
329 10465897
330 62920111
331 1676883
332 30997681
333 21337589
334 9899019
335 18293717
336 2963389
337 18359719
338 8570045
339 23115001
340 5523427
341 4503317
342 12842225
343 1011725
344 6707323
345 5880589
346 1667421
347 13860253
348 6474845
349 6386237
350 244050631
351 15489005
352 6130467
353 5179951
354 31184681
355 12981353
356 3242525
357 42434249
358 22453277
359 3959657
360 14704261
361 2211275
362 24121895
363 182670275
364 8521063
365 10743949
366 17437903
367 6765843
368 1994069
369 9900919
370 3468621
371 2564705
372 8622383
373 4381533
374 54662881
375 2588047
376 11737649
377 650011745
378 1753895
379 13881707
380 11260613
381 3313453
382 4185995
383 2503193
384 27123109
385 61772553
386 3985267
387 533533
388 2750041
389 246529019
390 67903297
391 10870119
392 19986475
393 1352065
394 1035741
395 32718931
396 58032169
397 4008641
398 2230195
399 118645813
400 16739437
401 7004855
402 59629829
403 63317177
404 721259
405 130531049
406 16554005
407 28200731
408 10391975
409 902937
410 15580279
411 6132269
412 17612309
413 12911041
414 16934567
415 40918507
416 26227705
417 59834047
418 55439995
419 2608463
420 67685449
421 7890025
422 13246145
423 2304445
424 55454971
425 2409407
426 5309525
427 9502337
428 775129909
429 117233921
430 11740157
431 7939255
432 56643587
433 6923345
434 13889447
435 77165023
436 376805
437 15049811
438 20511469
439 26329459
440 113253881
441 15818825
442 42833847
443 1167595
444 4841753
445 849927
446 37394525
447 12895129
448 1003145
449 4084157
450 78824291
451 12063177
452 164395
453 27957215
454 271997977
455 384126611
456 2671955
457 11886791
458 1333475
459 26695361
460 6952099
461 6369883
462 19682039
463 16110423
464 2011009
465 29889451
466 369655
467 9870245
468 15352513
469 13144599
470 39051023
471 6152419
472 5876339
473 153301975
474 19513637
475 231547459
476 54312775
477 29804995
478 8479471
479 18387421
480 191400319
481 25397405
482 36191725
483 371924449
484 71968143
485 1812239
486 382525
487 75909295
488 8351369
489 5931211
490 21708401
491 3834061
492 81692039
493 11960575
494 997994081
495 41817841
496 808775
497 36736975
498 14917045
499 26565253
500 52787567
501 5037851
502 2695231
503 13540483
504 125764249
505 22595769
506 107301943
507 2680645
508 4882031
509 166767139
510 77496497
511 22258457
512 7601737
513 8851895
514 12505059
515 124551973
516 20645755
517 440887077
518 10006711
519 163406023
520 370135271
521 3394105
522 37113973
523 6988751
524 40211743
525 59172971
526 123991205
527 904087093
528 65648401
529 29432767
530 10528661
531 11523655
532 3681095
533 32201281
534 34813961
535 2426053
536 5333419
537 6439345
538 19637787
539 193608727
540 25401803
541 4035031
542 57620129
543 5798507
544 22934197
545 84927359
546 24901525
547 6610637
548 7820153
549 18661097
550 102442899
551 8101775
552 6474875
553 6487195
554 33940517
555 52505537
556 3746171
557 16163719
558 20322533
559 77422301
560 276027193
561 107717441
562 4722991
563 7958093
564 157487371
565 23190431
566 18141227
567 76471637
568 2032639
569 74391031
570 106203539
571 39473405
572 78099581
573 44989633
574 125366449
575 102337807
576 2404259
577 10242729
578 91787917
579 9022937
580 46903571
581 14046643
582 85993225
583 54368873
584 11266297
585 24087371
586 12982255
587 203677595
588 22873721
589 34449701
590 9113819
591 4230655
592 36797945
593 98251517
594 657868103
595 186905907
596 2049905
597 145725725
598 65769583
599 88602371
600 53134279
601 60763729
602 26326795
603 15074983
604 35569729
605 68874259
606 4268275
607 5254249
608 131958475
609 3686969
610 116787699
611 117489911
612 82056689
613 36452507
614 2315621
615 84129929
616 34558025
617 30372013
618 6775639
619 57801933
620 254672561
621 2763605
622 49198391
623 19803575
624 75200741
625 21259537
626 95274205
627 328211299
628 40141829
629 290710849
630 27814567
631 7090655
632 43066933
633 46005895
634 26164853
635 58846021
636 5014405
637 451934375
638 27919151
639 174555337
640 14364779
641 6804655
642 6513941
643 1174745
644 35179001
645 906513377
646 16006705
647 27806405
648 231463453
649 459053487
650 36836041
651 5219357
652 21333725
653 3299725
654 20137397
655 18118243
656 8592155
657 17038879
658 96073783
659 114811319
660 139656023
661 18266755
662 26617745
663 114283895
664 99947627
665 739540919
666 506938487
667 40144225
668 10183459
669 74766307
670 233777999
671 84563525
672 60070945
673 73674153
674 2403401
675 65308339
676 44834525
677 157650779
678 57449975
679 13729001
680 57385867
681 27851525
682 34269977
683 114721321
684 338772577
685 72518039
686 73439405
687 12401623
688 80949121
689 136987207
690 10698919
691 558943
692 54385669
693 35807083
694 68717077
695 38182001
696 26545805
697 116055667
698 6494345
699 24609013
700 120434743
701 2115905
702 272432633
703 116521795
704 25829713
705 58543121
706 21807005
707 35916529
708 32405945
709 1850849
710 71607179
711 5005055
712 34657645
713 865880521
714 1873130143
715 209399981
716 24862279
717 71223625
718 87540125
719 9995167
720 28888379
721 30312139
722 62584225
723 167228633
724 295200451
725 404443481
726 138818617
727 65293481
728 174676975
729 21414679
730 32458023
731 70811455
732 8729903
733 9166417
734 3687827
735 104348057
736 482687647
737 463720475
738 32868803
739 30237987
740 676706437
741 14906875
742 16531463
743 237371017
744 11548537
745 150570581
746 17440555
747 1655645641
748 792645789
749 198730649
750 262350613
751 5794789
752 133225345
753 164595475
754 287039137
755 4482907
756 96629005
757 4389077
758 186777487
759 320537737
760 112528559
761 68354275
762 550119167
763 43710095
764 721723739
765 52425373
766 33767525
767 24578345
768 15070517
769 328783923
770 236976379
771 105604109
772 52726843
773 1508087
774 171169141
775 94574077
776 359578021
777 148591339
778 1988371
779 420586579
780 815706689
781 314226237
782 308269775
783 58772909
784 40381783
785 36511189
786 6654505
787 14661361
788 236321525
789 3350479
790 288012659
791 167191583
792 1629926153
793 28107409
794 13948109
795 58267027
796 11437855
797 314164279
798 122248841
799 96135611
800 135066659
801 65177609
802 92592227
803 298142243
804 93275039
805 1161705429
806 256896775
807 127690145
808 16811827
809 327871999
810 8157149
811 4366505
812 53852821
813 412916125
814 195106093
815 223402399
816 451846109
817 154860667
818 116272475
819 1968259799
820 38640173
821 46343275
822 21211619
823 4826855
824 1019211319
825 124764887
826 126330655
827 73502849
828 52154245
829 4724863
830 92094691
831 48161663
832 332948495
833 223216565
834 26851517
835 185805971
836 21809827
837 72824345
838 25298845
839 652865603
840 403118573
841 42594775
842 18869983
843 143666809
844 211303161
845 75289753
846 19655519
847 212265587
848 24604151
849 288911623
850 375491623
851 31554193
852 76400975
853 72974693
854 643192979
855 2292433
856 5172505
857 162683591
858 1153667821
859 39959843
860 280336069
861 32744525
862 16435133
863 22774895
864 69496141
865 41499601
866 25576705
867 648745747
868 1271629801
869 629092021
870 151105537
871 4733905
872 59316803
873 8211931
874 362843793
875 22532939
876 17515355
877 48028145
878 7351123
879 167331619
880 214765607
881 1404455
882 66090475
883 213917825
884 359047549
885 16166891
886 265902455
887 11206349
888 47930597
889 207612449
890 67893631
891 254094869
892 8954495
893 147965279
894 26479013
895 7534241
896 1047056155
897 43964975
898 25427545
899 241410829
900 508657303
901 206348493
902 347023703
903 37921169
904 141592507
905 54022969
906 33573589
907 41552147
908 102806803
909 1528568753
910 37154709
911 55158455
912 547350139
913 45149871
914 306590713
915 496512523
916 50577943
917 1378336663
918 74398775
919 96957817
920 110587771
921 22756591
922 13604437
923 119124475
924 28205567
925 65254721
926 20116525
927 458465231
928 48281717
929 66742117
930 106780927
931 744496775
932 38826725
933 127733053
934 277908839
935 1016843501
936 16236275
937 510726359
938 239122697
939 256953079
940 185092167
941 270580121
942 45800975
943 76614395
944 463229063
945 1539829369
946 283168405
947 62010091
948 145497611
949 1360894843
950 97719349
951 333602005
952 262572609
953 37842475
954 84202547
955 132473757
956 238820063
957 456457225
958 134198207
959 12658217
960 232644269
961 1284645103
962 388045259
963 259952095
964 86340331
965 88473253
966 66908855
967 24188463
968 46053475
969 32267807
970 54005809
971 110550055
972 358092845
973 86566337
974 209671693
975 562209907
976 7756199
977 34115345
978 270030397
979 254287241
980 25673791
981 165446567
982 55531333
983 48132491
984 349332841
985 1615493297
986 865555405
987 343389145
988 308063987
989 450250151
990 122981621
991 1311805
992 28308553
993 24625315
994 434704971
995 214059643
996 393274141
997 12709411
998 99949759
999 130927489
1000 1469747869