1 0
2 1
3 2
4 6
5 13
6 23
7 36
8 62
9 78
10 123
11 150
12 238
13 255
14 355
15 427
16 567
17 580
18 864
19 810
20 1202
21 1232
22 1471
23 1452
24 2310
25 1960
26 2479
27 2712
28 3414
29 2947
30 4649
31 3600
32 5126
33 5022
34 5673
35 5845
36 8457
37 6165
38 7975
39 8405
40 11062
41 8410
42 13133
43 9702
44 13726
45 14475
46 14323
47 12696
48 20983
49 15225
50 20315
51 19126
52 22890
53 18265
54 28266
55 23183
56 30710
57 26858
58 29079
59 25230
60 44810
61 27915
62 35611
63 40020
64 44058
65 38524
66 52353
67 37026
68 51830
69 48072
70 61221
71 44100
72 76320
73 47970
74 61003
75 68950
76 72654
77 63276
78 87053
79 60840
80 97159
81 81360
82 83301
83 70602
84 123718
85 86801
86 96223
87 97225
88 120422
89 87142
90 152322
91 104655
92 129718
93 119012
94 125995
95 121459
96 181542
97 112920
98 155344
99 156198
100 187180
101 127525
102 196511
103 135252
104 199334
105 207877
106 181299
107 151686
108 261177
109 160407
110 239153
111 203411
112 265143
113 178780
114 275225
115 216317
116 261722
117 258189
118 250735
119 234616
120 398110
121 231440
122 277351
123 277492
124 320166
125 278145
126 415998
127 254016
128 369108
129 320462
130 395433
131 278850
132 481918
133 327816
134 368215
135 436665
136 447262
137 319090
138 490557
139 333270
140 564626
141 419292
142 438691
143 401625
144 656649
145 435392
146 477109
147 520793
148 546450
149 410737
150 712825
151 427500
152 625094
153 578226
154 648325
155 532273
156 796066
157 480675
158 605515
159 602695
160 822630
161 582222
162 831969
163 538002
164 744926
165 804427
166 702823
167 578676
168 1082862
169 629772
170 885923
171 807594
172 859998
173 643495
174 987989
175 846280
176 1021047
177 832998
178 867549
179 712890
180 1399749
181 737145
182 1068649
183 921137
184 1110710
185 907186
186 1208213
187 895370
188 1124614
189 1180452
190 1237497
191 866400
192 1522074
193 894000
194 1124593
195 1326334
196 1402611
197 950845
198 1602834
199 980100
200 1617490
201 1222322
202 1270251
203 1168483
204 1781534
205 1235783
206 1347523
207 1433532
208 1681191
209 1248630
210 2151959
211 1168650
212 1615490
213 1455792
214 1511455
215 1426207
216 2258184
217 1427706
218 1598239
219 1582940
220 2171642
221 1470595
222 2059961
223 1379952
224 2220134
225 2088390
226 1781529
227 1455666
228 2487694
229 1494597
230 2197109
231 2170962
232 2230150
233 1574410
234 2639430
235 1864025
236 2231614
237 2008268
238 2384811
239 1699320
240 3388039
241 1742460
242 2334376
243 2308806
244 2467386
245 2330398
246 2806763
247 2049501
248 2725142
249 2330442
250 2815565
251 1968750
252 3782841
253 2211172
254 2532475
255 2960863
256 3033060
257 2113600
258 3239777
259 2429181
260 3574358
261 2875377
262 2780311
263 2265252
264 4154750
265 2675894
266 3326845
267 2875600
268 3272814
269 2424127
270 4476372
271 2478600
272 3746167
273 3571079
274 3181653
275 3226410
276 4414054
277 2647185
278 3323455
279 3512688
280 4872526
281 2763670
282 4235013
283 2823102
284 3897046
285 4130887
286 4074709
287 3306406
288 5482410
289 3135208
290 4407953
291 3726266
292 4236990
293 3133525
294 5305874
295 3694439
296 4637942
297 4501722
298 4096419
299 3626295
300 6447860
301 3814812
302 4264051
303 4208227
304 5223159
305 4084168
306 5882280
307 3604986
308 5843734
309 4464032
310 5385213
311 3747900
312 6833358
313 3820830
314 4794583
315 6287277
316 5373894
317 3969355
318 6080513
319 4424717
320 6808922
321 5006382
322 5894353
323 4548190
324 7478370
325 5297095
326 5367223
327 5293325
328 6313582
329 4982802
330 8233499
331 4519350
332 6234958
333 5974611
334 5773315
335 5415115
336 9125719
337 4769940
338 6336967
339 5899630
340 7960610
341 5402400
342 8201898
343 5643393
344 7284710
345 7320157
346 6420159
347 5207646
348 8850002
349 5298387
350 8616245
351 7391235
352 8452006
353 5482840
354 8396625
355 6446453
356 7691822
357 7947316
358 7113415
359 5767380
360 12040536
361 6096834
362 7355251
363 7756892
364 9599850
365 7008079
366 9282533
367 6161976
368 9246903
369 8130648
370 9160773
371 7147345
372 10810678
373 6469545
374 9055943
375 9367195
376 9515990
377 7250386
378 12031332
379 6786990
380 11097194
381 8383412
382 8646331
383 7004352
384 12515668
385 9693905
386 8921569
387 9380022
388 9964710
389 7339117
390 13530623
391 8038016
392 11945948
393 9202962
394 9489243
395 8885929
396 14418897
397 7801695
398 9781795
399 11075894
400 13523035
401 8040100
402 12309353
403 8850315
404 11252306
405 12396141
406 11800689
407 9176055
408 15204454
409 8531382
410 12467423
411 10529836
412 11935638
413 9862356
414 14521326
415 10307987
416 13870118
417 10998878
418 12615025
419 9173010
420 19426130
421 9305205
422 11664871
423 12250200
424 13651414
425 11757740
426 14654733
427 10900491
428 13384414
429 13561725
430 14383569
431 9984600
432 18883497
433 10124460
434 14409865
435 14657650
436 14150922
437 11186688
438 15931643
439 10551420
440 18549502
441 15386091
442 14850519
443 10842702
444 18382954
445 12713747
446 13775323
447 13554175
448 18251418
449 11289712
450 21250350
451 12478760
452 15770390
453 14108552
454 14531575
455 15909664
456 21188382
457 11904450
458 14919979
459 16407948
460 19640690
461 12220015
462 22099923
463 12379752
464 18498151
465 17899177
466 15717189
467 12703626
468 23669853
469 14446512
470 18785741
471 15862121
472 18838694
473 14392122
474 20202725
475 16371070
476 21326342
477 17568759
478 16965355
479 13709040
480 28078598
481 15024900
482 17395801
483 19595136
484 20775821
485 16466341
486 23315895
487 14407956
488 20822342
489 17755202
490 23614962
491 14766150
492 25013798
493 16052231
494 20677981
495 23896695
496 22583607
497 17193366
498 23437017
499 15500250
500 25111240
501 19097472
502 19656751
503 15876252
504 32320440
505 18591938
506 22302453
507 21017906
508 22403814
509 16451707
510 30072881
511 18688590
512 24652872
513 22847142
514 21103233
515 19719877
516 28856254
517 18786136
518 24482101
519 21235165
520 30439966
521 17643730
522 29051214
523 17847702
524 24592366
525 28687000
526 22618723
527 19588900
528 34665303
529 19106813
530 26943533
531 24238974
532 29703270
533 20427385
534 28908419
535 22111295
536 27597830
537 23526618
538 24205359
539 23629725
540 40154469
541 19756035
542 24750091
543 24325607
544 30769542
545 23376532
546 36262379
547 20420946
548 28135550
549 26789433
550 32660865
551 22330705
552 37481774
553 23689026
554 26433763
555 30413308
556 29387934
557 21562375
558 35467974
559 23556585
560 40673479
561 30084706
562 27597501
563 22267002
564 37682518
565 26049449
566 28191823
567 33164028
568 32846582
569 22987102
570 41892179
571 23230350
572 36362770
573 28592532
574 33298455
575 28923600
576 44965278
577 23970960
578 31469465
579 29501810
580 39279686
581 27474792
582 37443911
583 26925035
584 35703854
585 39196362
586 31292619
587 25239606
588 47410699
589 27248220
590 37174817
591 31377691
592 38351367
593 26022100
594 45603456
595 35298857
596 36210722
597 32344688
598 36534073
599 26820300
600 54905370
601 27090150
602 38406373
603 35500290
604 37690806
605 34355453
606 42278873
607 27909936
608 42834470
609 39172651
610 41087073
611 30742515
612 52532025
613 28746405
614 36003655
615 41367517
616 49668110
617 29313130
618 44845037
619 29599110
620 47951522
621 40367388
622 37431571
623 33877858
624 56849575
625 36095600
626 38159629
627 41880888
628 42372570
629 33232153
630 63942360
631 31355100
632 45259094
633 38566922
634 39643623
635 36996385
636 54036506
637 38702160
638 44553629
639 42247668
640 55560532
641 32870560
642 50284833
643 33179202
644 52500958
645 47714107
646 45801903
647 33802596
648 63440694
649 37128850
650 53530265
651 47816372
652 47426478
653 34752415
654 53162429
655 40607723
656 52149847
657 45920544
658 50137273
659 35719530
660 73708010
661 36046065
662 45139711
663 49288969
664 52493510
665 49142173
666 60233490
667 39399755
668 51009814
669 45539972
670 54449001
671 41029365
672 75182790
673 38046120
674 47642953
675 59141940
676 56228328
677 38728885
678 59242703
679 43864476
680 67525654
681 48038562
682 54375181
683 39768102
684 73141089
685 46454111
686 56732326
687 49321475
688 60143223
689 44051080
690 74062919
691 41182650
692 56716490
693 63934410
694 52017295
695 48520399
696 74921518
697 45165470
698 52923319
699 51955300
700 76932220
701 42997675
702 74740776
703 46214235
704 68991898
705 62290177
706 54766449
707 49520461
708 74546014
709 44487357
710 64799333
711 58202664
712 64729870
713 48068562
714 80430773
715 60150674
716 62833294
717 56079228
718 57610435
719 46397160
720 100253145
721 52522182
722 61153552
723 57500942
724 64966146
725 57742475
726 78212178
727 47963916
728 81409406
729 63651366
730 70433583
731 52076506
732 82387378
733 49162035
734 61553515
735 78437170
736 75654502
737 54349566
738 81906324
739 50379570
740 81417470
741 68592473
742 71867709
743 51202452
744 91450830
745 59777102
746 64626259
747 67501002
748 80569550
749 58884732
750 94604515
751 52875000
752 78499383
753 64970502
754 72938181
755 62218813
756 107434545
757 54153225
758 67799215
759 73969242
760 94001374
761 55016590
762 84145973
763 62250183
764 76355686
765 86895471
766 69971323
767 60733041
768 101724132
769 56770752
770 98163311
771 69748546
772 78782790
773 57661645
774 94461426
775 70459060
776 83814782
777 81168461
778 73315899
779 62801500
780 120836798
781 64665100
782 80854331
783 80592375
784 98886333
785 69942496
786 92361513
787 60852906
788 83789810
789 74755152
790 89274477
791 69360880
792 122341800
793 67109850
794 77938543
795 89291824
796 86370774
797 63203395
798 111961307
799 67944236
800 110898190
801 83227332
802 80321001
803 70279440
804 109169518
805 86801147
806 89002369
807 79995925
808 94623862
809 66102682
810 125326971
811 66594150
812 104856218
813 81795692
814 92263873
815 78279547
816 126002743
817 72407718
818 85230589
819 104755623
820 110701322
821 69089305
822 105661211
823 69595452
824 100360310
825 108430950
826 99113365
827 70615566
828 129210585
829 71129547
830 103538489
831 87356831
832 112984026
833 85633597
834 110362625
835 84190565
836 112113694
837 98343192
838 91643575
839 73735620
840 165147430
841 76401892
842 92963851
843 91200832
844 102978126
845 92890681
846 123293238
847 91614446
848 112497991
849 93164342
850 118549315
851 81496101
852 129913798
853 77490465
854 109528705
855 120939051
856 112519910
857 78586150
858 137040783
859 79137630
860 127664570
861 110349562
862 99754411
863 80248752
864 154852170
865 93604004
866 101151289
867 104166106
868 127963374
869 89052360
870 147955655
871 88883445
872 118951910
873 107753766
874 112463725
875 110829045
876 141205126
877 84219735
878 105419155
879 103406035
880 153789959
881 85377820
882 155374821
883 85960602
884 131922650
885 123147187
886 108330223
887 87134556
888 155227614
889 98479242
890 127663703
891 125113230
892 121588518
893 94461396
894 135971249
895 103693379
896 148328532
897 121086879
898 112796769
899 95818207
900 189447195
901 97325405
902 125407571
903 127252706
904 132541534
905 107211478
906 141526973
907 93164886
908 128256814
909 121644003
910 160825803
911 94403400
912 175353943
913 103262422
914 118940533
915 136089562
916 131680722
917 108083856
918 165518034
919 96913260
920 166021390
921 118966682
922 122094351
923 105744495
924 197038318
925 119507965
926 123691723
927 129015492
928 150987174
929 100112872
930 180571199
931 119101857
932 138709790
933 123682872
934 126928615
935 133163011
936 200429640
937 102722490
938 145098253
939 126087080
940 166617986
941 104044135
942 159098261
943 110725742
944 155119479
945 177680217
946 144604153
947 106047546
948 178964374
949 114921345
950 164933705
951 130988401
952 180307030
953 108076990
954 176694810
955 125996993
956 149715334
957 147621505
958 136977115
959 123631006
960 229230554
961 113842695
962 150962809
963 144640470
964 153509526
965 130000189
966 197726583
967 112911876
968 175154232
969 151762798
970 165289323
971 114319350
972 206989146
973 129126636
974 143962435
975 177565945
976 171411687
977 116452660
978 178066697
979 127292612
980 210031535
981 152905317
982 147542431
983 118611852
984 211026550
985 138258266
986 161282495
987 166065372
988 183522306
989 127652052
990 241713852
991 121532400
992 184225766
993 149140862
994 172645345
995 142514869
996 207549454
997 123754245
998 154879495
999 166807713