0 1
1 0
2 3
3 4700063497
4 6
5 19147
6 10669
7 25
8 9
9 2228071
10 18
11 262279
12 3763
13 95
14 1010
15 481
16 20
17 45
18 35
19 2873
20 2951
21 3175999
22 42
23 555
24 50
25 95921
26 27
27 174934013
28 36
29 777
30 49
31 140039
32 56
33 2463240427
34 110
35 477
36 697
37 91
38 578
39 623
40 156
41 2453
42 540923
43 55
44 70
45 345119
46 287
47 1131
48 104
49 943
50 147
51 21967
52 4044
53 135
54 970
55 46979
56 220
57 125
58 59378
59 3811
60 119
61 23329
62 345
63 155
64 66
65 1064959
66 3007
67 245
68 75
69 887817490061261
70 1990362
71 19719
72 184
73 834976783
74 190
75 4029547
76 100
77 1207
78 115
79 931
80 81
81 329
82 162
83 429
84 470
85 143
86 406
87 18607
88 812
89 423
90 6631
91 5422229
92 105
93 175
94 310
95 4991
96 160
97 2076287
98 207
99 202201409
100 322
101 50721
102 19145
103 355
104 152
105 319
106 714
107 225
108 16733
109 8683
110 867
111 1917403
112 121
113 2097039
114 130
115 4819
116 140
117 40477
118 215
119 5829
120 136
121 2737
122 741
123 1001
124 150
125 387
126 2168638
127 1805
128 133
129 4997
130 602
131 4979787
132 325
133 7717397
134 189
135 1073
136 180
137 2327
138 43135634
139 144943
140 442
141 6782813041
142 385
143 369
144 770
145 2225759
146 39778637
147 1261877
148 294
149 2129701
150 342563
151 161
152 884
153 14795
154 290
155 289
156 380
157 159025
158 266
159 756737
160 492
161 187
162 253
163 655
164 430
165 6439
166 58957
167 3201
168 418
169 86070137
170 171
171 2424703
172 342
173 235
174 850
175 467429821
176 200
177 13279
178 1491046
179 333
180 6751
181 321187367
182 625
183 755
184 1956
185 680827363701
186 203
187 876445
188 377
189 10948709
190 198
191 9541
192 704
193 247
194 830
195 5959
196 780
197 441
198 415
199 8299
200 2211
201 4453
202 242
203 238407
204 410
205 1067
206 25317
207 1681
208 306
209 555589371
210 1702
211 26054947
212 4354
213 5017703
214 4110
215 1089
216 15560
217 38275817
218 286
219 871
220 228
221 249767
222 693482
223 955
224 352
225 133290503
226 22099
227 6677
228 455
229 2224331
230 41191
231 220567109627
232 276
233 279
234 790
235 749
236 460
237 47765
238 515
239 273
240 616
241 215070011
242 243
243 1055
244 270
245 11479
246 210395261
247 167671
248 1210249
249 2827
250 84379
251 261
252 7849
253 493
254 2530
255 529
256 260
257 425
258 45982
259 19679
260 1113
261 15172003
262 793
263 2955
264 6890
265 27550543
266 45881
267 388323827
268 295
269 194357
270 497
271 19547
272 29321
273 137251416059
274 1050
275 637
276 1100
277 1043
278 1035
279 437
280 299
281 651
282 847
283 1255
284 370
285 1631041
286 5041
287 765
288 736
289 512862281
290 37829462
291 412097
292 2166
293 957
294 730
295 15703
296 1460
297 20527
298 702
299 11371
300 1919
301 226711
302 374
303 1355
304 948
305 413
306 261991
307 26525
308 8115
309 157458552833
310 658
311 343738144742266767
312 392
313 20703919615
314 323
315 186047
316 338
317 897
318 475
319 1337
320 16064
321 901
322 12298
323 559
324 343
325 2071
326 434
327 36205
328 988
329 34031213
330 1081
331 3451
332 1703
333 3337
334 570
335 748409
336 2608
337 13471
338 851
339 77211413
340 371
341 52497
342 10385
343 1555
344 1029
345 767
346 1247
347 1605
348 395
349 403
350 2266
351 1219
352 432
353 535
354 670
355 440369
356 30532
357 845
358 667
359 1287
360 1352
361 1631
362 605
363 1655
364 1210
365 609
366 68527
367 29567191
368 5275
369 2117
370 782
371 473
372 14036
373 2695
374 961
375 542626067
376 500
377 621
378 495895
379 7813
380 868
381 18337
382 1778
383 1615
384 2432
385 8207
386 903
387 1661
388 1236
389 43737
390 19706
391 403129
392 627
393 4075
394 574
395 4173
396 3836
397 20267
398 632463
399 1754831987
400 462
401 564319
402 1132385
403 517
404 646
405 2908385595517
406 666
407 525
408 2212
409 134569
410 833
411 27981973
412 986
413 635
414 610
415 477397
416 592
417 84361
418 2197
419 3379
420 264193
421 9953473
422 1813
423 4090655
424 450
425 23397
426 989
427 419173
428 1155
429 18361
430 20022
431 707
432 5008
433 382891
434 590
435 100841
436 732
437 507
438 506
439 13031
440 128188
441 34201
442 558
443 1875
444 1921
445 2219
446 494
447 16397
448 912
449 483
450 3598
451 383787851
452 9022
453 2501
454 858
455 1060243
456 3320
457 1309
458 17127
459 9359
460 722
461 3885540629
462 242411
463 2155
464 1328
465 164196324252985941533
466 5306
467 4205
468 575
469 714079
470 2893
471 3871
472 1128
473 32295
474 550
475 149941
476 940
477 9439561
478 1115
479 6012019
480 928
481 673123
482 283443
483 10835
484 516
485 1343
486 781
487 2513
488 1391
489 20460691
490 551
491 1617
492 532
493 10475
494 530
495 130577
496 660
497 5205
498 638
499 5513641
500 3959
501 1547
502 3478
503 1133
504 4427
505 84989
506 6538
507 1759685
508 2028
509 247801
510 14039809331
511 2082221
512 513
513 3377
514 1026
515 13943
516 580
517 95763751
518 1275
519 33031
520 1078
521 99443
522 1379
523 1691
524 650
525 16753
526 4118
527 7940137
528 3824
529 2807
530 1711
531 2119
532 774
533 835
534 4438
535 713
536 1064
537 222218065
538 2915
539 134217189
540 23533
541 42763
542 1007
543 581
544 1776
545 1121
546 16207
547 119011
548 1498
549 584977
550 35906
551 332531
552 4267
553 703
554 1342
555 4486633
556 708
557 1125
558 1315
559 135011183
560 2096
561 138724321
562 4102
563 969
564 5909
565 279233
566 783
567 294065
568 648
569 9163
570 1339
571 3101
572 4465
573 8455
574 1054
575 232953
576 608
577 7807
578 2059
579 335039
580 3516
581 303976350129
582 1378
583 1435
584 6481126
585 195373141
586 23778
587 9465
588 695
589 16049
590 742
591 106769
592 656
593 675
594 1189
595 2099259451
596 1220
597 201983
598 1415
599 35304397
600 949
601 15917
602 2013
603 1159
604 1036
605 118079
606 1673
607 1441
608 968
609 7933293691
610 629
611 5269
612 90169
613 41309
614 7790
615 8495801767
616 820
617 861
618 2726
619 855892952693
620 1107
621 99657629
622 3006
623 20933435
624 1250
625 1817
626 1261
627 557629
628 2108
629 1677
630 825668761
631 130441
632 1545
633 30179
634 11993
635 11563591
636 836
637 1357
638 735
639 2921
640 832
641 2086027
642 35039
643 624061535
644 294758
645 1067706307
646 33166
647 1245
648 715
649 3577612969291381957
650 211786
651 2263272601
652 4326
653 9761
654 31006
655 1421
656 1720
657 20725
658 1314
659 11899
660 754
661 893
662 5198
663 3155
664 3102
665 2509
666 7213999231
667 1519
668 16341
669 455286451057
670 2170097
671 25779
672 28192
673 3721
674 1269
675 5808628761697
676 900
677 1419
678 1507
679 89330333
680 12052
681 1144669
682 1625
683 855
684 4658
685 4677383419
686 2697
687 1027
688 852
689 1887
690 1967
691 7501
692 6165
693 394855
694 990
695 1551
696 748
697 3983
698 16035
699 304249
700 3396
701 2247
702 109774
703 327415
704 1376
705 30799
706 962
707 725
708 4202
709 32651
710 3729
711 50897
712 1445
713 1135
714 21431
715 30637021
716 1540
717 7657
718 2618
719 903291
720 5104
721 133410763
722 1079
723 3455
724 3030
725 1012441
726 3142537
727 3397
728 729
729 166014889
730 846
731 14559
732 7826
733 6767
734 803
735 31553
736 740
737 29385
738 15355
739 394567
740 31924
741 9988731091037308003
742 76614
743 915
744 5656
745 14333
746 1521
747 2585
748 895
749 4566783
750 65161
751 103518541
752 14353
753 611795
754 526378
755 1501
756 553843
757 10025
758 1455
759 25427
760 1668
761 37040091
762 220951
763 11051
764 987
765 1183
766 1634
767 1241
768 2816
769 793963
770 33182
771 128053255763
772 3324
773 86333
774 3122
775 10027
776 1240
777 1271
778 15535
779 4841
780 24961
781 4571
782 1809
783 3755
784 1136
785 5439
786 3082
787 45223
788 7291
789 112169
790 23826
791 899
792 594712
793 6307075
794 4191
795 9740213
796 7062
797 23613
798 1915
799 25455747038179
800 952
801 1649
802 34265
803 108197
804 99770
805 751819
806 1491
807 3565
808 1272
809 1589
810 3881902
811 72599
812 1826
813 1235
814 2422
815 787003897
816 1946
817 9085445
818 14775
819 75920671
820 1092
821 109527
822 1829
823 8077591
824 1139
825 26241601
826 39433
827 1739
828 995
829 405386897
830 42503
831 9741494677
832 1564
833 31935
834 42074
835 8449
836 2133
837 10234647185
838 29034
839 211479
840 1748
841 827977
842 2318
843 2575
844 1014
845 3159613
846 325713779
847 64834393
848 1995
849 2725497894187
850 56738
851 23080421
852 6166228
853 2629
854 4917
855 13123
856 1368
857 1045
858 2227
859 7627
860 2698
861 8592082903
862 2442
863 6555
864 2204
865 5603
866 20935242067
867 139445
868 3228
869 52603
870 10106
871 930186118118867
872 3878
873 76187
874 2250
875 20999
876 1798
877 71365
878 3335
879 92870183
880 1976
881 9736056265781
882 4709
883 20435
884 4619
885 100882904641861
886 21306
887 6233
888 49502
889 7677767
890 1863
891 1225051
892 1062
893 2975
894 63310
895 3097
896 1616
897 22747885
898 1246
899 4213
900 1106
901 888491
902 2251041
903 2561
904 1596
905 10491
906 3293
907 3193
908 4307
909 4727
910 2567
911 3633
912 5005
913 2120018333
914 917
915 103109
916 3660
917 1943
918 2215
919 8239
920 15657
921 7747
922 1794
923 2035
924 1065052
925 251641
926 1834
927 969119
928 1232
929 3497
930 9773
931 12287
932 2625
933 3077
934 6990
935 1883
936 3128
937 1111
938 1298
939 141691000109
940 2684
941 2613
942 1591
943 4555
944 946
945 1541
946 1674
947 1645
948 18518
949 5747
950 7169
951 169579
952 1572
953 1515
954 1513
955 271193
956 2660
957 55789273
958 2315
959 4899
960 1819
961 2275399
962 4334
963 1169
964 6516
965 8833
966 1102
967 1265
968 1288
969 93615868517
970 5138
971 1377
972 116497
973 93847
974 1969
975 20682703
976 1140
977 1003
978 5555
979 918296551
980 19866717
981 4443747872057
982 4087
983 235549
984 1717
985 1991581
986 659103
987 1158892877
988 1195
989 32477
990 1258
991 6041
992 3424
993 6355
994 2882
995 31187
996 7037
997 4790845
998 1127
999 4574351
1000 1332
1001 10693
1002 2185
1003 4855
1004 3796
1005 153103
1006 5550283
1007 1305
1008 1744
1009 2809
1010 7546
1011 1411
1012 3084
1013 1095
1014 6854
1015 3901
1016 1058
1017 17605
1018 1602
1019 4559
1020 10382
1021 1049593
1022 4913
1023 4955
1024 1030
1025 1881
1026 3143