1 1
2 3
3 5
4 7
5 3
6 19
7 67
8 179
9 31
10 311
11 59
12 709
13 419
14 5867
15 557
16 2971
17 61
18 157
19 373
20 829
21 1741
22 38303
23 2381
24 1039
25 191
26 4967
27 13411
28 375509
29 418837
30 966547
31 14981479
32 16127
33 16631
34 149
35 163
36 5869
37 15511
38 829
39 137
40 29
41 17
42 13
43 7
44 103
45 61
46 401
47 31
48 1489
49 191
50 9551
51 3163
52 164477
53 622663
54 206281
55 4759
56 163
57 101
58 31
59 61
60 523
61 997
62 317
63 4993
64 523
65 2833
66 757
67 317
68 21557
69 3011
70 2129
71 3779
72 1129
73 29
74 113
75 163
76 953
77 36691
78 168347
79 2216569
80 33757
81 1367159
82 4597
83 7949
84 311
85 2203
86 2339
87 101747
88 229583
89 364873
90 1423
91 64747
92 79423
93 28409
94 68473
95 2069
96 227
97 367
98 631
99 6247
100 61
101 79
102 8059
103 415039
104 4423
105 631
106 317
107 53
108 229
109 1783
110 107
111 5939
112 221723
113 22777
114 2596579
115 268049
116 126913
117 15121
118 6217
119 15413
120 1621
121 971
122 118463
123 291419
124 643
125 197
126 241
127 1913
128 48973
129 3158759
130 970777
131 1031
132 136093
133 11987
134 1606259
135 3209
136 23
137 197
138 877
139 401
140 1811
141 541
142 4519
143 3989
144 1847
145 11159
146 46549
147 2287
148 338477
149 6991
150 17191
151 5171
152 587
153 22453
154 3457763
155 267976633
156 21852773
157 333031
158 4397
159 9199
160 210263
161 8689
162 1407619
163 16388707
164 32429
165 12329
166 2903
167 1087
168 182617
169 670919
170 114056231
171 50587
172 1471
173 7069
174 5279
175 1949
176 13721
177 809
178 2087
179 1237
180 11719
181 139
182 937
183 1531
184 547
185 937
186 439
187 41047
188 2572279
189 8923
190 1861
191 1559
192 299329
193 28885249
194 8016793
195 103583
196 520571
197 12819061
198 183037
199 1399
200 241
201 457
202 499
203 16883
204 44729
205 10687
206 733841
207 5507
208 929
209 97081
210 287141
211 78889
212 179833
213 166541
214 1049
215 881
216 190297
217 825889
218 881
219 877
220 641
221 367
222 3259
223 363379
224 27132299
225 1249
226 1613
227 1237
228 937
229 6311
230 1451531
231 506501
232 2459
233 631
234 29531
235 165233
236 35099
237 211
238 3863
239 9421
240 2261041
241 272455441
242 2230597
243 249097
244 87959
245 5387489
246 1223
247 199
248 16451
249 137
250 233
251 14621
252 13697
253 21391
254 362221
255 624097
256 2591
257 20809
258 6221
259 463
260 40127
261 374041
262 9413
263 17683
264 359101
265 991
266 87869
267 733157
268 65495359
269 163131959
270 44045628931
271 44939
272 1111219
273 20887
274 4517
275 1493
276 43
277 1489
278 4451
279 124183
280 9803
281 688661
282 985799
283 241
284 13
285 109
286 43
287 17
288 83
289 1999
290 1597
291 5281
292 90709
293 499
294 13337
295 81967
296 3527
297 6547
298 1951007
299 120977
300 2791777
301 835313
302 540181
303 2406983
304 245627
305 18729059
306 88170647
307 20983247
308 17326649
309 14315333
310 1479251077
311 387245021
312 13458889
313 220811
314 1066687
315 168003203
316 18414503
317 5385053
318 6989579
319 371612617
320 33620593
321 294499
322 118093
323 71
324 107
325 23
326 7499
327 1226087
328 134052179
329 188401
330 4782487
331 20399
332 615679
333 368743
334 374347
335 101
336 33937
337 1129
338 971
339 32917
340 1049
341 35771
342 22697
343 6007
344 229601
345 39606173
346 845753
347 73369073
348 11057
349 239
350 3637
351 319147
352 9697
353 3881
354 379
355 67273
356 26879
357 58511
358 2699
359 449
360 161641
361 369319
362 14854831
363 1137137
364 6793
365 113
366 701
367 1949
368 65203
369 983
370 2957
371 137131
372 73189
373 1021
374 25457
375 71
376 809
377 2089
378 3541
379 4793
380 9437
381 78163
382 29858267
383 68889857
384 179453
385 11514901
386 7298443
387 7001
388 109
389 191
390 457
391 349
392 563
393 37
394 239
395 3631
396 281
397 18593
398 12437
399 3889
400 4483
401 21401
402 563
403 2521
404 1741
405 12157
406 4935743
407 1004423701
408 409804870009
409 339291886303
410 2083
411 61151
412 2069
413 427249
414 3337379
415 10992161
416 247939
417 71999
418 1433123
419 665719
420 279601981
421 661305809
422 257293
423 92233
424 60257
425 4523
426 673
427 71843
428 6149761
429 1753
430 5059
431 3461
432 109
433 23599
434 31321
435 701
436 101879
437 11130281
438 296663
439 7235281
440 1267831
441 13399
442 5922359
443 18637
444 81929
445 2025467
446 263293
447 224603
448 6217
449 27367
450 7523
451 757
452 22811
453 1291673
454 75853
455 261463
456 17032447
457 51169
458 13729
459 1543
460 1181
461 239
462 110419
463 1503647
464 3505991
465 11117
466 1726841
467 4114463
468 385113737
469 180257827
470 13702277
471 11282819
472 36227827
473 33301
474 631387
475 12433
476 3049
477 38273
478 39343
479 116329
480 1509133
481 1010993
482 52973
483 9547
484 521
485 18049
486 134951
487 1579
488 151
489 71
490 11597
491 32353
492 4093
493 40357
494 130303
495 32249993
496 5331998843
497 662500856243
498 5796809741
499 21599
500 5711
501 715303
502 327331
503 831553
504 9127
505 5879
506 463
507 117371
508 6624941
509 337209497
510 171976843471
511 43940083506841
512 2499702528389177
513 1383601159
514 3847849
515 216431
516 18269
517 26681
518 321413
519 3207949
520 12542357
521 466754857
522 111508483
523 499691
524 1415341
525 2598091
526 15017537
527 565303
528 1388279
529 1799999
530 2517149
531 33415153
532 991957
533 362629
534 6246577
535 75527
536 40482473
537 221281
538 1676749
539 9414247
540 397
541 6317
542 4201
543 911
544 3671
545 313
546 170899
547 16747
548 419
549 1307
550 34231
551 281
552 22159
553 49411
554 25703
555 7132583
556 65809
557 2036423
558 2951491
559 3499
560 59377
561 27259
562 487
563 45697
564 61511
565 33289
566 251221
567 35610577
568 192991
569 305033
570 2946929
571 28044941
572 3131311
573 660619
574 379195307
575 9910786433
576 625190339
577 48564193
578 695407
579 1277
580 1033
581 33343
582 181361
583 2939
584 4259
585 622879
586 1028189
587 9421
588 8779
589 2467
590 6301
591 930973
592 210277
593 29989
594 1399
595 6823
596 1355503
597 11900519
598 2903513
599 673
600 23753
601 2379259
602 4301243
603 13650787
604 87011
605 387071
606 1404581
607 4179317
608 1272421
609 5960803
610 5483
611 1675057
612 205026977
613 62157041
614 26633
615 30109
616 119659
617 6152467
618 3338213
619 3079
620 4159
621 73
622 2671
623 1031
624 128669
625 788413
626 15139
627 39883
628 8419
629 27581
630 294509
631 65899
632 593
633 37537
634 231053
635 491
636 6373
637 2029801
638 22719527
639 83911
640 1931
641 3917
642 71849
643 183329
644 118063877
645 20459753
646 191550731
647 3211207
648 2080862137
649 390707
650 2514451
651 182813
652 39731359
653 4011221
654 67883
655 12413
656 8142929
657 2674952177
658 586706177489
659 96659842741313
660 63795496209266581
661 6493505234728243
662 16429019
663 115877017
664 705893021
665 9522067
666 6341696623
667 157444787
668 30317993
669 119689
670 6168587
671 7869053
672 406769509
673 14409721
674 8111
675 7583
676 1708703
677 2371
678 1889
679 4111
680 23893
681 1009
682 688139
683 3923
684 4349
685 496511
686 857951
687 912403
688 70177
689 1151237
690 794353531
691 169308541
692 4128749
693 37307
694 30713
695 419
696 2333
697 30113
698 168151
699 857
700 199967
701 1777
702 613
703 743
704 1061
705 101
706 139
707 1489
708 1054213
709 1108957
710 54941
711 1395109
712 993317609
713 786979
714 5455369
715 975147209
716 569659
717 6381961
718 654606857
719 828630863
720 3660209947
721 59977531177
722 8677
723 1181
724 19001
725 6887863
726 12789229
727 2324442371
728 4019
729 1301
730 316577
731 9013
732 6597517
733 38639
734 28361027
735 34763
736 587
737 223
738 227
739 383
740 2039
741 521
742 128861
743 7459
744 326441
745 40533091
746 10079228629
747 8544317
748 86017
749 49031
750 14149
751 1801
752 41
753 359
754 3923
755 1480933
756 8831
757 42853
758 4657
759 127
760 367
761 431
762 19319
763 7247
764 190921
765 10432469
766 1181267
767 86371
768 300149
769 38469097
770 759518069
771 16921
772 271
773 23
774 937
775 2063
776 1600889
777 36497
778 67
779 8699
780 30427
781 106087
782 19543
783 117709
784 1377371
785 421699
786 2882221
787 1361
788 16007
789 569
790 149837
791 29630267
792 125597
793 1117
794 22741
795 2857
796 2617
797 103
798 967
799 197
800 439
801 149
802 653
803 13109
804 52963
805 2887
806 5501
807 1087
808 125471
809 18523
810 15003631
811 1100773
812 171923
813 53759
814 26863
815 433
816 353329
817 20619271
818 5696239
819 171251
820 19577
821 3011
822 9133
823 1013
824 75883
825 1203913
826 994432139
827 2543171
828 5279
829 364691
830 6177419
831 4787
832 3361
833 466619
834 55594321
835 11605314509
836 388081717181
837 3019768303
838 9829
839 5167
840 394571
841 3072539
842 2587077839
843 110731
844 1093
845 2609
846 441443
847 2010227
848 107693
849 11689
850 347
851 409
852 401
853 613
854 281
855 1877
856 535571
857 34019
858 29101
859 281
860 79
861 179
862 2707
863 389357
864 9929
865 20161
866 56503
867 31687
868 39461
869 7159
870 270797
871 55057
872 3889
873 1231
874 215179
875 251
876 311
877 191
878 23957
879 6143
880 1619
881 71317
882 65183
883 727
884 89
885 39383
886 20807
887 1845581
888 1638875929
889 664065953
890 6113
891 1873
892 1670717
893 1182211
894 211379327
895 76157
896 2201183
897 863
898 10333
899 317
900 285301
901 57149
902 1289
903 1399
904 257
905 116293
906 769
907 1373
908 1193
909 542219
910 164473097
911 72223
912 124513
913 15383
914 93113
915 21299599
916 129221
917 8353
918 3863
919 12589
920 82141
921 173
922 479
923 221059
924 204258517
925 41307199
926 20483
927 24281
928 7013
929 61463
930 123457
931 145861
932 15104717
933 7046350481
934 21771089
935 17401
936 9431
937 563
938 105619
939 4508011
940 4423
941 2731
942 863
943 27127
944 38977
945 41017
946 61493
947 1039
948 593
949 13399
950 61493
951 1579
952 15497
953 1054903
954 57301
955 402371
956 384666677
957 5399
958 8171
959 783599
960 251843
961 231821
962 740903
963 88853
964 28551431
965 4207717
966 529183
967 855719
968 74071
969 179437
970 15823081
971 8368307
972 2859049
973 50147
974 634327
975 4615439
976 2481911
977 43300483
978 1197113
979 4650689
980 9635677
981 34498537
982 87993671
983 42693869
984 3231597469
985 122427827191
986 39373963
987 2709671
988 103393
989 811553
990 329683
991 34913
992 7841
993 11833
994 1069273
995 17159
996 3418073
997 5051
998 5040899
999 163853
1000 1400453