1 1
2 6
3 18
4 12
5 200
6 42
7 196
8 56
9 459
10 950
11 5203
12 396
13 9243
14 980
15 1800
16 336
17 19363
18 270
19 13357
20 600
21 1764
22 10406
23 72473
24 168
25 18625
26 34814
27 4293
28 812
29 145493
30 1350
31 15376
32 992
33 19602
34 38726
35 41615
36 1836
37 99937
38 26714
39 1521
40 440
41 274003
42 3822
43 475193
44 20812
45 1485
46 144946
47 620729
48 1680
49 33271
50 37250
51 262701
52 36972
53 592699
54 2754
55 65945
56 21112
57 40071
58 290986
59 1228793
60 9000
61 1812127
62 76880
63 14112
64 5952
65 128375
66 31218
67 1800089
68 77452
69 652257
70 83230
71 1426603
72 864
73 1364224
74 199874
75 64125
76 218044
77 36421
78 18486
79 979837
80 16720
81 64395
82 548006
83 2280259
84 588
85 924800
86 950386
87 1309437
88 87032
89 8111104
90 2970
91 447993
92 592388
93 72075
94 1241458
95 671365
96 672
97 1815937
98 66542
99 20493
100 74500
101 10292809
102 116178
103 6545753
104 139256
105 124845
106 1185398
107 7338809
108 27540
109 7758293
110 131890
111 299811
112 6496
113 8644613
114 80142
115 3028525
116 1167308
117 3042
118 2457586
119 12334231
120 3720
121 320771
122 3624254
123 1664067
124 169136
125 311875
126 8820
127 1032256
128 16256
129 1425579
130 256750
131 8975203
132 130548
133 70756
134 3600178
135 67095
136 258944
137 10266643
138 726846
139 5351917
140 20300
141 5586561
142 2853206
143 11676379
144 4320
145 4457155
146 6821120
147 301497
148 1609796
149 33057289
150 149250
151 41292611
152 436088
153 1055853
154 72842
155 192200
156 42588
157 7715137
158 1959674
159 3589743
160 21120
161 3062381
162 25758
163 25957913
164 1096012
165 197835
166 4560518
167 46546741
168 15288
169 740389
170 4103630
171 159201
172 6353164
173 20680939
174 2336298
175 351575
176 174064
177 11059137
178 22543166
179 57321349
180 5940
181 47405167
182 2997722
183 5436381
184 1184776
185 10061225
186 144150
187 3846403
188 4974668
189 127008
190 1342730
191 153256681
192 6720
193 57475207
194 3631874
195 385125
196 17836
197 30542683
198 98010
199 15721597
200 19000
201 5400267
202 20585618
203 4774357
204 1161780
205 3437645
206 13091506
207 2227941
208 147888
209 1312729
210 249690
211 18743341
212 2370796
213 21399045
214 14677618
215 39707275
216 25704
217 4708900
218 15516586
219 12278016
220 263780
221 3846947
222 599622
223 88666807
224 9632
225 97875
226 17289226
227 46736803
228 160284
229 23965537
230 6057050
231 480249
232 2368024
233 202335103
234 12402
235 43517065
236 14745516
237 2939511
238 5721044
239 81854393
240 45600
241 195907213
242 641542
243 656829
244 7248508
245 831775
246 1644018
247 67838797
248 107632
249 13763973
250 623750
251 189696011
252 17892
253 15978721
254 5161280
255 8318865
256 55552
257 203629067
258 2851158
259 4896913
260 169000
261 7129737
262 17950406
263 72696619
264 124872
265 56306405
266 353780
267 68009439
268 28855292
269 116718293
270 20790
271 39731581
272 224128
273 452907
274 20533286
275 1368125
276 2970588
277 254970467
278 10703834
279 432450
280 258440
281 88673203
282 9953754
283 135911033
284 5706412
285 2014095
286 23352758
287 11696111
288 6048
289 2834801
290 8914310
291 5447811
292 5475584
293 100529179
294 199626
295 122983435
296 3219592
297 79299
298 66114578
299 381446559
300 256500
301 7778743
302 82585222
303 185576289
304 1495984
305 56726645
306 1576206
307 27237961
308 145684
309 19637259
310 912950
311 300705589
312 73944
313 183887813
314 15430274
315 374535
316 15727004
317 191029589
318 3556194
319 184178159
320 19840
321 66049281
322 6124762
323 134688739
324 257580
325 973375
326 51915826
327 23274879
328 4437512
329 56486339
330 395670
331 72419821
332 9121036
333 4497165
334 93093482
335 36136115
336 51744
337 76431937
338 1480778
339 77801517
340 1167560
341 34978075
342 240426
343 3027661
344 15250552
345 18566175
346 41361878
347 250571129
348 9506316
349 339946591
350 703150
351 167427
352 129536
353 439745161
354 22118274
355 17870345
356 24333312
357 37002693
358 114642698
359 277480793
360 11160
361 12435367
362 94810334
363 107811
364 1594684
365 163599935
366 10872762
367 98727037
368 2369552
369 4992201
370 19987400
371 4148893
372 46128
373 311231573
374 7692806
375 2058375
376 13271672
377 5696093
378 108486
379 108736237
380 2685460
381 9290304
382 306513362
383 224580859
384 11904
385 2790865
386 114950414
387 4276737
388 29129876
389 353031893
390 462150
391 76440109
392 266168
393 54056757
394 61085366
395 79010665
396 81972
397 375267029
398 31443194
399 689871
400 304000
401 1418425621
402 10800534
403 40733225
404 98868092
405 1189485
406 9548714
407 193804853
408 464712
409 469892329
410 6875290
411 138684141
412 34924828
413 422499413
414 3913542
415 68545135
416 591552
417 16055751
418 2625458
419 1176785383
420 60900
421 895244291
422 37486682
423 33638229
424 9572648
425 61376375
426 8559618
427 155526637
428 58756268
429 1854567
430 79414550
431 320066203
432 85536
433 649274407
434 9794512
435 20814315
436 62113868
437 85162123
438 32645454
439 169016317
440 208120
441 1240533
442 7693894
443 521433593
444 1199244
445 127527655
446 177333614
447 357058683
448 127232
449 542911493
450 128250
451 733667407
452 69462908
453 123877833
454 93473606
455 6290375
456 320568
457 572455109
458 47931074
459 4213161
460 24754900
461 1175453651
462 218526
463 595302713
464 4736048
465 648675
466 404670206
467 407172163
468 24804
469 26426743
470 87034130
471 23145411
472 29491032
473 70291111
474 5879022
475 13161775
476 3795148
477 10769229
478 163708786
479 1098792949
480 67200
481 315575923
482 391814426
483 9187143
484 1283084
485 182061725
486 386370
487 1385778467
488 14497016
489 77873739
490 1663550
491 1183466629
492 6656268
493 276832811
494 135677594
495 886545
496 154256
497 70115269
498 13681554
499 248253997
500 1247500
501 502755003
502 379392022
503 508801099
504 137592
505 51464045
506 31957442
507 6149403
508 11354816
509 2373441041
510 16637730
511 66846976
512 390144
513 2388015
514 407258134
515 819280025
516 5702316
517 276109537
518 9793826
519 124444263
520 689000
521 565411603
522 7856622
523 858060473
524 35900812
525 1054725
526 145393238
527 83542675
528 499488
529 51478577
530 112612810
531 99720207
532 711284
533 605393659
534 67629498
535 305974525
536 57710584
537 344888787
538 233436586
539 3314311
540 132840
541 1266430687
542 79463162
543 142215501
544 520064
545 388270535
546 895986
547 327035437
548 41066572
549 36737433
550 2637800
551 668833003
552 2907384
553 27566497
554 509940934
555 30183675
556 85784684
557 1727776681
558 691920
559 349041277
560 162400
561 11539209
562 177346406
563 713497219
564 44772012
565 360405025
566 271822066
567 631071
568 79889768
569 1104996293
570 4028190
571 1489029247
572 46705516
573 921947259
574 23392222
575 91514125
576 79488
577 383867137
578 5669602
579 172425621
580 17526440
581 223657693
582 10895622
583 1584902407
584 9549568
585 304200
586 201058358
587 808703443
588 168756
589 191086325
590 245758600
591 412500861
592 9637168
593 833759779
594 40986
595 186715165
596 158692748
597 47164791
598 855209966
599 1289171993
600 57000
601 433802401
602 15557486
603 16200801
604 165170444
605 12976645
606 61756854
607 446928637
608 4296736
609 21493437
610 113453290
611 2736816251
612 4223412
613 1381702613
614 115549274
615 10312935
616 291368
617 939159763
618 39274518
619 473970157
620 1825900
621 11995857
622 601411178
623 2417655541
624 739440
625 3903125
626 367775626
627 3538161
628 154302740
629 690765913
630 749070
631 736199689
632 31454008
633 56230023
634 382059178
635 245966615
636 14358972
637 37602747
638 368356318
639 102896253
640 122240
641 3160085771
642 73433886
643 3721454449
644 12249524
645 119121825
646 269377478
647 1624621529
648 103032
649 513864571
650 1946750
651 45911775
652 138477628
653 1670244053
654 46549758
655 337127845
656 8875024
657 231028137
658 112972678
659 3433859867
660 791340
661 577172641
662 144839642
663 11540841
664 36703928
665 9752225
666 1798866
667 1780000889
668 223446668
669 266000421
670 72272230
671 198187231
672 19488
673 4267044109
674 152863874
675 1090125
676 2961556
677 1240696603
678 86497206
679 307184353
680 2034560
681 631178721
682 69956150
683 1273981459
684 2404260
685 1463888155
686 931588
687 71896611
688 30589168
689 69345783
690 18171150
691 659401261
692 82723756
693 960498
694 501142258
695 536154275
696 9345192
697 783095531
698 679893182
699 1216615791
700 171500
701 1377397003
702 410670
703 145284089
704 647680
705 176907765
706 879490322
707 936645619
708 103218612
709 2137902293
710 35740690
711 44092665
712 16313344
713 1449360019
714 74005386
715 146108105
716 459851716
717 736689537
718 554961586
719 4459822547
720 23760
721 595663523
722 24870734
723 587721639
724 189620668
725 22285775
726 1313334
727 767952637
728 13002808
729 9563751
730 327199870
731 3905644549
732 21745524
733 2362459733
734 197454074
735 2742285
736 3273728
737 218304559
738 9984402
739 4842454907
740 40244900
741 121938219
742 8297786
743 1640137579
744 230640
745 826432225
746 622463146
747 41291919
748 15385612
749 308630693
750 1871250
751 3387954007
752 26543344
753 1707264099
754 11392186
755 344181095
756 89964
757 6072600253
758 217472474
759 61815237
760 2180440
761 7932220337
762 34935414
763 380156357
764 668769692
765 3940515
766 449161718
767 1804282363
768 119040
769 3637461511
770 5581730
771 1832661603
772 229900828
773 2770741973
774 8553474
775 3579725
776 58259752
777 14690739
778 706063786
779 2835767993
780 1540500
781 381225625
782 152880218
783 23976243
784 532336
785 2203497355
786 53851218
787 2924041049
788 122170732
789 1090449285
790 158021330
791 282718429
792 477576
793 628849
794 750534058
795 80014365
796 251861564
797 2024411083
798 1379742
799 1019526397
800 796000
801 204028317
802 2836851242
803 2675956547
804 21601068
805 148397725
806 81466450
807 1050464637
808 197736184
809 5294096809
810 775170
811 1066165741
812 4073804
813 119194743
814 387609706
815 2164709275
816 1858848
817 5150329601
818 1094352302
819 298116
820 13750580
821 5533202569
822 61599858
823 3343973273
824 69849656
825 4104375
826 240843428
827 2261753203
828 8911764
829 1138758337
830 137090270
831 764911401
832 4140864
833 330192037
834 32111502
835 1163668525
836 5250916
837 14452479
838 2353570766
839 5905193269
840 241080
841 246109399
842 1790488582
843 532985907
844 374866820
845 18509725
846 33519366
847 18838127
848 19145296
849 407733099
850 122752750
851 7242734201
852 85596180
853 4964476207
854 311053274
855 5896935
856 176131416
857 10070030239
858 70058274
859 3802300793
860 44449960
861 35088333
862 640132406
863 6426611701
864 30240
865 621025885
866 1298548814
867 8504403
868 19992644
869 1561604297
870 41628630
871 638017081
872 434464408
873 81717165
874 170324246
875 20365625
876 4092672
877 1348283137
878 338032634
879 604204383
880 2206160
881 15042776341
882 1808982
883 4130012633
884 15387788
885 665740365
886 1042867186
887 2790669643
888 2398488
889 200628631
890 255055310
891 2438667
892 354667228
893 2480024419
894 198343734
895 1034923405
896 231168
897 184255461
898 1085822986
899 3495469325
900 391500
901 1462053601
902 1467334814
903 23336229
904 138925816
905 1123538495
906 247755666
907 4476033209
908 186947212
909 741999429
910 12580750
911 3023402203
912 2616528
913 1078562507
914 1144910218
915 170179935
916 384077884
917 3521636713
918 6335118
919 6208367911
920 29619400
921 81713883
922 2350907302
923 3144469939
924 913836
925 50306125
926 1190605426
927 58911777
928 18998944
929 4809727493
930 2738850
931 49759157
932 809340412
933 5415601299
934 814344326
935 89519705
936 85176
937 1644435937
938 52853486
939 551663439
940 24829160
941 14997391697
942 46290822
943 5030481593
944 137624816
945 271215
946 140582222
947 20381778143
948 11758044
949 5127121493
950 26323550
951 1719266301
952 32733568
953 5192230853
954 21538458
955 1393391795
956 656205092
957 346940253
958 2197585898
959 71866501
960 200640
961 45431275
962 631151846
963 396912969
964 1343529692
965 8985390025
966 18374286
967 1807527037
968 2566168
969 404066217
970 363187400
971 16478032157
972 1545480
973 903448987
974 2771556934
975 2920125
976 60534448
977 3729344803
978 155747478
979 2217745343
980 281260
981 69824637
982 2366933258
983 3798482059
984 6576072
985 4354175755
986 553665622
987 169459017
988 271355188
989 7509970511
990 392040
991 7784956087
992 7712800
993 217259463
994 140230538
995 1574134775
996 55055892
997 1981059937
998 496507994
999 43245711
1000 995000