1 1
2 3
3 10
4 19
5 51
6 48
7 148
8 147
9 253
10 253
11 606
12 352
13 1015
14 738
15 960
16 1171
17 2313
18 1263
19 3250
20 1869
21 2803
22 3028
23 5820
24 2784
25 6301
26 5073
27 6814
28 5458
29 11775
30 4798
31 14416
32 9363
33 11505
34 11563
35 14898
36 9343
37 24643
38 16248
39 19276
40 14797
41 33621
42 14013
43 38830
44 22404
45 25503
46 29098
47 50808
48 22240
49 50569
50 31503
51 43938
52 37537
53 73035
54 34068
55 61156
56 43218
57 61741
58 58873
59 100950
60 35502
61 111631
62 72078
63 74488
64 74899
65 102465
66 57523
67 148138
68 85563
69 110571
70 74488
71 176436
72 73983
73 191845
74 123213
75 119710
76 120232
77 178623
78 96378
79 243400
80 118221
81 183961
82 168103
83 282450
84 103693
85 233563
86 194148
87 223716
88 177412
89 348525
90 127513
91 299278
92 215322
93 273895
94 254038
95 328200
96 177888
97 451633
98 252843
99 305778
100 233119
101 510051
102 219688
103 541060
104 297249
105 283053
106 365173
107 606798
108 252100
109 641575
110 305778
111 468208
112 345298
113 715065
114 308703
115 587770
116 435657
117 512323
118 504748
119 682188
120 281134
121 805861
122 558153
123 638790
124 533374
125 787551
126 372438
127 1016128
128 599187
129 737761
130 512323
131 1115466
132 425667
133 958603
134 740688
135 688164
136 677563
137 1276293
138 552853
139 1333150
140 551208
141 965343
142 882178
143 1228560
144 591103
145 1189225
146 959223
147 960802
148 911773
149 1642875
150 598548
151 1710076
152 952104
153 1167813
154 893113
155 1455966
156 713194
157 1922623
158 1216998
159 1387656
160 945613
161 1716753
162 919803
163 2152090
164 1243959
165 1161955
166 1412248
167 2314788
168 821133
169 2228773
170 1167813
171 1640998
172 1436692
173 2573895
174 1118578
175 1858648
176 1417476
177 1918041
178 1742623
179 2851650
180 943593
181 2948491
182 1496388
183 2120980
184 1705114
185 2488893
186 1369473
187 2800438
188 1879878
189 2009983
190 1640998
191 3465696
192 1423072
193 3575905
194 2258163
195 1946826
196 1871035
197 3803283
198 1528888
199 3920500
200 1846047
201 2814613
202 2550253
203 3473478
204 1625688
205 3395671
206 2705298
207 2938848
208 2374945
209 3935145
210 1415263
211 4674706
212 2702277
213 3352275
214 3033988
215 3921780
216 1996356
217 4252573
218 3207873
219 3645046
220 2262754
221 4692063
222 2341038
223 5519920
224 2761938
225 3181753
226 3575323
227 5822778
228 2284399
229 5978275
230 2938848
231 3393828
232 3449929
233 6297525
234 2561613
235 5131558
236 3735132
237 4624591
238 3410938
239 6797400
240 2246190
241 6969721
242 4029303
243 4966930
244 4130329
245 5107419
246 3193948
247 6593236
248 4223742
249 5366541
250 3937753
251 7875126
252 2756038
253 7047415
254 5080638
255 4437688
256 4793491
257 8454273
258 3688803
259 7269538
260 3791187
261 5946123
262 5577328
263 9061140
264 3370819
265 7376485
266 4793013
267 6621966
268 5481088
269 9696375
270 3440818
271 9914536
272 5413563
273 5686273
274 6381463
275 7629906
276 4091109
277 10588603
278 6665748
279 7279828
280 4364968
281 11054541
282 4826713
283 11292550
284 6528114
285 6235791
286 6142798
287 9918048
288 4728063
289 11361169
290 5946123
291 8581018
292 7098247
293 12533955
294 4804008
295 10195900
296 7220253
297 8251149
298 8214373
299 11807766
300 4429252
301 11454703
302 8550378
303 9690960
304 7607080
305 11274681
306 5839063
307 14420098
308 6609033
309 10280131
310 7279828
311 14991756
312 5647722
313 15283165
314 9613113
315 7523238
316 9005782
317 15877263
318 6938278
319 14258920
320 7564749
321 11529153
322 8583763
323 15028938
324 6806539
325 12783715
326 10760448
327 12189916
328 9850807
329 14988213
330 5809773
331 18077566
332 10450632
333 12444463
334 11573938
335 14961888
336 6560653
337 19079593
338 11143863
339 13586226
340 8641813
341 17457171
342 8204988
343 17344972
344 11377044
345 11167621
346 12869473
347 20830758
348 8277474
349 21193375
350 9293238
351 13824592
352 11337988
353 21931185
354 9590203
355 17819986
356 12895407
357 12961563
358 14258248
359 23069700
360 7472233
361 22288141
362 14742453
363 15311350
364 11073268
365 19376295
366 10604898
367 24648088
368 13623450
369 16978353
370 12444463
371 21545178
372 10134097
373 25877995
374 14002188
375 14963460
376 14886598
377 23890461
378 10049913
379 27148150
380 12143382
381 19306423
382 17328478
383 28017600
384 11384544
385 18040873
386 17879523
387 19608898
388 16710403
389 29356275
390 9734128
391 26915188
392 14816571
393 21193845
394 19016413
395 24583350
396 11313768
397 31206583
398 19602498
399 18213448
400 14749471
401 32160201
402 14073063
403 29249050
404 18871869
405 18580011
406 17367388
407 29842068
408 12873688
409 34125325
410 16978353
411 24249558
412 20019202
413 29780103
414 14694238
415 28527400
416 18996513
417 25329841
418 19675723
419 36692250
420 10472943
421 37220611
422 23373528
423 25657788
424 21399109
425 29139813
426 16761373
427 32930998
428 22451508
429 23342631
430 19608898
431 39938616
432 15950404
433 40497625
434 21262863
435 22595266
436 23738257
437 37820931
438 18225228
439 42205900
440 17918562
441 25537093
442 23460313
443 43371030
444 17323678
445 35200975
446 27599598
447 31214616
448 22095058
449 45158625
450 15908763
451 40714426
452 26457387
453 32491435
454 29113888
455 30227028
456 18089967
457 47617573
458 29891373
459 31512438
460 21747472
461 48879831
462 16969138
463 49519240
464 27564105
465 27663345
466 31487623
467 50814738
468 18955933
469 43700563
470 25657788
471 36529828
472 29578204
473 47022525
474 23122953
475 40946950
476 25240938
477 36882423
478 33986998
479 54836400
480 17966638
481 49999633
482 34848603
483 32618298
484 29816839
485 45614883
486 24834648
487 57632068
488 32707737
489 40889701
490 25537093
491 59064846
492 23635212
493 54457063
494 32966178
495 30883528
496 33746686
497 52048473
498 26832703
499 62001250
500 29139369
501 43980963
502 39375628
503 63505260
504 21824838
505 51515101
506 35237073
507 42346678
508 37596718
509 65806575
510 22188438
511 56594128
512 38347923
513 44280937
514 42271363
515 54647010
516 27297139
517 61527883
518 36347688
519 48903996
520 30022099
521 70574661
522 29730613
523 71391070
524 41272224
525 35314303
526 45305698
527 66671688
528 26932035
529 70805593
530 36882423
531 50979498
532 35468293
533 68215995
534 33109828
535 61286548
536 43404288
537 54181341
538 48481873
539 61238454
540 25462050
541 79023871
542 49572678
543 56021320
544 43301563
545 64799025
546 28431363
547 81684058
548 47222823
549 56373403
550 38149528
551 76522476
552 32397157
553 71802853
554 52943013
555 47288958
556 49326532
557 86249223
558 36399138
559 78785056
560 34875048
561 53208313
562 55272703
563 89068290
564 35717673
565 72221515
566 56462748
567 54268348
568 51695602
569 91948125
570 31178953
571 92921686
572 45456702
573 65848215
574 49590238
575 73331520
576 37823743
577 95883553
578 56805843
579 67942186
580 44001307
581 83322603
582 42905088
583 88444780
584 56210439
585 51744573
586 62669773
587 100958718
588 35549656
589 93686335
590 50979498
591 72262368
592 57688093
593 104088105
594 41255743
595 68900938
596 60786357
597 74489491
598 59038828
599 107281500
600 35074884
601 108360301
602 57273513
603 74809438
604 63272794
605 81391911
606 48454798
607 111640048
608 60846888
609 65996073
610 56373403
611 103088418
612 43209063
613 114985315
614 72100488
615 64517740
616 52336393
617 117252213
618 51400653
619 118396750
620 53870724
621 79302327
622 74958778
623 102814728
624 45123946
625 98443801
626 76415823
627 74767746
628 71137033
629 113971563
630 37616188
631 125420716
632 71316054
633 88819405
634 79386313
635 102628878
636 51343254
637 102603487
638 71294598
639 89099928
640 60517837
641 131481921
642 57645763
643 132717130
644 63519843
645 74513811
646 75144688
647 135210708
648 53900427
649 122249845
650 63918573
651 80798878
652 79627312
653 139009335
654 60949578
655 112662016
656 78705591
657 96881473
658 74941063
659 142878450
660 42992317
661 144183931
662 90387828
663 89149188
664 82757704
665 96818853
666 62222313
667 137043406
668 85647138
669 104878471
670 74809438
671 135184536
672 52476813
673 152184145
674 95397963
675 85856914
676 82464583
677 154915203
678 67931128
679 133231588
680 68433813
681 110632773
682 87285853
683 159072750
684 60716908
685 128905543
686 86724858
687 113587216
688 90899860
689 148187001
690 55838103
691 164730946
692 95234097
693 90204363
694 104153788
695 134648100
696 65548642
697 155494813
698 105966873
699 119652966
700 68769958
701 171990351
702 69122958
703 160151608
704 90702084
705 97499593
706 109655923
707 150464898
708 70967499
709 177949075
710 89099928
711 122916748
712 102117679
713 167782005
714 64807813
715 124084510
716 105511032
717 129150591
718 115348498
719 185589000
720 59701353
721 159612553
722 111440703
723 132424690
724 109094149
725 148370475
726 76556748
727 191856028
728 87688308
729 134107093
730 96881473
731 179586438
732 78476242
733 196647775
734 123240438
735 97040952
736 108970138
737 179394513
738 84891763
739 201518650
740 92089023
741 125271475
742 107725888
743 204810180
744 80251089
745 165930325
746 129389973
747 142636998
748 103616188
749 179005263
750 74817298
751 211500376
752 118940358
753 149627385
754 119452303
755 172717626
756 74369353
757 216612523
758 135740748
759 133900876
760 96162454
761 220065981
762 96532113
763 189264478
764 128230734
765 117949063
766 140087998
767 204826536
768 91076320
769 227082625
770 90204363
771 160631178
772 132308467
773 230646195
774 98044488
775 181649716
776 132328323
777 138121213
778 146781373
779 218499630
780 72032544
781 213663391
782 134575938
783 160451112
784 118380859
785 194184873
786 105969223
787 243412018
788 140721453
789 172161651
790 122916748
791 210944028
792 89592808
793 226498285
794 156032913
795 140153206
796 145058482
797 252813183
798 91067238
799 234984688
800 117976863
801 176004873
802 160801003
803 232323690
804 104140663
805 173392003
806 146245248
807 184231116
808 149444797
809 264410325
810 92900053
811 266377006
812 128518668
813 188376175
814 149210338
815 217361040
816 102857688
817 252352921
818 170626623
819 151135138
820 125639809
821 276356811
822 121247788
823 278382220
824 158530434
825 144968205
826 148900513
827 282462678
828 108737358
829 284517775
830 142636998
831 201183448
832 151969057
833 233879313
834 126649203
835 233793538
836 145600347
837 196440019
838 183461248
839 294942900
840 82934383
841 287167861
842 186103053
843 210036270
844 172964104
845 225106023
846 128288938
847 237728848
848 170973765
849 214558441
850 145699063
851 286814058
852 124034157
853 309961435
854 164654988
855 165740748
856 177791668
857 314344173
858 116713153
859 316550950
860 145105842
861 188442903
862 199693078
863 320995440
864 127582788
865 259963345
866 202488123
867 215862202
868 157345183
869 294756795
870 112976328
871 300570988
872 187981329
873 228074413
874 189104653
875 232327398
876 134866684
877 336878503
878 211029498
879 238145136
880 143165026
881 341510841
882 127685463
883 343842850
884 173606313
885 193722091
886 216855148
887 348538668
888 137184798
889 299757613
890 176004873
891 222776166
892 204237022
893 330197943
894 156073078
895 288016600
896 176760018
897 224347545
898 225793123
899 339470610
900 117724843
901 337784563
902 203572128
903 217639348
904 209513899
905 297797541
906 162457173
907 372659998
908 215442768
909 257575503
910 151135138
911 377614056
912 144534511
913 342046345
914 238087863
915 214218930
916 221196157
917 329062323
918 157562188
919 387653500
920 172216464
921 273981853
922 244399153
923 357987630
924 125571618
925 310520143
926 247596198
927 273235048
928 220477513
929 400451025
930 138316723
931 328644682
932 233008407
933 284843355
934 254073688
935 282844188
936 150110493
937 410889493
938 218502813
939 290380126
940 189867628
941 416176071
942 182649138
943 391309000
944 236322780
945 203008233
946 235112623
947 424190658
948 171109849
949 389252491
950 204734748
951 301667988
952 199880938
953 432307485
954 184412113
955 350035246
956 251503782
957 270919471
958 274181998
959 376506288
960 143730222
961 429451681
962 249998163
963 306432738
964 257879659
965 361166355
966 163091488
967 451647988
968 236117127
969 285549813
970 228074413
971 457277886
972 183776392
973 393279103
974 288160338
975 242890576
976 261327001
977 465810153
978 204448503
979 422063170
980 188974485
981 323995123
982 295324228
983 474447900
984 187165324
985 384131533
986 272285313
987 284776038
988 243949714
989 451936551
990 154417638
991 486130096
992 269930238
993 343473745
994 260242363
995 395970450
996 198561999
997 495016483
998 310006248
999 335803348
1000 230752297