1 -1
2 2084
3 7081
4 10847
5 25963
6 22421
7 202891
8 142679
9 252953
10 188501
11 257479
12 604328
13 667827
14 57217
15 115497
16 231930
17 203331
18 283651
19 426851
20 153521
21 231299
22 142267
23 236487
24 149872
25 204527
26 215033
27 285983
28 188082
29 153461
30 128802
31 213853
32 202259
33 94967
34 224778
35 182015
36 83944
37 157415
38 209090
39 148439
40 113026
41 336115
42 380293
43 68473
44 114634
45 555495
46 223963
47 469453
48 122230
49 163701
50 377857
51 358689
52 119448
53 479843
54 138679
55 257129
56 113332
57 517777
58 157689
59 249759
60 268921
61 282815
62 334308
63 269579
64 237907
65 447241
66 278473
67 545495
68 172750
69 637973
70 264286
71 129097
72 549304
73 706563
74 238385
75 342499
76 409256
77 343627
78 346233
79 450343
80 516544
81 489037
82 503300
83 674405
84 295829
85 214935
86 515143
87 910403
88 325789
89 581163
90 157082
91 632977
92 254149
93 407347
94 714133
95 893447
96 428705
97 1205063
98 407574
99 594083
100 691020
101 932297
102 420743
103 663521
104 438572
105 843977
106 396470
107 715357
108 586562
109 743545
110 581004
111 832777
112 518819
113 536935
114 456511
115 697903
116 528984
117 1255085
118 777471
119 1365009
120 314965
121 558157
122 682910
123 1081209
124 955134
125 1024733
126 786290
127 876517
128 543306
129 1052919
130 794340
131 1055315
132 1212369
133 1220529
134 1336784
135 1426345
136 1869057
137 939523
138 561145
139 643633
140 1115926
141 1265109
142 1070722
143 806991
144 1728380
145 954071
146 943307
147 1029765
148 992262
149 946289
150 1001541
151 2250633
152 1168271
153 1561751
154 1258360
155 1308141
156 2217390
157 2071639
158 1019456
159 2299193
160 1449025
161 945929
162 884830
163 1476849
164 1187528
165 1592833
166 1420231
167 1426261
168 1087130
169 1692883
170 1496056
171 1445129
172 1681184
173 1376113
174 1603743
175 1718047
176 1389488
177 1394293
178 1648008
179 2711863
180 1291984
181 1446621
182 2561796
183 1895393
184 708527
185 1774839
186 1868045
187 1574359
188 940137
189 1788173
190 1693272
191 2662431
192 1456050
193 2415547
194 1124926
195 2617347
196 1947656
197 2819985
198 2197098
199 1829997
200 809699
201 2044121
202 2122506
203 2217495
204 1810680
205 2177503
206 1399053
207 2025633
208 1732520
209 3030055
210 1501009
211 2167867
212 2107676
213 3805269
214 2044584
215 1993435
216 2186363
217 2670745
218 2049871
219 1175711
220 1874905
221 2018109
222 3697076
223 3044263
224 2683331
225 2228289
226 1805711
227 1635261
228 2097481
229 1797181
230 2316139
231 2062351
232 1649462
233 3592115
234 2340110
235 1839459
236 2124759
237 1960717
238 3144897
239 3412327
240 3110862
241 2418501
242 1155138
243 3395749
244 1716907
245 2484567
246 2840204
247 1603031
248 2492956
249 4544807
250 3340106
251 1716901
252 3443223
253 2626863
254 3422073
255 3453529
256 2930162
257 2933569
258 4252928
259 3331439
260 3617207
261 2670243
262 3131538
263 3795091
264 3208694
265 3796929
266 1522318
267 3774207
268 3953075
269 2940335
270 6308575
271 4421033
272 3197227
273 3517211
274 3454869
275 4306065
276 4507656
277 3324211
278 2129570
279 3253603
280 4092157
281 4381737
282 2329064
283 4866943
284 3411806
285 5889017
286 2222460
287 4124103
288 2908151
289 2563643
290 4047755
291 3430819
292 4485410
293 3670157
294 4963502
295 2916381
296 4491155
297 5879187
298 4087452
299 5598777
300 4584846
301 4948861
302 4441028
303 4720735
304 3557597
305 4914515
306 7776710
307 3854381
308 3196094
309 5395199
310 5519123
311 5578071
312 3571439
313 3673983
314 1021807
315 2778207
316 4495385
317 5302579
318 6334009
319 5281891
320 5980802
321 3846165
322 4619994
323 4019303
324 3852691
325 9527643
326 4394507
327 5097603
328 5069857
329 6513339
330 3295232
331 6384511
332 4699240
333 6182045
334 7141080
335 6311589
336 5838829
337 6440177
338 5729495
339 4872571
340 4085096
341 4988145
342 4037122
343 6586275
344 5587485
345 5451787
346 6070190
347 4937763
348 5259131
349 6724885
350 4994365
351 7101827
352 6191483
353 5041173
354 5224644
355 8394859
356 5777424
357 9701529
358 6714655
359 5872051
360 3933515
361 4372927
362 7663388
363 3014445
364 4273603
365 5831107
366 7044420
367 3023381
368 4463048
369 7358789
370 7588713
371 8974057
372 9010160
373 4671323
374 7277727
375 6606077
376 7276960
377 9823773
378 7071019
379 6688069
380 7380121
381 8853117
382 6621068
383 8858073
384 8978276
385 10583601
386 5726877
387 4198897
388 6647326
389 9040813
390 5369672
391 6017983
392 4983038
393 8440433
394 5727705
395 6855177
396 6523363
397 7032659
398 9670534
399 11385231
400 7451387
401 9757769
402 10674554
403 6690531
404 11412220
405 10561219
406 7771307
407 6228777
408 5679920
409 10760393
410 7877945
411 6171895
412 7951667
413 8762933
414 6213185
415 8674337
416 5981243
417 10875233
418 6699229
419 5765521
420 11729039
421 9231175
422 7044156
423 9764063
424 6539589
425 5190301
426 7186773
427 10190703
428 6858169
429 11263845
430 5639560
431 11395661
432 8455076
433 8513183
434 3206763
435 11500549
436 1971749
437 10901895
438 8116331
439 7415233
440 7418802
441 10489689
442 11942203
443 6478367
444 13034272
445 7522185
446 6586014
447 7740409
448 3477283
449 8873963
450 8848242
451 13917237
452 8665558
453 7619021
454 3351647
455 9864137
456 8388232
457 15651973
458 6482581
459 10747737
460 11712725
461 11375315
462 9152194
463 8908663
464 10888521
465 8339157
466 8834369
467 8485063
468 11616068
469 8665649
470 8290509
471 10620257
472 9952513
473 14587069
474 13038456
475 14068091
476 12751172
477 8733519
478 13997047
479 23757239
480 10177979
481 7448241
482 4890011
483 8787739
484 6382189
485 10063269
486 14568748
487 16331961
488 6448074
489 9833045
490 10473452
491 12512969
492 13223221
493 12520385
494 8536701
495 9507455
496 8688336
497 11284411
498 10113999
499 8351067
500 10089488
501 8226943
502 14575241
503 10077997
504 11684547
505 5903883
506 13005009
507 14420049
508 10652127
509 12157651
510 10693570
511 15274741
512 9217840
513 7586239
514 12914236
515 18124565
516 4249266
517 5138243
518 5388316
519 15443945
520 14912730
521 7705115
522 17294241
523 9389595
524 9264477
525 10473779
526 16865427
527 10395779
528 10444278
529 16119671
530 12768125
531 17474513
532 14632481
533 21559895
534 20960565
535 9157559
536 19987126
537 16118325
538 18132646
539 17390997
540 18031042
541 13095591
542 16077155
543 10862001
544 15392911
545 8570993
546 16469439
547 17870883
548 15803615
549 15563633
550 9045853
551 21088935
552 13008833
553 21240865
554 12132979
555 19195363
556 11893961
557 14380281
558 16637343
559 13215195
560 12614932
561 17903539
562 12088897
563 12654079
564 20880980
565 10427381
566 13554279
567 12062371
568 19804720
569 18985699
570 16340709
571 21083543
572 11752898
573 19195269
574 11828621
575 20239861
576 15525385
577 10962135
578 14136993
579 5850303
580 9275754
581 13012223
582 12001477
583 9654055
584 12629265
585 31317337
586 10091917
587 11164441
588 28870231
589 13012299
590 9993703
591 14678625
592 15754966
593 10512363
594 20969492
595 16939679
596 16291092
597 15013825
598 24809508
599 22750677
600 22627933
601 14954453
602 10062221
603 14774541
604 6141706
605 12872513
606 16012676
607 11053807
608 20149977
609 14377419
610 8078197
611 15600651
612 17456805
613 16648267
614 23061570
615 23988131
616 20351391
617 16466121
618 14023721
619 15974095
620 6886637
621 21061217
622 20340957
623 14958287
624 24868154
625 13430447
626 11234428
627 15971301
628 17499503
629 23939019
630 17181788
631 15486295
632 18338001
633 6779489
634 10941587
635 15743131
636 17978274
637 21029319
638 5692359
639 11777333
640 18817168
641 16858355
642 22976881
643 19306129
644 28362908
645 11925359
646 19218771
647 14456417
648 18080508
649 23898093
650 23749992
651 14574515
652 19782324
653 19050911
654 25027507
655 25596523
656 17768482
657 10923699
658 15940766
659 20536501
660 28319098
661 18824951
662 19750223
663 17743017
664 18868362
665 31344883
666 17080165
667 16451843
668 18586822
669 14377573
670 17857078
671 18094383
672 28410920
673 14785167
674 21504408
675 20359315
676 18081682
677 24952711
678 27270419
679 28346715
680 26453105
681 26898479
682 17974714
683 21010683
684 29387930
685 25934249
686 36956398
687 19791239
688 20104169
689 31778691
690 20814593
691 12525283
692 15635297
693 22389271
694 9624113
695 18492237
696 34714301
697 18518039
698 20680821
699 26228875
700 22333153
701 47524499
702 21323470
703 15854909
704 18937814
705 19925051
706 20855125
707 25981751
708 18769788
709 17378671
710 20714033
711 30320161
712 21504416
713 26637439
714 15506099
715 30357435
716 30506433
717 16876899
718 34902050
719 27849175
720 23100107
721 21055281
722 26954046
723 18915241
724 11907417
725 21070971
726 21180744
727 29612471
728 31100139
729 18218607
730 28619811
731 30975997
732 22644773
733 25408867
734 30330246
735 17333247
736 15355412
737 21867267
738 31223943
739 20951231
740 24598918
741 37184159
742 22331797
743 21998589
744 23782906
745 22214627
746 33353440
747 33065287
748 21713339
749 25697595
750 32870087
751 21904799
752 17625873
753 22534821
754 11157858
755 27469581
756 34225489
757 20800467
758 24409409
759 34877939
760 26360744
761 28461423
762 21421417
763 18478331
764 15076115
765 27136109
766 26726563
767 34196723
768 25479810
769 37095681
770 30939921
771 24364953
772 24257100
773 34984283
774 23787716
775 24179975
776 28999760
777 33299789
778 26876693
779 33030953
780 26369516
781 33111205
782 24293194
783 32413363
784 25810616
785 20826951
786 22564904
787 15192083
788 44273024
789 47164863
790 25697300
791 20604909
792 17244082
793 18577231
794 22903762
795 36794799
796 29395707
797 20419745
798 34124205
799 28931201
800 35031810
801 26126595
802 20669036
803 35130429
804 32618709
805 27117167
806 27912919
807 33801599
808 28128367
809 30306429
810 39353760
811 31548275
812 24990908
813 27502237
814 26668511
815 23166517
816 41392384
817 27451479
818 24552900
819 36411983
820 28725517
821 21029307
822 20321219
823 40880093
824 35191372
825 42544577
826 30728133
827 24377253
828 20031114
829 25768325
830 27070228
831 21611093
832 35800695
833 25157765
834 24918267
835 47612735
836 25066703
837 29892593
838 31738871
839 12307051
840 29585450
841 31722517
842 31891147
843 39503701
844 29477022
845 25374679
846 27430506
847 48033733
848 29809078
849 25288299
850 37520398
851 48584535
852 28013273
853 34202401
854 41909491
855 28719767
856 38486204
857 20090919
858 41134610
859 31547705
860 27998097
861 26700489
862 23339939
863 32129007
864 38153755
865 42515245
866 30000374
867 36097749
868 26364744
869 24868415
870 23610815
871 43960115
872 35500931
873 30814659
874 28603821
875 26964741
876 47496254
877 44392201
878 25543805
879 39754767
880 35524944
881 14095157
882 46480065
883 31089105
884 43874258
885 37752237
886 28779625
887 40308719
888 23418583
889 28566379
890 32458808
891 31767253
892 41322101
893 48167117
894 32853653
895 51633345
896 32742307
897 37690901
898 23201395
899 33747623
900 42511625
901 51994957
902 23831758
903 49466623
904 34213972
905 10062947
906 46463254
907 47186563
908 38385222
909 35351999
910 40784231
911 37463943
912 26345376
913 37837731
914 16684979
915 21891115
916 30157502
917 35025903
918 35209202
919 11493653
920 37688884
921 39779973
922 28412372
923 47131787
924 34424714
925 40279903
926 29573568
927 24062063
928 35381722
929 16980403
930 53279028
931 30226133
932 34642799
933 34448839
934 26566958
935 50101469
936 39628536
937 52689557
938 38724699
939 40607633
940 25349314
941 27675303
942 35703749
943 60184885
944 36848147
945 56808285
946 29879994
947 25081277
948 43186348
949 55737339
950 59880721
951 54413785
952 40047014
953 45906297
954 34771767
955 40707731
956 51427051
957 46170941
958 52448187
959 27528673
960 35960928
961 30496055
962 27251365
963 39762721
964 25631894
965 37567589
966 37219315
967 65973163
968 42038762
969 36918989
970 56308096
971 39021821
972 27574358
973 51240879
974 43431752
975 28669219
976 42253654
977 25965303
978 35806143
979 42709261
980 28277188
981 27012021
982 80688430
983 37431065
984 42505534
985 34724517
986 52457661
987 54167897
988 52812633
989 46568949
990 40604349
991 34926093
992 56645112
993 37412733
994 45458251
995 41773611
996 49326140
997 37243575
998 36787253
999 66046239
1000 19555510