3 0
4 52
5 235
6 111
7 1498
8 2920
9 1719
10 4235
11 13156
12 6516
13 28015
14 19481
15 17610
16 70096
17 91273
18 19485
19 147592
20 183940
21 75537
22 138149
23 333730
24 133224
25 474925
26 280163
27 218916
28 765100
29 886327
30 170235
31 1171366
32 1337248
33 506715
34 860591
35 1941520
36 727452
37 2444923
38 1365245
39 1013454
40 3375880
41 3738421
42 688233
43 4550260
44 5002492
45 1829205
46 3003593
47 6562798
48 2385360
49 7788697
50 4231175
51 3059592
52 9939748
53 10747075
54 1933767
55 12508210
56 13465816
57 4825791
58 7772435
59 16670332
60 5951940
61 19103431
62 10207649
63 7264530
64 23240512
65 24758305
66 4391541
67 28015648
68 29759860
69 10528089
70 16745645
71 35483386
72 12521016
73 39732805
74 20997611
75 14784300
76 46808476
77 49364623
78 8670675
79 54789502
80 57663760
81 20216547
82 31874999
83 66967720
84 23435244
85 73766995
86 38677253
87 27023766
88 84920440
89 88905037
90 15504705
91 97293196
92 101703148
93 35420445
94 55485521
95 115835590
96 40286112
97 126042673
98 65696015
99 45636624
100 142599700
101 148465051
102 25751583
103 160736650
104 167150152
105 57917895
106 90275483
107 187545748
108 64913940
109 202143007
110 104876585
111 72525402
112 225616048
113 233876665
114 40393677
115 251076280
116 260023396
117 89735841
118 139316405
119 288303442
120 99407880
121 308397661
122 159414899
123 109841460
124 340485772
125 351718375
126 60537771
127 375014998
128 387088000
129 133150059
130 206053055
131 425060416
132 146105916
133 451882795
134 232880141
135 159984990
136 494471656
137 509315173
138 87415065
139 540002212
140 555855580
141 190685157
142 294303449
143 605514910
144 207594864
145 640421065
146 329214743
147 225605016
148 695582980
149 714738547
150 122381175
151 754233826
152 774584248
153 265114575
154 408258851
155 838111660
156 286710372
157 882581623
158 452734385
159 309599394
160 952575520
161 976806481
162 166916133
163 1026652240
164 1052278612
165 359460585
166 552483773
167 1132041898
168 386536920
169 1187680117
170 608127995
171 415114812
172 1274951548
173 1305083455
174 222624387
175 1366946350
176 1398689776
177 476994291
178 731915975
179 1497243352
180 510407820
181 1565778691
182 800457749
183 545546790
184 1672959832
185 1709880445
186 291234801
187 1785551548
188 1824315340
189 621235629
190 951866465
191 1944400246
192 661905216
193 2027685985
194 1035159071
195 704539680
196 2157595636
197 2202254923
198 374600655
199 2293649722
200 2340399400
201 795953367
202 1218019499
203 2484943300
204 844860084
205 2584957135
206 1318040633
207 895986666
208 2740600720
209 2794010857
210 474699645
211 2903169256
212 2958932548
213 1005165105
214 1536432581
215 3131049730
216 1063352232
217 3249893773
218 1655284355
219 1124029764
220 3434463340
221 3497698711
222 593633883
223 3626785030
224 3692651872
225 1253137275
226 1913536463
227 3895643248
228 1321710300
229 4035544027
230 2053445405
231 1393059822
232 4252418248
233 4326615445
234 733629897
235 4477918420
236 4555040956
237 1544385141
238 2356135145
239 4792394062
240 1624511760
241 4955702521
242 2519452199
243 1707716520
244 5208446692
245 5294804515
246 897038631
247 5470737298
248 5560329880
249 1883672799
250 2871405875
251 5835718876
252 1976582916
253 6024910375
254 3060606401
255 2072888370
256 6317276416
257 6417055873
258 1086335445
259 6620156032
260 6723495220
261 2276013177
262 3466899149
263 7040780890
264 2382998904
265 7258455205
266 3684582923
267 2493712716
268 7594381660
269 7708905967
270 1304120115
271 7941835486
272 8060260048
273 2726668035
274 4150538711
275 8423489800
276 2849083692
277 8672371123
278 4399429925
279 2975575734
280 9055983160
281 9186637741
282 1553116833
283 9452183020
284 9587093932
285 3241147965
286 4930621553
287 10000501798
288 3380410080
289 10283438737
290 5213568815
291 3524112432
292 10719048148
293 10867280635
294 1836174207
295 11168352490
296 11321212936
297 3825212391
298 5815817915
299 11789219572
300 3982799700
301 12109185151
302 6135794249
303 4145206650
304 12601290352
305 12768610585
306 2156265261
307 13108244248
308 13280579620
309 4484869569
310 6815171285
311 13807792306
312 4662323016
313 14167883965
314 7175274131
315 4844991060
316 14721169996
317 14909150023
318 2516487435
319 15290505142
320 15483903040
321 5226376587
322 7938098399
323 16075115680
324 5425299324
325 16478555275
326 8341549613
327 5629847166
328 17097893800
329 17308167877
330 2920062585
331 17734528516
332 17950638748
333 6056239365
334 9194389241
335 18610831870
336 6278296752
337 19060965673
338 9644535095
339 6506405304
340 19751414980
341 19985679571
342 3370336983
343 20460454210
344 20700988792
345 6981212655
346 10594207043
347 21435329548
348 7228132260
349 21935628247
350 11094518225
351 7481544642
352 22702433248
353 22962447025
354 3870781317
355 23489168560
356 23755901716
357 8008300041
358 12148088285
359 24569743882
360 8281871640
361 25123802581
362 12702159899
363 8562393180
364 25972394812
365 26259978655
366 4424990691
367 26842304398
368 27137072560
369 9144753939
370 13866942695
371 28035956536
372 9446829516
373 28647494755
374 14478494261
375 9756327750
376 29583492376
377 29900529373
378 5036684625
379 30542241052
380 30866942860
381 10398075597
382 15762053249
383 31856595670
384 10730569344
385 32529457345
386 16434928703
387 11070974016
388 33558665140
389 33907100587
390 5709707055
391 34612104346
392 34968700648
393 11776015095
394 17845076171
395 36055035940
396 12140903412
397 36793189423
398 18583243865
399 12514206474
400 37921598800
401 38303440201
402 6448026333
403 39075766600
404 39466280452
405 13286571345
406 20128040933
407 40655398498
408 13685892840
409 41462936557
410 20935593635
411 14094148452
412 42696725548
413 43114042615
414 7255735227
415 43957846630
416 44384363296
417 14937992091
418 22623350255
419 45682550992
420 15373847580
421 46563690811
422 23504505149
423 15819172110
424 47909224072
425 48364148725
426 8137050921
427 49283709748
428 49748376700
429 16738773909
430 25343780105
431 51162107566
432 17213326416
433 52121190745
434 26302878791
435 17697898440
436 53585019556
437 54079745923
438 9096315015
439 55079467762
440 55584494680
441 18697662207
442 28302479699
443 57120428860
444 19213136964
445 58161921415
446 29343988193
447 19739197266
448 59750783680
449 60287568097
450 10137993525
451 61371978976
452 61919637748
453 20823651225
454 31512971501
455 63584622010
456 21382335672
457 64713114373
458 32641480235
459 21952187244
460 66433934620
461 67015095631
462 11266676883
463 68188848190
464 68781472912
465 23125984035
466 34989151223
467 70582540648
468 23730227820
469 71802747667
470 36209375045
471 24346235862
472 73662637048
473 74290555405
474 12487079937
475 75558426700
476 76198413676
477 25614152541
478 38745287825
479 78142784902
480 26266367520
481 79459545841
482 40062065999
483 26930959440
484 81465802132
485 82142920795
486 13804041951
487 83509812298
488 84199620040
489 28297897479
490 42796023515
491 86294701396
492 29000557716
493 87712979935
494 44214319721
495 29716223130
496 89873087536
497 90601911673
498 15222526605
499 92072849272
500 92814998500
501 31187208417
502 47156373749
503 95068383250
504 31942850184
505 96593267485
506 48681276083
507 32712140916
508 98914897420
509 99697994407
510 16747621995
511 101278128406
512 102075202048
513 34292323755
514 51841727231
515 104494670080
516 35103545532
517 106131372523
518 53478448205
519 35929075614
520 108622382440
521 109462381861
522 18384540633
523 111156986980
524 112011630172
525 37623730725
526 56867845913
527 114605147998
528 38493193200
529 116359005577
530 58621722455
531 39377638872
532 119027439748
533 119927033395
534 20138619447
535 121741508770
536 122656428856
537 41192165391
538 62250864995
539 125432149612
540 42122591460
541 127308623671
542 64127358449
543 43068691170
544 130162712992
545 131124654865
546 22015319781
547 133064524048
548 134042490580
549 45008612649
550 68007292925
551 137008754026
552 46002787416
553 139013430325
554 70011989051
555 47013341820
556 142061592316
557 143088698623
558 24020227395
559 145159609582
560 146203454320
561 49084306227
562 74154011399
563 149368786840
564 50145077004
565 151507375555
566 76292620373
567 51222948966
568 154758214360
569 155853363517
570 26159052465
571 158061088636
572 159173705548
573 53430728685
574 80708275361
575 162546820150
576 54561004992
577 164825155873
578 82986631775
579 55709119584
580 168287462260
581 169453594891
582 28437629583
583 171804030970
584 172988376232
585 58059611415
586 87687713003
587 176578172548
588 59262364980
589 179002214287
590 90111775865
591 60483709482
592 182684965648
593 183925084585
594 30861917757
595 186424252840
596 187683344836
597 62982934641
598 95110325765
599 191498909122
600 64261199400
601 194074740301
602 97686178499
603 65558823300
604 197987100652
605 199304270935
606 33438000411
607 201958316998
608 203295236320
609 68212927419
610 102994488335
611 207345841456
612 69569799516
613 210079669915
614 105728338781
615 70946814510
616 214230989896
617 215628338773
618 36172085385
619 218443532692
620 219861422140
621 73762067637
622 111358948649
623 224156527630
624 75200705424
625 227054685625
626 114257129063
627 76660285416
628 231454502500
629 232935219427
630 39070504935
631 235917955666
632 237420020248
633 79643082015
634 120222827891
635 241969272220
636 81166706052
637 245038216423
638 123291794945
639 82712087154
640 249696254080
641 251263590721
642 42139715733
643 254420388160
644 256009895092
645 85868946105
646 129605620493
647 260823126298
648 87480839160
649 264069437797
650 132851955275
651 89115319692
652 268995606748
653 270652876975
654 45386298867
655 273990378910
656 275670657616
657 92452884291
658 139527194135
659 280757887432
660 94156391340
661 284188271731
662 142957602149
663 95883331830
664 289392669112
665 291143249005
666 48816959841
667 294668223148
668 296442665260
669 99408369789
670 150007789745
671 301814099686
672 101206898016
673 305435386705
674 153629100911
675 103029721200
676 310928296276
677 312775624123
678 52438528575
679 316494962602
680 318367021960
681 106749124647
682 161068021499
683 324033053620
684 108646143444
685 327852197695
686 164887190153
687 110568334266
688 333644089840
689 335591666137
690 56257959405
691 339512385496
692 341485578148
693 114489119745
694 172728876821
695 347456786290
696 116488160712
697 351480866173
698 176752981715
699 118513266324
700 357582397900
701 359633785351
702 60282331083
703 363763026550
704 365840930752
705 122642574795
706 185011716383
707 372128081248
708 124747231740
709 376364300107
710 189247960685
711 126878861502
712 382786315048
713 384945138565
714 64518846777
715 389290166980
716 391476423196
717 131223958341
718 197938274105
719 398090468542
720 133437887280
721 402546153961
722 202393985399
723 135679712760
724 409299682372
725 411569629075
726 68974834071
727 416137834498
728 418436145400
729 140247987759
730 211530657155
731 425388224716
732 142574906916
733 430070828695
734 216213287441
735 144930661890
736 437167087456
737 439551906673
738 73657744965
739 444350803312
740 446764933780
741 149729629257
742 225811345949
743 454066372810
744 152173319064
745 458983471765
746 230728471643
747 154646799516
748 466433864380
749 468937367647
750 78575155875
751 473974594126
752 476508371248
753 159684097875
754 240803194151
755 484170682360
756 162248400972
757 489329977123
758 245962516085
759 164843465094
760 497146093720
761 499772154781
762 83734767633
763 505055474140
764 507712787212
765 170126857485
766 256529428673
767 515747669398
768 172815678720
769 521156985217
770 261938772095
771 175536246912
772 529350602548
773 532103157355
774 89144405487
775 537640457050
776 540425257576
777 181073620791
778 273013649675
779 548844596452
780 183890927220
781 554511882991
782 278680964249
783 186740982090
784 563094964432
785 565978011145
786 94812019101
787 571777303048
788 574693604740
789 192540349329
790 290279830565
791 583509472546
792 195490170216
793 589442803885
794 296213190371
795 198473756580
796 598427499436
797 601445098423
798 100745682555
799 607514518822
800 610566397600
801 204543253467
802 308352317999
803 619791053200
804 207629680284
805 625998627835
806 314559921533
807 210750905166
808 635397274120
809 638553547957
810 106953594345
811 644901357556
812 648092951548
813 217098792405
814 327255831881
815 657738840430
816 220325978832
817 664228981273
818 333746002055
819 223589011464
820 674054101540
821 677353235011
822 113444077383
823 683987818930
824 687323328472
825 230223674175
826 347015465363
827 697403082748
828 233595836100
829 704184237127
830 353796649505
831 237004907922
832 714448541248
833 717894781345
834 120225578997
835 724824649120
836 728308336756
837 243934855641
838 367656684845
839 738834775162
840 247456271160
841 745915514821
842 374737454699
843 251015675820
844 756631899292
845 760229555215
846 127306670931
847 767463340798
848 771099531280
849 258249542499
850 389205329975
851 782085659176
852 261924551916
853 789474680275
854 396594381701
855 265638645270
856 800656228216
857 804409671373
858 134696049345
859 811956133132
860 815749213420
861 273185189277
862 411687613649
863 827208222790
864 277018195104
865 834914345905
866 419393767823
867 280891395216
868 846574327060
869 850487991067
870 142402534815
871 858356011786
872 862310431048
873 288759499335
874 435130122011
875 874255700500
876 292754966292
877 882287870623
878 443162323625
879 296791753434
880 894439741360
881 898518122041
882 150435072333
883 906716708920
884 910836978532
885 304990424865
886 459559814453
887 923282073298
888 309152879880
889 931649359837
890 467927132915
891 313357796532
892 944306763148
893 948554418535
894 158802731307
895 957092703190
896 961383396736
897 321896166891
898 485004023615
899 974342068672
900 326230199100
901 983053665451
902 493715652749
903 330607849950
904 996230430952
905 1000651981285
906 167514705561
907 1009539219748
908 1014004973020
909 339495175269
910 511490455385
911 1027491160606
912 344005436016
913 1036556385865
914 520555713431
915 348560487960
916 1050266529796
917 1054866657523
918 176580313335
919 1064112230242
920 1068757741240
921 357806148687
922 539047188899
923 1082785569580
924 362497351524
925 1092213865975
926 548475518513
927 367234533666
928 1106471591200
929 1111255040977
930 186008997285
931 1120868452816
932 1125698481748
933 376848034665
934 567702676541
935 1140282262570
936 381724955352
937 1150083197173
938 577503644795
939 386649059004
940 1164902893180
941 1169874471871
942 195810324483
943 1179865352110
944 1184884721392
945 396640029555
946 597485743943
947 1200038953048
948 401707506060
949 1210222217347
950 607669042325
951 406823384742
952 1225618460248
953 1230783036925
954 205993986417
955 1241161139260
956 1246374733516
957 417201578541
958 628425589985
959 1262114100982
960 422464511040
961 1272689510881
962 639001034399
963 427777080480
964 1288677063412
965 1294039569355
966 216569798991
967 1304814771898
968 1310227537960
969 438552375639
970 660551786795
971 1326566912836
972 444015726516
973 1337544408655
974 671529317561
975 449529964650
976 1354138220176
977 1359703648873
978 227547702525
979 1370885954152
980 1376502901060
981 460712363697
982 693894279749
983 1393457341570
984 466381157544
985 1404846988045
986 705283961603
987 472102104516
988 1422062194540
989 1427835601687
990 238937761755
991 1439435136646
992 1445261335648
993 483701734395
994 728483387471
995 1462846086640
996 489581058012
997 1474658072923
998 740295409565
999 495513816174
1000 1492509997000