1 0
2 1
3 3
4 14
5 100
6 979
7 196
8 500
9 3834
10 1333
11 2178
12 1022
13 16731
14 12647
15 42420
16 23912
17 23409
18 26265
19 15162
20 79730
21 84441
22 21723
23 28566
24 160732
25 280625
26 329405
27 137295
28 569702
29 74849
30 71999
31 463202
32 715984
33 247665
34 31873
35 1302420
36 574170
37 807710
38 225091
39 1377129
40 968260
41 2153361
42 1204357
43 3152545
44 831182
45 2252475
46 91239
47 2957851
48 106040
49 3791179
50 3486665
51 6638772
52 7237698
53 7008455
54 3644091
55 1879130
56 8204972
57 2308044
58 7541709
59 6874975
60 6343990
61 12796519
62 4706511
63 3887541
64 12607904
65 5150275
66 12240833
67 19109673
68 1606058
69 9638058
70 5889331
71 5812273
72 17185044
73 3218716
74 11315893
75 18351750
76 1632670
77 32301192
78 3298087
79 21556414
80 34285320
81 2948076
82 18952617
83 15390026
84 14407442
85 42222900
86 54442427
87 7511232
88 8059260
89 54250929
90 14363997
91 43160572
92 67452422
93 68079441
94 54914751
95 7555730
96 45080176
97 10481626
98 2717281
99 10284516
100 49270650
101 5406530
102 91145891
103 98377257
104 2843620
105 85934100
106 125931973
107 115062450
108 49039470
109 133982037
110 16844663
111 62089959
112 93878232
113 4303153
114 98219113
115 117308395
116 53599714
117 14446458
118 167912523
119 191343432
120 37218380
121 48739889
122 113299629
123 58267191
124 181293270
125 174984375
126 564879
127 73983723
128 210297664
129 16364037
130 210695329
131 282933407
132 81423946
133 2175747
134 2764083
135 138720195
136 104306356
137 290788117
138 151761797
139 146008797
140 229326910
141 204383730
142 370064423
143 369249452
144 371921064
145 20583475
146 233013881
147 360167493
148 433100466
149 74706365
150 367109995
151 169593838
152 294018844
153 195636816
154 246875629
155 512001580
156 31125926
157 140277459
158 166327151
159 31079253
160 156954640
161 583766841
162 544490289
163 239599242
164 559526426
165 613306650
166 90879603
167 285722805
168 532599172
169 277213066
170 425702661
171 836682480
172 140662030
173 782942640
174 871935431
175 117728625
176 61567352
177 716724507
178 267445977
179 647516569
180 883139970
181 252816637
182 581997467
183 588413442
184 664219116
185 245359025
186 855176509
187 976369449
188 242931062
189 402985611
190 449147327
191 708935273
192 265651424
193 146165076
194 780381585
195 903421155
196 965123306
197 975503024
198 104999235
199 541266468
200 366601300
201 1088861421
202 1349060533
203 655758817
204 389856478
205 1600269975
206 741624615
207 660831561
208 1325800008
209 1736843922
210 315377993
211 662338917
212 385050194
213 989604390
214 681845835
215 1440380245
216 305394876
217 1275499743
218 1382640909
219 1674766803
220 1963497030
221 502085480
222 156599503
223 1277438552
224 655892912
225 817965000
226 2432550433
227 1375463597
228 292601786
229 1238551538
230 2340188659
231 1083307071
232 542326564
233 2621127209
234 2149320693
235 2595199470
236 260063150
237 599174157
238 594356567
239 32444728
240 1217825560
241 1654785771
242 1763547753
243 1278076239
244 3428598818
245 3397655100
246 2389223627
247 1924040833
248 2174296972
249 1957640988
250 1531683325
251 2819294750
252 669668118
253 3817694606
254 57568463
255 3357535530
256 1025656448
257 1664632947
258 685998049
259 216738711
260 552465290
261 3054772710
262 3658290147
263 3146705317
264 1469350388
265 2675151150
266 3908176101
267 1438850451
268 2460019838
269 3452415671
270 1452005991
271 785524936
272 5429543912
273 1812804357
274 3725471001
275 303195750
276 3935043826
277 5107772801
278 4477157611
279 634897143
280 4278614620
281 5781524420
282 4152775757
283 5732610442
284 4343917030
285 4743729525
286 6649056271
287 4180968071
288 689140560
289 3228420734
290 6933880657
291 1582378266
292 2858788186
293 834452280
294 295151059
295 6269472455
296 4040645828
297 6540726753
298 3959227253
299 1857752780
300 2911791950
301 6095725881
302 305471639
303 7687107273
304 5640602808
305 7681911475
306 1698039321
307 257488268
308 8833354178
309 6305407032
310 3632311323
311 5206007825
312 300501292
313 6876738017
314 6150143885
315 356284845
316 6230881206
317 8249744944
318 9806172095
319 23201508
320 3001755680
321 8810556015
322 9190325809
323 1890656275
324 1246497066
325 1486566250
326 6593194659
327 1270246215
328 2693582740
329 2327830946
330 3578651989
331 1819917771
332 10615599902
333 6133972887
334 7174375943
335 1344814620
336 10327920008
337 9989302102
338 2057475433
339 8916529872
340 10035544210
341 1973172289
342 11356546107
343 11894078602
344 7307087868
345 197859225
346 11168768413
347 13149385254
348 9790294150
349 6877737067
350 6768956655
351 10102532544
352 14932305136
353 12387131472
354 2444577857
355 5632208480
356 8851664634
357 9689498364
358 11774942019
359 6044003376
360 2815715940
361 15335002391
362 13627743941
363 11717877765
364 9319591918
365 14770522525
366 7236529735
367 13785823217
368 10098646616
369 9926863092
370 6491699321
371 13517034405
372 12029074274
373 12269229994
374 8042505163
375 15909262500
376 17255222988
377 14978691052
378 6582169629
379 663765061
380 2971389270
381 3486816750
382 8254130511
383 17834741998
384 9893063104
385 6532127525
386 12341254337
387 12775944699
388 14522176714
389 17607257597
390 182753987
391 17898695956
392 13091786036
393 22325346714
394 1638515781
395 2860281505
396 10623528894
397 20767665103
398 22159031879
399 20485113663
400 13444642600
401 16511207481
402 15924012409
403 2096375372
404 6085889330
405 17429679225
406 12965876539
407 12350955089
408 24282662300
409 14535213371
410 24773484653
411 22746959400
412 16864179494
413 26099615535
414 9283202799
415 5612847195
416 599029392
417 12456771618
418 27672951185
419 22343648470
420 12109714330
421 25027138164
422 22282506243
423 29584896219
424 11318974468
425 3377506875
426 4548624869
427 33016135320
428 3208895118
429 5266394562
430 739055319
431 6837305127
432 24119908344
433 20725409038
434 26547359609
435 4916355645
436 28664322306
437 34931667542
438 32705678635
439 9247331743
440 6307402860
441 13920070185
442 11361164685
443 20104532556
444 20004269558
445 38486950850
446 10781557391
447 29034913161
448 39139232608
449 19841772021
450 20650679985
451 4691037263
452 21204167274
453 33685742739
454 4137005763
455 6232736055
456 3646814932
457 25494615128
458 1067871653
459 18090826335
460 9385226590
461 33683515895
462 16638178823
463 34589081257
464 9721708744
465 25552893900
466 11226525993
467 44547295318
468 31767898578
469 47322849462
470 4778082651
471 8600407248
472 36140518204
473 5692804744
474 39857554237
475 9157938250
476 4405513926
477 31340147832
478 16462774815
479 33775550728
480 39908943920
481 31754065889
482 41585314209
483 9131275839
484 33984994362
485 18681334275
486 3258184419
487 42865925060
488 47215076772
489 50507218794
490 36469197317
491 6502436732
492 46870575406
493 44473835167
494 30226854919
495 26451804555
496 14863774104
497 51872384018
498 14435694905
499 23413813031
500 45524953250
501 45344921826
502 25647607451
503 11831459867
504 8366307852
505 47104137600
506 48192561549
507 37951848012
508 42817634710
509 22569582234
510 31517387983
511 9043403593
512 55197469952
513 57647257173
514 64731174673
515 24494907920
516 62622674954
517 69468411100
518 54236841571
519 58357151994
520 44831012980
521 48859380000
522 70274159781
523 12629928046
524 74554339838
525 74009302500
526 36330887063
527 34466446629
528 76083702376
529 72842332459
530 34167368649
531 17785347984
532 14928185202
533 28447536104
534 39945239435
535 19810548170
536 73734594780
537 38731514862
538 11144375981
539 17099485018
540 7546161510
541 2139205429
542 60229663007
543 64554929670
544 47322102224
545 15661831225
546 38637455857
547 30935218510
548 1653874138
549 23578700697
550 35873603315
551 48782001478
552 80027935556
553 84797165992
554 10683237109
555 53004798255
556 47612714446
557 34215810965
558 51161816487
559 43575475450
560 33027517240
561 26972953491
562 36761158185
563 34701132182
564 23893402690
565 86348447150
566 15064526667
567 91398189834
568 3196157868
569 45244952228
570 105549065981
571 74322676155
572 9723705654
573 61936750380
574 95857187503
575 20967326125
576 56280739488
577 39184744513
578 73160693009
579 59219765652
580 111847238570
581 99985568200
582 68739290851
583 86529312408
584 55415105044
585 62396971650
586 101161384805
587 56558933936
588 57193953950
589 20129397183
590 11564550647
591 113046310974
592 4063425544
593 83814835852
594 84017234169
595 7951139105
596 684619538
597 109157148615
598 67714013627
599 73575733060
600 23712523900
601 88303892073
602 110783468605
603 105764161860
604 95654268678
605 23619227225
606 50174484575
607 7057272146
608 122865052528
609 9178368717
610 10753161313
611 23137315617
612 107451540858
613 122814836884
614 31653200307
615 88799110770
616 101682508004
617 144507260266
618 78377046085
619 55107364503
620 140689771630
621 131812607988
622 118427739799
623 67056659201
624 45243155672
625 141581640625
626 11467534681
627 103271188053
628 139386611170
629 91268839726
630 39162311979
631 26206558859
632 29990552908
633 107149583019
634 130922535229
635 59446735945
636 80606948566
637 38537099237
638 91306114735
639 116624780127
640 154049540160
641 165525054374
642 124085643905
643 30097846853
644 763975498
645 89908133475
646 3721828547
647 10346340044
648 63290684340
649 102068374727
650 105728226645
651 67887612597
652 79951292990
653 158899608214
654 89908850887
655 165372491330
656 41003310504
657 125178353883
658 43837571113
659 175907256174
660 64565907890
661 65016903247
662 14260567995
663 66120149316
664 47660792860
665 193725063525
666 70113509085
667 154634518620
668 41888534182
669 31778324877
670 182437069311
671 147547577628
672 72936848656
673 15120128807
674 199646748817
675 136631701125
676 130066922778
677 188310886256
678 20694173075
679 59784108552
680 67424153220
681 141031268013
682 192379140661
683 187016373078
684 74554110222
685 129773089025
686 19481795879
687 54700422546
688 81324719736
689 117822429153
690 72941003977
691 172235991358
692 203597329794
693 17814628755
694 216381440731
695 179939950780
696 187870874348
697 66242972004
698 63147131309
699 86974563171
700 162767154550
701 126734774905
702 51396943455
703 143405613948
704 104671941088
705 107773575600
706 85315136465
707 134164470090
708 116419881706
709 97524638129
710 204411224643
711 216834807600
712 143159378260
713 58414139945
714 13735905701
715 54578483245
716 45485574366
717 215363365572
718 226228048503
719 247153367529
720 206479550280
721 43111973653
722 55609695881
723 146308364409
724 273903276370
725 252141786875
726 24885563131
727 114292282134
728 208029172156
729 174305384973
730 189368375309
731 247083182790
732 248542112582
733 170682745786
734 248311036975
735 62103550845
736 222855835312
737 158944828625
738 112983622305
739 174393365051
740 141608698810
741 226035994548
742 5226393123
743 244797296266
744 111198972964
745 147513989475
746 305078649669
747 266248600263
748 138007994542
749 114536208164
750 108973799975
751 60882779948
752 107826108440
753 209009914824
754 129183755337
755 211608214655
756 285523247394
757 68150998423
758 92999562347
759 98655215439
760 309318758540
761 19724282139
762 319059082861
763 203296907814
764 20075250966
765 69526095525
766 9465002015
767 196069075943
768 48145159040
769 5170269223
770 306260012641
771 183797791014
772 190820170378
773 341362939939
774 170135425443
775 94498853875
776 50923962100
777 89617216521
778 274481678101
779 25933956976
780 355566847870
781 304055189163
782 261381254487
783 337860064305
784 58681200872
785 110654907025
786 241179593993
787 301446892300
788 78462069746
789 282802784880
790 250305917307
791 377366355849
792 24587085660
793 277253235610
794 86977978477
795 48271246455
796 282211721446
797 307870557284
798 30339311359
799 316468782121
800 95648645200
801 118742594139
802 98990277345
803 251803776400
804 244502713946
805 382175335850
806 380175857571
807 417259361298
808 385126476228
809 422514608132
810 30512537973
811 31529171577
812 82953245518
813 125196343959
814 424889141655
815 17718334720
816 248331309496
817 401958538355
818 278076974425
819 400907513097
820 150847188930
821 208524693965
822 220349781131
823 133674264795
824 136586581548
825 448298647500
826 3818367133
827 252727495867
828 280990508214
829 193173136485
830 170630348639
831 129032246091
832 423688058144
833 117852189427
834 320711580145
835 462701657870
836 488255783466
837 169878408057
838 297511040083
839 343869632026
840 465279757460
841 435904353110
842 195162381861
843 52159744065
844 32125403678
845 326633592350
846 47077560951
847 314336340395
848 448669899400
849 5933155845
850 275650823305
851 20681007957
852 350442292882
853 20314843280
854 232141384731
855 210991749480
856 307117952252
857 71279009899
858 504238750301
859 91414601328
860 69321389190
861 340927209021
862 336525861551
863 391043942526
864 128530313712
865 254840945650
866 233528879809
867 218205839523
868 563589846778
869 226996865634
870 1522385971
871 473953378340
872 566950750052
873 169896337110
874 314910842549
875 324911496875
876 325911011054
877 233217602767
878 2940618231
879 80092998885
880 242328562520
881 290066888920
882 90063548841
883 482908958729
884 148274142562
885 123849280650
886 490544854059
887 524506634771
888 66584038348
889 521483827998
890 63608240637
891 291098168064
892 620234940246
893 586922464
894 474717857759
895 571677284255
896 377902118592
897 59958121665
898 485056174065
899 551071879719
900 371816795850
901 268253146042
902 437515449443
903 287661190719
904 279092005428
905 619472834850
906 474751794469
907 309144913008
908 150201950654
909 445363255584
910 206687511303
911 245706411260
912 446913037352
913 349287993142
914 55721572649
915 606526423320
916 377639527474
917 618008006994
918 389247160923
919 301031944596
920 636639527580
921 438055688658
922 412614086781
923 343886252424
924 259193654566
925 448624722500
926 602605537455
927 18053070075
928 416081085328
929 136750572532
930 741165731969
931 35388118108
932 715651785370
933 502638921831
934 365739541459
935 471096423270
936 159823566084
937 260758548938
938 740717348069
939 757579388529
940 448352276110
941 314493630327
942 719732503063
943 493891562347
944 592013354232
945 168062372100
946 781202221833
947 752307959448
948 61452936962
949 131755224497
950 152312296635
951 396246418851
952 547376206188
953 165160531277
954 579664438269
955 234373278930
956 167748687606
957 774967917009
958 380751259551
959 615091849610
960 421024159840
961 445342143662
962 217913530449
963 856295748963
964 127039099754
965 380795595775
966 846539922179
967 847727375086
968 327217870804
969 368308704198
970 400114459301
971 340916220144
972 283509559134
973 761736259942
974 834087260487
975 494130702000
976 685062573512
977 691209766473
978 428660587465
979 453044517849
980 58660457170
981 263910502539
982 225056248219
983 298836468718
984 477213968444
985 352404154275
986 588125738781
987 471795381435
988 227409013702
989 623331082154
990 906821783967
991 400024179163
992 229588612400
993 114997310238
994 541117624929
995 628093838555
996 173567530810
997 912212993399
998 753059298627
999 274794918012
1000 693731406500