1 1
2 5
3 19
4 37
5 101
6 95
7 295
8 293
9 505
10 505
11 1211
12 703
13 2029
14 1475
15 1919
16 2341
17 4625
18 2525
19 6499
20 3737
21 5605
22 6055
23 11639
24 5567
25 12601
26 10145
27 13627
28 10915
29 23549
30 9595
31 28831
32 18725
33 23009
34 23125
35 29795
36 18685
37 49285
38 32495
39 38551
40 29593
41 67241
42 28025
43 77659
44 44807
45 51005
46 58195
47 101615
48 44479
49 101137
50 63005
51 87875
52 75073
53 146069
54 68135
55 122311
56 86435
57 123481
58 117745
59 201899
60 71003
61 223261
62 144155
63 148975
64 149797
65 204929
66 115045
67 296275
68 171125
69 221141
70 148975
71 352871
72 147965
73 383689
74 246425
75 239419
76 240463
77 357245
78 192755
79 486799
80 236441
81 367921
82 336205
83 564899
84 207385
85 467125
86 388295
87 447431
88 354823
89 697049
90 255025
91 598555
92 430643
93 547789
94 508075
95 656399
96 355775
97 903265
98 505685
99 611555
100 466237
101 1020101
102 439375
103 1082119
104 594497
105 566105
106 730345
107 1213595
108 504199
109 1283149
110 611555
111 936415
112 690595
113 1430129
114 617405
115 1175539
116 871313
117 1024645
118 1009495
119 1364375
120 562267
121 1611721
122 1116305
123 1277579
124 1066747
125 1575101
126 744875
127 2032255
128 1198373
129 1475521
130 1024645
131 2230931
132 851333
133 1917205
134 1481375
135 1376327
136 1355125
137 2552585
138 1105705
139 2666299
140 1102415
141 1930685
142 1764355
143 2457119
144 1182205
145 2378449
146 1918445
147 1921603
148 1823545
149 3285749
150 1197095
151 3420151
152 1904207
153 2335625
154 1786225
155 2911931
156 1426387
157 3845245
158 2433995
159 2775311
160 1891225
161 3433505
162 1839605
163 4304179
164 2487917
165 2323909
166 2824495
167 4629575
168 1642265
169 4457545
170 2335625
171 3281995
172 2873383
173 5147789
174 2237155
175 3717295
176 2834951
177 3836081
178 3485245
179 5703299
180 1887185
181 5896981
182 2992775
183 4241959
184 3410227
185 4977785
186 2738945
187 5600875
188 3759755
189 4019965
190 3281995
191 6931391
192 2846143
193 7151809
194 4516325
195 3893651
196 3742069
197 7606565
198 3057775
199 7840999
200 3692093
201 5629225
202 5100505
203 6946955
204 3251375
205 6791341
206 5410595
207 5877695
208 4749889
209 7870289
210 2830525
211 9349411
212 5404553
213 6704549
214 6067975
215 7843559
216 3992711
217 8505145
218 6415745
219 7290091
220 4525507
221 9384125
222 4682075
223 11039839
224 5523875
225 6363505
226 7150645
227 11645555
228 4568797
229 11956549
230 5877695
231 6787655
232 6899857
233 12595049
234 5123225
235 10263115
236 7470263
237 9249181
238 6821875
239 13594799
240 4492379
241 13939441
242 8058605
243 9933859
244 8260657
245 10214837
246 6387895
247 13186471
248 8447483
249 10733081
250 7875505
251 15750251
252 5512075
253 14094829
254 10161275
255 8875375
256 9586981
257 16908545
258 7377605
259 14539075
260 7582373
261 11892245
262 11154655
263 18122279
264 6741637
265 14752969
266 9586025
267 13243931
268 10962175
269 19392749
270 6881635
271 19829071
272 10827125
273 11372545
274 12762925
275 15259811
276 8182217
277 21177205
278 13331495
279 14559655
280 8729935
281 22109081
282 9653425
283 22585099
284 13056227
285 12471581
286 12285595
287 19836095
288 9456125
289 22722337
290 11892245
291 17162035
292 14196493
293 25067909
294 9608015
295 20391799
296 14440505
297 16502297
298 16428745
299 23615531
300 8858503
301 22909405
302 17100755
303 19381919
304 15214159
305 22549361
306 11678125
307 28840195
308 13218065
309 20560261
310 14559655
311 29983511
312 11295443
313 30566329
314 19226225
315 15046475
316 18011563
317 31754525
318 13876555
319 28517839
320 15129497
321 23058305
322 17167525
323 30057875
324 13613077
325 25567429
326 21520895
327 24379831
328 19701613
329 29976425
330 11619545
331 36155131
332 20901263
333 24888925
334 23147875
335 29923775
336 13121305
337 38159185
338 22287725
339 27172451
340 17283625
341 34914341
342 16409975
343 34689943
344 22754087
345 22335241
346 25738945
347 41661515
348 16554947
349 42386749
350 18586475
351 27649183
352 22675975
353 43862369
354 19180405
355 35639971
356 25790813
357 25923125
358 28516495
359 46139399
360 14944465
361 44576281
362 29484905
363 30622699
364 22146535
365 38752589
366 21209795
367 49296175
368 27246899
369 33956705
370 24888925
371 43090355
372 20268193
373 51755989
374 28004375
375 29926919
376 29773195
377 47780921
378 20099825
379 54296299
380 24286763
381 38612845
382 34656955
383 56035199
384 22769087
385 36081745
386 35759045
387 39217795
388 33420805
389 58712549
390 19468255
391 53830375
392 29633141
393 42387689
394 38032825
395 49166699
396 22627535
397 62413165
398 39204995
399 36426895
400 29498941
401 64320401
402 28146125
403 58498099
404 37743737
405 37160021
406 34734775
407 59684135
408 25747375
409 68250649
410 33956705
411 48499115
412 40038403
413 59560205
414 29388475
415 57054799
416 37993025
417 50659681
418 39351445
419 73384499
420 20945885
421 74441221
422 46747055
423 51315575
424 42798217
425 58279625
426 33522745
427 65861995
428 44903015
429 46685261
430 39217795
431 79877231
432 31900807
433 80995249
434 42525725
435 45190531
436 47476513
437 75641861
438 36450455
439 84411799
440 35837123
441 51074185
442 46920625
443 86742059
444 34647355
445 70401949
446 55199195
447 62429231
448 44190115
449 90317249
450 31817525
451 81428851
452 52914773
453 64982869
454 58227775
455 60454055
456 36179933
457 95235145
458 59782745
459 63024875
460 43494943
461 97759661
462 33938275
463 99038479
464 55128209
465 55326689
466 62975245
467 101629475
468 37911865
469 87401125
470 51315575
471 73059655
472 59156407
473 94045049
474 46245905
475 81893899
476 50481875
477 73764845
478 67973995
479 109672799
480 35933275
481 99999265
482 69697205
483 65236595
484 59633677
485 91229765
486 49669295
487 115264135
488 65415473
489 81779401
490 51074185
491 118129691
492 47270423
493 108914125
494 65932355
495 61767055
496 67493371
497 104096945
498 53665405
499 124002499
500 58278737
501 87961925
502 78751255
503 127010519
504 43649675
505 103030201
506 70474145
507 84693355
508 75193435
509 131613149
510 44376875
511 113188255
512 76695845
513 88561873
514 84542725
515 109294019
516 54594277
517 123055765
518 72695375
519 97807991
520 60044197
521 141149321
522 59461225
523 142782139
524 82544447
525 70628605
526 90611395
527 133343375
528 53864069
529 141611185
530 73764845
531 101958995
532 70936585
533 136431989
534 66219655
535 122573095
536 86808575
537 108362681
538 96963745
539 122476907
540 50924099
541 158047741
542 99145355
543 112042639
544 86603125
545 129598049
546 56862725
547 163368115
548 94445645
549 112746805
550 76299055
551 153044951
552 64794313
553 143605705
554 105886025
555 94577915
556 98653063
557 172498445
558 72798275
559 157570111
560 69750095
561 106416625
562 110545405
563 178136579
564 71435345
565 144443029
566 112925495
567 108536695
568 103391203
569 183896249
570 62357905
571 185843371
572 90913403
573 131696429
574 99180475
575 146663039
576 75647485
577 191767105
578 113611685
579 135884371
580 88002613
581 166645205
582 85810175
583 176889559
584 112420877
585 103489145
586 125339545
587 201917435
588 71099311
589 187372669
590 101958995
591 144524735
592 115376185
593 208176209
594 82511485
595 137801875
596 121572713
597 148978981
598 118077655
599 214562999
600 70149767
601 216720601
602 114547025
603 149618875
604 126545587
605 162783821
606 96909595
607 223280095
608 121693775
609 131992145
610 112746805
611 206176835
612 86418125
613 229970629
614 144200975
615 129035479
616 104672785
617 234504425
618 102801305
619 236793499
620 107741447
621 158604653
622 149917555
623 205629455
624 90247891
625 196887601
626 152831645
627 149535491
628 142274065
629 227943125
630 75232375
631 250841431
632 142632107
633 177638809
634 158772625
635 205257755
636 102686507
637 205206973
638 142589195
639 178199855
640 121035673
641 262963841
642 115291525
643 265434259
644 127039685
645 149027621
646 150289375
647 270421415
648 107800853
649 244499689
650 127837145
651 161597755
652 159254623
653 278018669
654 121899155
655 225324031
656 157411181
657 193762945
658 149882125
659 285756899
660 85984633
661 288367861
662 180775655
663 178298375
664 165515407
665 193637705
666 124444625
667 274086811
668 171294275
669 209756941
670 149618875
671 270369071
672 104953625
673 304368289
674 190795925
675 171713827
676 164929165
677 309830405
678 135862255
679 266463175
680 136867625
681 221265545
682 174571705
683 318145499
684 121433815
685 257811085
686 173449715
687 227174431
688 181799719
689 296374001
690 111676205
691 329461891
692 190468193
693 180408725
694 208307575
695 269296199
696 131097283
697 310989625
698 211933745
699 239305931
700 137539915
701 343980701
702 138245915
703 320303215
704 181404167
705 194999185
706 219311845
707 300929795
708 141934997
709 355898149
710 178199855
711 245833495
712 204235357
713 335564009
714 129615625
715 248169019
716 211022063
717 258301181
718 230696995
719 371177999
720 119402705
721 319225105
722 222881405
723 264849379
724 218188297
725 296740949
726 153113495
727 383712055
728 175376615
729 268214185
730 193762945
731 359172875
732 156952483
733 393295549
734 246480875
735 194081903
736 217940275
737 358789025
738 169783525
739 403037299
740 184178045
741 250542949
742 215451775
743 409620359
744 160502177
745 331860649
746 258779945
747 285273995
748 207232375
749 358010525
750 149634595
751 423000751
752 237880715
753 299254769
754 238904605
755 345435251
756 148738705
757 433225045
758 271481495
759 267801751
760 192324907
761 440131961
762 193064225
763 378528955
764 256461467
765 235898125
766 280175995
767 409653071
768 182152639
769 454165249
770 180408725
771 321262355
772 264616933
773 461292389
774 196088975
775 363299431
776 264656645
777 276242425
778 293562745
779 436999259
780 144065087
781 427326781
782 269151875
783 320902223
784 236761717
785 388369745
786 211938445
787 486824035
788 281442905
789 344323301
790 245833495
791 421888055
792 179185615
793 452996569
794 312065825
795 280306411
796 290116963
797 505626365
798 182134475
799 469969375
800 235953725
801 352009745
802 321602005
803 464647379
804 208281325
805 346784005
806 292490495
807 368462231
808 298889593
809 528820649
810 185800105
811 532754011
812 257037335
813 376752349
814 298420675
815 434722079
816 205715375
817 504705841
818 341253245
819 302270275
820 251279617
821 552713621
822 242495575
823 556764439
824 317060867
825 289936409
826 297801025
827 564925355
828 217474715
829 569035549
830 285273995
831 402366895
832 303938113
833 467758625
834 253298405
835 467587075
836 291200693
837 392880037
838 366922495
839 589885799
840 165868765
841 574335721
842 372206105
843 420072539
844 345928207
845 450212045
846 256577875
847 475457695
848 341947529
849 429116881
850 291398125
851 573628115
852 248068313
853 619922869
854 329309975
855 331481495
856 355583335
857 628688345
858 233426305
859 633101899
860 290211683
861 376885805
862 399386155
863 641990879
864 255165575
865 519926689
866 404976245
867 431724403
868 314690365
869 589513589
870 225952655
871 601141975
872 375962657
873 456148825
874 378209305
875 464654795
876 269733367
877 673757005
878 422058995
879 476290271
880 286330051
881 683021681
882 255370925
883 687685699
884 347212625
885 387444181
886 433710295
887 697077335
888 274369595
889 599515225
890 352009745
891 445552331
892 408474043
893 660395885
894 312146155
895 576033199
896 353520035
897 448695089
898 451586245
899 678941219
900 235449685
901 675569125
902 407144255
903 435278695
904 419027797
905 595595081
906 324914345
907 745319995
908 430885535
909 515151005
910 302270275
911 755228111
912 289069021
913 684092689
914 476175725
915 428437859
916 442392313
917 658124645
918 315124375
919 775306999
920 344432927
921 547963705
922 488798305
923 715975259
924 251143235
925 621040285
926 495192395
927 546470095
928 440955025
929 800902049
930 276633445
931 657289363
932 466016813
933 569686709
934 508147375
935 565688375
936 300220985
937 821778985
938 437005625
939 580760251
940 379735255
941 832352141
942 365298275
943 782617999
944 472645559
945 406016465
946 470225245
947 848381315
948 342219697
949 778504981
950 409469495
951 603335975
952 399761875
953 864614969
954 368824225
955 700070491
956 503007563
957 541838941
958 548363995
959 753012575
960 287460443
961 858903361
962 499996325
963 612865475
964 515759317
965 722332709
966 326182975
967 903295975
968 472234253
969 571099625
970 456148825
971 914555771
972 367552783
973 786558205
974 576320675
975 485781151
976 522654001
977 931620305
978 408897005
979 844126339
980 377948969
981 647990245
982 590648455
983 948895799
984 374330647
985 768263065
986 544570625
987 569552075
988 487899427
989 903873101
990 308835275
991 972260191
992 539860475
993 686947489
994 520484725
995 791940899
996 397123997
997 990032965
998 620012495
999 671606695
1000 461504593