1 0
2 1
3 3
4 14
5 100
6 115
7 196
8 500
9 189
10 333
11 847
12 1022
13 1352
14 1671
15 1920
16 3432
17 3757
18 2937
19 1444
20 7730
21 1092
22 427
23 4232
24 8668
25 15000
26 13037
27 19197
28 20902
29 1682
30 17999
31 16337
32 27856
33 32043
34 31873
35 16170
36 14298
37 47915
38 5603
39 12792
40 8260
41 16810
42 18949
43 51772
44 64526
45 65475
46 91239
47 50807
48 106040
49 26411
50 111665
51 6222
52 66690
53 11236
54 22419
55 49005
56 126636
57 85728
58 127453
59 97468
60 79990
61 85583
62 178279
63 136836
64 24992
65 207025
66 166001
67 161604
68 33898
69 111297
70 58331
71 85697
72 15636
73 106580
74 374845
75 211125
76 315742
77 343882
78 450775
79 355737
80 493320
81 290871
82 206105
83 523564
84 182546
85 462400
86 377667
87 267699
88 563068
89 673285
90 512997
91 207025
92 485254
93 513453
94 96207
95 696730
96 843376
97 442223
98 834897
99 581526
100 270650
101 255025
102 943211
103 31827
104 593892
105 269850
106 875293
107 1133451
108 1170414
109 594050
110 872663
111 546564
112 1152984
113 1417359
114 437209
115 201020
116 529250
117 31941
118 323259
119 920465
120 930380
121 907742
122 717053
123 580314
124 163990
125 1156250
126 564879
127 241935
128 582464
129 1337214
130 1980329
131 1922032
132 925066
133 2175747
134 357979
135 939195
136 1172660
137 225228
138 1961693
139 985371
140 1574910
141 2551818
142 700271
143 799370
144 1659048
145 2291725
146 2715817
147 1220394
148 1942130
149 1931487
150 2609995
151 889239
152 2538780
153 2231658
154 2173941
155 1830705
156 754598
157 961311
158 666047
159 2941500
160 1306640
161 3680782
162 294705
163 1408157
164 3747482
165 2377650
166 3967979
167 1617562
168 1536388
169 2084953
170 3184661
171 1647243
172 3273934
173 1107373
174 2711471
175 5181750
176 1597816
177 1389450
178 2377633
179 5158601
180 2507970
181 3767515
182 3254939
183 78690
184 3891692
185 4757275
186 5775517
187 2028202
188 3722870
189 4660740
190 3312327
191 5180302
192 3769568
193 2383936
194 6434881
195 6221280
196 1342698
197 4540653
198 4088139
199 5385736
200 6601300
201 700887
202 5548029
203 3255511
204 7821598
205 6471850
206 7312071
207 4470579
208 2959944
209 2271412
210 503993
211 4763747
212 3925074
213 3917496
214 5622099
215 9254245
216 3063996
217 8428931
218 4730053
219 4716822
220 4265030
221 5567874
222 3424831
223 2138347
224 4006320
225 9230625
226 8483473
227 6904886
228 8145338
229 1625671
230 4124659
231 10911054
232 5378340
233 2714450
234 9565725
235 12602345
236 10322286
237 131772
238 1180599
239 5140890
240 1313560
241 3078293
242 6159241
243 1023516
244 277794
245 540225
246 7313867
247 10249512
248 8372108
249 12421614
250 433325
251 4536072
252 13544790
253 12039511
254 8407271
255 8097780
256 2246272
257 1122833
258 16231081
259 8250963
260 7609290
261 14464359
262 7390363
263 17776433
264 15770612
265 13974775
266 12209229
267 11288226
268 15418174
269 7091378
270 15146991
271 9327007
272 16282600
273 1973244
274 2151857
275 12039500
276 3448114
277 6828881
278 8287595
279 5085612
280 19926620
281 12633760
282 4008677
283 20983318
284 14625574
285 21308025
286 5257967
287 20345143
288 20280144
289 18124057
290 7404657
291 5279322
292 20520154
293 4378299
294 15617035
295 5412955
296 20823748
297 17406576
298 16152045
299 13320749
300 22791950
301 14314958
302 2491951
303 9304221
304 21710008
305 21302725
306 7534977
307 26012724
308 9484354
309 21134055
310 27600323
311 2127862
312 27159340
313 7935489
314 20233373
315 12470220
316 14645494
317 31151590
318 30312767
319 23201508
320 19867680
321 12297189
322 9107609
323 3553323
324 22057002
325 10456875
326 10459219
327 11478027
328 11728788
329 13097161
330 20888989
331 6683221
332 3233182
333 4250745
334 20512775
335 28976495
336 10128776
337 113569
338 10908417
339 34055940
340 13024210
341 30233060
342 36068403
343 30118144
344 20430332
345 33604725
346 26321429
347 29861432
348 12841606
349 33860678
350 37581655
351 26785161
352 16246000
353 26790935
354 4675337
355 39849105
356 8533498
357 43648248
358 28967747
359 29127106
360 16355940
361 45091066
362 13058605
363 46833897
364 11482926
365 36503650
366 29429023
367 44043303
368 31768152
369 28911519
370 8115321
371 35924301
372 34502690
373 21982382
374 38520691
375 36215625
376 32233164
377 29136445
378 46941237
379 10485793
380 8301270
381 2517267
382 4171247
383 25083819
384 40643008
385 26532275
386 33588753
387 24612039
388 36230858
389 6960766
390 4796987
391 25531127
392 20511540
393 49012995
394 48278197
395 25307255
396 4576638
397 56739240
398 30309887
399 31287585
400 4642600
401 4020025
402 7634449
403 1948908
404 19477042
405 24986475
406 49657251
407 13251920
408 36181916
409 30612423
410 30845653
411 44483763
412 9958246
413 34966645
414 58670079
415 37923945
416 23099024
417 57268695
418 65860289
419 54950593
420 33370330
421 29953729
422 37677635
423 66979089
424 37670916
425 76585000
426 64715861
427 5834528
428 72785038
429 55457688
430 23492319
431 31950892
432 14059512
433 23811103
434 61492313
435 59896020
436 70081986
437 48124188
438 18914227
439 25439172
440 3786860
441 25958583
442 49198357
443 21783639
444 47798006
445 66140350
446 46856535
447 7660686
448 26037088
449 18144090
450 56429985
451 12610862
452 57068842
453 34339665
454 19632547
455 15775305
456 43699924
457 11068997
458 11080621
459 7444062
460 40970590
461 79057812
462 71509319
463 49090501
464 31666376
465 14559150
466 95109433
467 39910287
468 94399890
469 74786740
470 2224651
471 32464146
472 72679740
473 84142443
474 27891661
475 48328875
476 91506886
477 83123928
478 80472015
479 35563355
480 95823920
481 37943204
482 40671881
483 4310292
484 84403066
485 85621900
486 44029251
487 14941647
488 32082340
489 110315955
490 115656317
491 110415098
492 66048622
493 19443920
494 88408919
495 11156805
496 98877848
497 66198412
498 108999833
499 54531219
500 24953250
501 74381466
502 93393835
503 123215383
504 44743692
505 96654475
506 127947413
507 27609699
508 80171798
509 19431075
510 79100983
511 103403916
512 33983744
513 134830251
514 91924529
515 45141295
516 111091274
517 97827774
518 30027091
519 61236291
520 117668980
521 69217455
522 9255669
523 41029350
524 25627006
525 66005625
526 93524639
527 71098624
528 129559144
529 8675071
530 74535649
531 118235646
532 21877170
533 132101385
534 49633787
535 56729795
536 127061212
537 17976612
538 88194069
539 31085747
540 145353510
541 80779956
542 44469743
543 33417849
544 152271312
545 121483225
546 60649225
547 2094463
548 8208218
549 82081539
550 102978315
551 102313537
552 134546756
553 71865115
554 141286341
555 9097005
556 2060814
557 172498444
558 81929559
559 80932579
560 11709240
561 136064379
562 17762289
563 81144064
564 32385538
565 135351400
566 14842499
567 73774071
568 80900524
569 111050023
570 174248981
571 41081166
572 179094006
573 41152287
574 162860159
575 55294875
576 96464544
577 188437814
578 168684353
579 17881257
580 48062570
581 158991231
582 135486787
583 133607276
584 43981332
585 134266275
586 143896693
587 127835099
588 67364318
589 104423221
590 63326647
591 131797137
592 121406472
593 195165195
594 183400569
595 157278730
596 49493330
597 2971866
598 138300955
599 72477802
600 168523900
601 168680867
602 172694149
603 82660446
604 22861702
605 146043975
606 101855975
607 124167313
608 148433776
609 143707557
610 85054313
611 99303386
612 176146554
613 40207283
614 172526323
615 175319895
616 3478244
617 52915771
618 15407461
619 82379615
620 76251630
621 96924438
622 31950583
623 76849542
624 50619608
625 224218750
626 183073385
627 237580959
628 194299746
629 186742552
630 154979979
631 77641395
632 203108684
633 115133205
634 189561877
635 43628945
636 84738838
637 24346140
638 153495463
639 255745053
640 171012160
641 125729586
642 248497121
643 57055962
644 229795530
645 15531600
646 217208779
647 54419170
648 163996596
649 105300250
650 272226645
651 17577651
652 126964286
653 185914324
654 116720143
655 137802830
656 69750184
657 113667570
658 249353377
659 185872268
660 166803890
661 35827522
662 44809123
663 256009494
664 234491932
665 220670275
666 101742933
667 32476897
668 157665702
669 39984123
670 174691311
671 117062660
672 105381136
673 183889174
674 16069169
675 80888625
676 13381082
677 275914058
678 124233443
679 305209142
680 135705220
681 174994527
682 147112453
683 309748696
684 310977294
685 241181650
686 112064519
687 227648442
688 235212408
689 72632313
690 12005977
691 7639696
692 133762562
693 175563234
694 118207283
695 3477780
696 76354796
697 214241769
698 234478789
699 225410025
700 185154550
701 313513838
702 196579071
703 264896024
704 346755552
705 199969725
706 156348993
707 228430993
708 14350570
709 227211812
710 44043643
711 101272707
712 225503572
713 56937328
714 268114973
715 115127870
716 336985758
717 99906780
718 68700751
719 347914753
720 73406280
721 9357138
722 283739825
723 48267480
724 281307666
725 249146250
726 12846691
727 172828983
728 67690428
729 353585412
730 306113309
731 212675678
732 264847238
733 153127365
734 365828167
735 161352345
736 387788464
737 19554084
738 36438873
739 45328043
740 185522810
741 223687893
742 324171267
743 334541694
744 4661284
745 310258975
746 350522645
747 309322989
748 318536174
749 244596436
750 130049975
751 313020555
752 235579416
753 227561871
754 156775073
755 297097030
756 349644834
757 44697822
758 233906291
759 274982664
760 279654540
761 332994575
762 52107973
763 299817035
764 7782486
765 133041150
766 26444999
767 240610201
768 128766848
769 167946524
770 382902641
771 13872603
772 338916106
773 26291276
774 426779859
775 5525750
776 456795892
777 19606818
778 411504037
779 406583470
780 127399870
781 125042005
782 277629159
783 385837344
784 372474088
785 362956525
786 328116617
787 206869246
788 173450226
789 380570205
790 335144307
791 242138547
792 244224348
793 487357975
794 380028645
795 35098455
796 275411622
797 63520900
798 357305431
799 217694741
800 416645200
801 26519508
802 463002217
803 161905678
804 235035866
805 320124350
806 37454355
807 491912499
808 41174468
809 522930319
810 220400973
811 57879448
812 503597006
813 527015055
814 418217327
815 395346720
816 25616824
817 44054274
818 26510969
819 428987286
820 323724930
821 450933429
822 406530923
823 445682482
824 74382892
825 209178750
826 437007277
827 465755649
828 564713526
829 37111014
830 237822639
831 488459307
832 379237664
833 516253416
834 499855537
835 448455120
836 384441706
837 415670940
838 328401723
839 146415568
840 7117460
841 493682138
842 557435573
843 40035756
844 261189726
845 220633725
846 454389279
847 183656704
848 466758280
849 425515404
850 522823305
851 343271274
852 388155154
853 454028016
854 446443323
855 357861105
856 406386428
857 154234290
858 199038125
859 141673152
860 627341190
861 87087567
862 261299351
863 260669150
864 180777456
865 485598025
866 372059145
867 533242281
868 519927226
869 595822029
870 205379971
871 176763353
872 38855012
873 234989775
874 458231645
875 669309375
876 555865070
877 506086882
878 233273623
879 632280522
880 406002520
881 136604336
882 180654033
883 294722442
884 441422306
885 467846400
886 212802579
887 410693418
888 62466508
889 158064200
890 161030637
891 378151983
892 638652822
893 586922464
894 278580383
895 294136380
896 257472192
897 54177006
898 599294217
899 329773877
900 26795850
901 548777476
902 128447875
903 498603189
904 578254900
905 556117975
906 285603061
907 241858806
908 479288254
909 718313616
910 209057303
911 743609216
912 126776360
913 727781516
914 745832681
915 572271195
916 269057138
917 360741381
918 115983027
919 661291263
920 451431580
921 566910498
922 347149133
923 259838345
924 438054694
925 662253750
926 736273247
927 527914449
928 508134288
929 450507402
930 352934969
931 689074995
932 2895258
933 720187365
934 717875667
935 273807270
936 738550020
937 798951790
938 428924285
939 17931144
940 667500110
941 363047210
942 25282495
943 817219831
944 626988280
945 124555725
946 645747641
947 696820593
948 110996738
949 135990751
950 556921635
951 607157391
952 360113516
953 711127647
954 541245381
955 78616555
956 867629750
957 170653197
958 49903655
959 355916547
960 774559840
961 702799481
962 685911217
963 747768537
964 725470250
965 674206900
966 98376635
967 462869055
968 683747284
969 728007762
970 363685301
971 350736852
972 663904350
973 852056100
974 629858039
975 114655125
976 792939976
977 171815220
978 228448249
979 777295651
980 306553170
981 513259200
982 625266403
983 579773400
984 832016444
985 716996275
986 512976853
987 658027965
988 767899782
989 350167318
990 562517967
991 21605782
992 183612720
993 437151369
994 958343729
995 601143180
996 659142010
997 468178239
998 592220683
999 619093287
1000 731406500