1 0
2 11
3 24
4 1
5 63
6 26
7 16
8 139
9 9
10 118
11 20
12 238
13 174
14 77
15 180
16 45
17 199
18 3
19 82
20 618
21 752
22 411
23 176
24 196
25 413
26 137
27 145
28 560
29 232
30 28
31 2275
32 1548
33 659
34 888
35 297
36 1039
37 2278
38 321
39 1273
40 1881
41 344
42 2925
43 672
44 253
45 1960
46 1541
47 1680
48 295
49 5422
50 2422
51 2556
52 227
53 916
54 1290
55 1294
56 2176
57 93
58 4706
59 423
60 2421
61 2129
62 10897
63 3024
64 946
65 7722
66 670
67 808
68 7310
69 7325
70 2091
71 1261
72 1833
73 2647
74 6343
75 226
76 5934
77 1305
78 2418
79 8422
80 1134
81 759
82 2165
83 7217
84 1523
85 291
86 7943
87 4703
88 7784
89 6494
90 3832
91 1869
92 4768
93 2870
94 6768
95 722
96 6981
97 10817
98 7185
99 2782
100 3547
101 231
102 190
103 7470
104 7688
105 18064
106 11332
107 1153
108 6899
109 2901
110 9700
111 13923
112 14642
113 1683
114 3816
115 825
116 456
117 8894
118 16571
119 8939
120 7136
121 2428
122 9776
123 1568
124 11482
125 39580
126 1237
127 14427
128 3797
129 11544
130 22690
131 7665
132 1986
133 16316
134 17717
135 22461
136 26835
137 1136
138 1851
139 29910
140 1672
141 1504
142 29981
143 22545
144 32863
145 727
146 3140
147 45838
148 27901
149 26694
150 666
151 40202
152 3091
153 40089
154 37508
155 134
156 4560
157 12387
158 4466
159 451
160 9071
161 5657
162 73695
163 33630
164 15248
165 407
166 90541
167 4683
168 2188
169 37300
170 31714
171 6564
172 10988
173 15880
174 3831
175 6329
176 18598
177 14687
178 31520
179 4122
180 11604
181 12479
182 4771
183 76485
184 39536
185 3992
186 21519
187 5289
188 7875
189 4391
190 23525
191 78573
192 374
193 6204
194 54469
195 41857
196 10796
197 3656
198 46941
199 3320
200 3612
201 48644
202 12563
203 80330
204 15965
205 56295
206 21754
207 33063
208 26153
209 2156
210 18527
211 4136
212 84406
213 25445
214 44750
215 10466
216 26080
217 31361
218 21303
219 19263
220 50542
221 69891
222 163698
223 33293
224 4409
225 86329
226 5456
227 20591
228 12377
229 218461
230 84896
231 6288
232 58789
233 24878
234 37876
235 115742
236 40604
237 13465
238 23458
239 91498
240 31231
241 4769
242 5759
243 60553
244 23692
245 76038
246 40929
247 20364
248 9263
249 71596
250 17729
251 27981
252 106722
253 58327
254 34762
255 93085
256 13320
257 5207
258 21718
259 109232
260 42642
261 33170
262 134748
263 480
264 61099
265 41347
266 8752
267 55353
268 32465
269 139589
270 16373
271 154008
272 1648
273 101728
274 30328
275 86282
276 37278
277 216978
278 52095
279 93915
280 58840
281 21918
282 4629
283 57431
284 70327
285 24908
286 131128
287 31702
288 129241
289 131592
290 36051
291 42272
292 210001
293 19697
294 58724
295 100899
296 102062
297 25705
298 26167
299 66394
300 6674
301 102273
302 19686
303 76688
304 69930
305 32999
306 159387
307 5810
308 244982
309 631
310 41850
311 57794
312 82395
313 12668
314 76801
315 114171
316 4473
317 77661
318 43909
319 19247
320 38450
321 7890
322 184515
323 128622
324 19180
325 15331
326 133930
327 16064
328 32495
329 53563
330 218447
331 58192
332 50147
333 75932
334 425919
335 66069
336 102673
337 39770
338 299
339 125931
340 118708
341 265356
342 33139
343 68725
344 66206
345 135934
346 54490
347 86340
348 51347
349 30307
350 96885
351 31351
352 18345
353 37251
354 44201
355 82852
356 21621
357 47106
358 49508
359 33133
360 3820
361 156301
362 87163
363 100964
364 3785
365 66184
366 90682
367 50621
368 386578
369 24657
370 283037
371 35145
372 24457
373 87724
374 21454
375 48244
376 145181
377 316876
378 172489
379 85076
380 29728
381 182365
382 91191
383 45947
384 126
385 313357
386 502853
387 2033
388 360506
389 29710
390 109883
391 27970
392 15111
393 45529
394 234163
395 24961
396 50833
397 4697
398 28288
399 15738
400 218941
401 174571
402 96255
403 88452
404 68533
405 6707
406 875
407 148069
408 48155
409 80951
410 19793
411 105106
412 108393
413 184706
414 3318
415 120309
416 292758
417 68375
418 28586
419 188062
420 62824
421 34864
422 108587
423 3105
424 41153
425 197760
426 427006
427 5263
428 62
429 81551
430 116234
431 124948
432 179609
433 166327
434 134430
435 91060
436 181958
437 107559
438 117652
439 37960
440 58411
441 14555
442 102776
443 83780
444 17305
445 119984
446 247692
447 29984
448 183162
449 113861
450 75630
451 49939
452 43300
453 190558
454 15540
455 12186
456 50785
457 61107
458 571
459 342262
460 415543
461 54827
462 260178
463 8749
464 21558
465 64931
466 63328
467 70002
468 6648
469 305214
470 36277
471 4300
472 418146
473 30571
474 276601
475 546997
476 120067
477 615097
478 48718
479 45548
480 16874
481 109498
482 246232
483 470552
484 56854
485 15928
486 55552
487 7076
488 48101
489 496375
490 23152
491 100792
492 301009
493 80932
494 241902
495 41837
496 90898
497 20401
498 118787
499 628814
500 79962
501 50666
502 14677
503 210605
504 78831
505 264540
506 60804
507 100091
508 12629
509 63675
510 17868
511 175892
512 143190
513 36193
514 20685
515 80612
516 30720
517 789268
518 435127
519 476346
520 21952
521 32608
522 181596
523 202770
524 440377
525 2697
526 287561
527 1555
528 480246
529 73262
530 158148
531 29273
532 649005
533 196764
534 7074
535 36934
536 85607
537 113187
538 54664
539 53719
540 348621
541 1044801
542 2012
543 170088
544 301705
545 17481
546 402417
547 107391
548 154285
549 45842
550 16870
551 165089
552 1018135
553 38883
554 14788
555 68517
556 61243
557 36350
558 46588
559 51761
560 26395
561 2802
562 90999
563 306090
564 138632
565 13539
566 205969
567 24685
568 295404
569 82265
570 150398
571 18377
572 132334
573 4636
574 90635
575 362430
576 39250
577 100726
578 118750
579 112097
580 659527
581 223288
582 81744
583 69198
584 1083261
585 115411
586 261336
587 70905
588 230499
589 399604
590 329030
591 726785
592 142777
593 67702
594 121935
595 117644
596 928128
597 304345
598 127734
599 211984
600 32831
601 96445
602 478804
603 147406
604 275843
605 337818
606 8567
607 344518
608 266391
609 409335
610 63754
611 190651
612 231499
613 490731
614 292689
615 675520
616 16310
617 956240
618 989261
619 1549943
620 183494
621 220041
622 338108
623 202140
624 425627
625 76516
626 24867
627 191761
628 147815
629 150932
630 399607
631 146164
632 103513
633 424017
634 592412
635 38506
636 205888
637 339518
638 323322
639 698014
640 285865
641 191635
642 1932157
643 715212
644 52579
645 125302
646 210524
647 115469
648 325148
649 87113
650 52239
651 1010243
652 124225
653 241918
654 1020425
655 367935
656 474985
657 10557
658 209491
659 2529
660 71722
661 377257
662 154534
663 28750
664 177940
665 1330175
666 913303
667 89920
668 195672
669 247870
670 505200
671 303790
672 44037
673 215756
674 431088
675 393568
676 329444
677 405943
678 23454
679 249836
680 177658
681 328965
682 433663
683 174755
684 561642
685 162103
686 89389
687 215434
688 368857
689 911306
690 375727
691 125381
692 121880
693 13820
694 236132
695 503909
696 133500
697 461716
698 452144
699 286029
700 342648
701 12604
702 53820
703 22105
704 57497
705 203125
706 1544709
707 303002
708 206613
709 22142
710 237962
711 447618
712 481799
713 1457453
714 30279
715 50724
716 179703
717 635507
718 52648
719 451314
720 668526
721 129828
722 161061
723 159936
724 437819
725 886866
726 248691
727 459509
728 639971
729 352262
730 100759
731 476747
732 196287
733 138921
734 745235
735 52969
736 56120
737 25954
738 46736
739 225560
740 388834
741 238217
742 362482
743 306197
744 352127
745 103866
746 2056233
747 137417
748 849875
749 259490
750 55572
751 325611
752 28050
753 362178
754 56961
755 453671
756 1845700
757 60357
758 1666052
759 483621
760 20305
761 511387
762 313673
763 126972
764 230114
765 428228
766 300027
767 937448
768 474647
769 491237
770 220162
771 728901
772 39305
773 73592
774 12732
775 84880
776 188690
777 1187697
778 82278
779 1993023
780 1891393
781 10717
782 150821
783 129368
784 251474
785 364846
786 751320
787 197093
788 300600
789 778220
790 133196
791 690640
792 230869
793 1200160
794 245541
795 208258
796 535583
797 175320
798 1265496
799 1395521
800 164832
801 356778
802 206289
803 549917
804 507940
805 244352
806 2214025
807 764706
808 698834
809 314899
810 1230279
811 148825
812 1503152
813 279997
814 494528
815 314350
816 228733
817 125652
818 59253
819 239842
820 202340
821 23619
822 29993
823 279580
824 97537
825 558809
826 281736
827 432196
828 1212234
829 971926
830 931365
831 229279
832 65602
833 171550
834 72983
835 462278
836 713815
837 688181
838 772842
839 1697306
840 810987
841 283094
842 672619
843 180545
844 169851
845 87337
846 803176
847 17293
848 771897
849 579882
850 383077
851 170609
852 461901
853 297374
854 7461
855 35021
856 724309
857 104480
858 732894
859 25936
860 511631
861 161182
862 166352
863 233750
864 103689
865 106123
866 1983746
867 613783
868 312173
869 25050
870 19611
871 148152
872 1692043
873 913334
874 149807
875 458888
876 213370
877 284696
878 182704
879 2214785
880 910091
881 295043
882 801950
883 685411
884 114894
885 404856
886 310528
887 468596
888 1060613
889 1001908
890 1018605
891 186636
892 252630
893 2767110
894 757772
895 67841
896 312167
897 19378
898 2064229
899 455482
900 168917
901 725939
902 1172392
903 86323
904 394356
905 12421
906 90242
907 6157
908 1726100
909 898104
910 407075
911 230181
912 187177
913 28778
914 566881
915 205122
916 225011
917 66618
918 110408
919 762245
920 1530428
921 1157771
922 2759
923 498800
924 61558
925 76574
926 498024
927 261668
928 267905
929 456606
930 833094
931 6224
932 105915
933 1832648
934 1153713
935 925761
936 12082
937 627343
938 358896
939 973755
940 49959
941 931760
942 881150
943 421575
944 1152568
945 278197
946 569761
947 690309
948 667518
949 357493
950 92844
951 644110
952 509077
953 215480
954 528802
955 99998
956 1285957
957 197944
958 83331
959 238210
960 66295
961 2585323
962 30155
963 242075
964 87416
965 995579
966 57702
967 127291
968 821952
969 2286693
970 320453
971 453219
972 204488
973 1531787
974 324434
975 1654720
976 251253
977 10976
978 8868
979 384713
980 191924
981 214236
982 736315
983 806653
984 1967133
985 624296
986 644849
987 488341
988 3732822
989 3436967
990 6576
991 1076220
992 437793
993 124519
994 383622
995 1056894
996 1705526
997 1676405
998 367829
999 1940003
1000 23158
1001 474057
1002 362812
1003 254243
1004 188415
1005 42764
1006 845575
1007 307292
1008 1082737
1009 879330
1010 150589
1011 2707134
1012 105490
1013 951009
1014 4539
1015 484462
1016 131580
1017 48392
1018 45478
1019 1277593
1020 475629
1021 133941
1022 1732821
1023 141903
1024 383428
1025 132636
1026 1319088
1027 938692
1028 313969
1029 1061330
1030 183571
1031 1116344
1032 18782
1033 1050229
1034 580488
1035 771113
1036 319228
1037 960628
1038 618782
1039 702212
1040 1185799
1041 10745
1042 439923
1043 323082
1044 174744
1045 141000
1046 478895
1047 68867
1048 1602652
1049 681719
1050 1101534
1051 1687825
1052 1904495
1053 179030
1054 744166
1055 385721
1056 1446243
1057 197880
1058 1541028
1059 111954
1060 271040
1061 878837
1062 720950
1063 83596
1064 70159
1065 955720
1066 27831
1067 173322
1068 452357
1069 71609
1070 4786518
1071 52715
1072 489831
1073 626787
1074 1231365
1075 1358320
1076 117651
1077 153450
1078 304620
1079 581069
1080 49023
1081 913056
1082 197537
1083 392431
1084 2438968
1085 915547
1086 1673276
1087 203367
1088 109212
1089 1620546
1090 25667
1091 656928
1092 453495
1093 726069
1094 2097632
1095 474192
1096 401345
1097 425162
1098 1037814
1099 1088060
1100 1545859
1101 1951637
1102 133274
1103 1525285
1104 3898939
1105 980204
1106 139405
1107 150469
1108 481150
1109 1515946
1110 131031
1111 1491066
1112 1349205
1113 4958175
1114 285823
1115 1197859
1116 447853
1117 315573
1118 453273
1119 267131
1120 1889877
1121 173007
1122 610229
1123 2251673
1124 494376
1125 297602
1126 143540
1127 591124
1128 305715
1129 251277
1130 251188
1131 482090
1132 1511036
1133 53758
1134 1449740
1135 500898
1136 272574
1137 1750898
1138 8281
1139 207863
1140 371808
1141 422411
1142 376857
1143 678508
1144 2817404
1145 709166
1146 548726
1147 80901
1148 1496055
1149 778218
1150 119177
1151 445276
1152 1400829
1153 224407
1154 888428
1155 1490461
1156 720387
1157 209861
1158 190107
1159 47542
1160 209641
1161 960153
1162 235461
1163 734471
1164 671359
1165 1363516
1166 865556
1167 191458
1168 1994885
1169 37329
1170 779306
1171 1784305
1172 50973
1173 1066014
1174 731853
1175 3775772
1176 11490
1177 329656
1178 2263790
1179 216662
1180 845703
1181 42971
1182 666448
1183 949994
1184 658535
1185 1625430
1186 1267218
1187 547991
1188 934599
1189 385430
1190 971764
1191 2156385
1192 291682
1193 1102626
1194 573986
1195 1651630
1196 179184
1197 158616
1198 984818
1199 1884331
1200 391529
1201 25411
1202 1637144
1203 1930487
1204 595184
1205 2566531
1206 214978
1207 2099127
1208 503687
1209 1256227
1210 2072931
1211 722120
1212 556070
1213 1492247
1214 590172
1215 1105360
1216 2184305
1217 1228722
1218 440572
1219 982877
1220 1436749
1221 1111210
1222 2482358
1223 150707
1224 1786164
1225 635226
1226 286297
1227 163316
1228 1595968
1229 1195727
1230 552957
1231 3918822
1232 347933
1233 647867
1234 517386
1235 2969690
1236 296345
1237 456091
1238 610299
1239 532223
1240 159130
1241 4218863
1242 563585
1243 584933
1244 15314
1245 319096
1246 2608243
1247 409680
1248 157558
1249 2865793
1250 452727
1251 1325562
1252 76387
1253 413305
1254 1015440
1255 267675
1256 597889
1257 498589
1258 3324085
1259 756579
1260 234372
1261 14941
1262 49118
1263 1128363
1264 353665
1265 624277
1266 432466
1267 1870560
1268 342103
1269 229117
1270 2911837
1271 544590
1272 218250
1273 3225694
1274 3241248
1275 1226688
1276 773175
1277 584244
1278 3216489
1279 1118193
1280 677747
1281 2952286
1282 586230
1283 2537421
1284 717602
1285 330516
1286 841180
1287 315046
1288 672452
1289 486648
1290 196356
1291 526165
1292 445424
1293 3410287
1294 3593587
1295 744216
1296 629578
1297 1566282
1298 312129
1299 2486887
1300 27261
1301 60811
1302 124499
1303 1530203
1304 429409
1305 130707
1306 2805918
1307 3911581
1308 852307
1309 1256371
1310 1978260
1311 260449
1312 469444
1313 6300988
1314 5211
1315 27522
1316 10677
1317 2917099
1318 551532
1319 1949913
1320 217037
1321 715703
1322 2770604
1323 1420377
1324 815608
1325 1455021
1326 1528824
1327 179043
1328 3155208
1329 1131573
1330 2055862
1331 26654
1332 503584
1333 1104374
1334 685935
1335 87573
1336 730618
1337 242318
1338 113686
1339 304491
1340 605390
1341 955298
1342 40635
1343 1695939
1344 331888
1345 2260729
1346 117958
1347 2783775
1348 174608
1349 125629
1350 1258013
1351 433504
1352 3697209
1353 844908
1354 396033
1355 3018
1356 96100
1357 1118431
1358 934505
1359 220001
1360 350506
1361 1283074
1362 767931
1363 79546
1364 460766
1365 776605
1366 625460
1367 504331
1368 186330
1369 2418397
1370 4155361
1371 17379
1372 1747397
1373 1180714
1374 503275
1375 2249812
1376 1609655
1377 324248
1378 643386
1379 966254
1380 2768389
1381 596100
1382 2094704
1383 354088
1384 1140290
1385 740807
1386 1407542
1387 2522593
1388 1862426
1389 2735329
1390 632239
1391 2247841
1392 323127
1393 153345
1394 989465
1395 170738
1396 1237445
1397 182652
1398 1059002
1399 286616
1400 1134804
1401 1733787
1402 1100873
1403 655510
1404 2648461
1405 1128126
1406 775847
1407 1379403
1408 3093358
1409 115224
1410 329042
1411 5112
1412 1631035
1413 4045329
1414 676104
1415 1111011
1416 3977291
1417 826096
1418 2428564
1419 1802378
1420 266187
1421 469706
1422 655293
1423 2804716
1424 58830
1425 2177323
1426 4538428
1427 6598077
1428 42665
1429 331798
1430 2097599
1431 1082297
1432 127566
1433 5394172
1434 1814078
1435 1295986
1436 805102
1437 421564
1438 87609
1439 252743
1440 164384
1441 1609886
1442 1370340
1443 1073276
1444 4273560
1445 726005
1446 1032023
1447 856740
1448 1686499
1449 1592069
1450 160954
1451 77082
1452 1472534
1453 344610
1454 586820
1455 480077
1456 224082
1457 1824751
1458 236091
1459 792584
1460 1914648
1461 527212
1462 2752695
1463 7830573
1464 339563
1465 1117094
1466 219041
1467 160390
1468 4449987
1469 11796
1470 3390620
1471 105963
1472 171584
1473 4851444
1474 220264
1475 2825262
1476 760906
1477 338878
1478 1646877
1479 583199
1480 4057997
1481 372712
1482 82501
1483 136867
1484 633318
1485 847058
1486 253478
1487 1920708
1488 282155
1489 1606768
1490 1341663
1491 455619
1492 874256
1493 3634422
1494 968260
1495 3688048
1496 71853
1497 3259529
1498 1392442
1499 1377726
1500 1664241
1501 3291719
1502 4570858
1503 864311
1504 2589502
1505 1143585
1506 1996262
1507 1578246
1508 2661012
1509 234336
1510 745003
1511 1703874
1512 2742130
1513 1279064
1514 48511
1515 2068737
1516 2933078
1517 173585
1518 129235
1519 6409861
1520 1692928
1521 2490072
1522 874501
1523 1246559
1524 4864564
1525 3033895
1526 2512873
1527 59042
1528 159681
1529 622128
1530 1379236
1531 833304
1532 932894
1533 327271
1534 3880915
1535 2080457
1536 115169
1537 1420940
1538 218822
1539 2821823
1540 2328810
1541 22864
1542 749947
1543 3022912
1544 1343494
1545 156834
1546 3297226
1547 946637
1548 3547067
1549 1537847
1550 3070507
1551 212998
1552 308964
1553 5184215
1554 4536372
1555 126173
1556 4199516
1557 488276
1558 4546431
1559 3426288
1560 1173490
1561 1394109
1562 1941355
1563 333924
1564 542780
1565 4050924
1566 1830718
1567 7228434
1568 70215
1569 622327
1570 924027
1571 1498489
1572 600319
1573 3360456
1574 1776007
1575 5361004
1576 449288
1577 4431450
1578 388251
1579 1809341
1580 271533
1581 485178
1582 566683
1583 1348981
1584 33126
1585 1905365
1586 63042
1587 3747070
1588 3311079
1589 3300838
1590 537862
1591 814939
1592 2757389
1593 3874422
1594 1347366
1595 692648
1596 1514577
1597 304668
1598 977199
1599 4485680
1600 240082
1601 10943
1602 208564
1603 6915
1604 86058
1605 1351882
1606 1693035
1607 1341793
1608 4609501
1609 814061
1610 306714
1611 580584
1612 687646
1613 670337
1614 2408939
1615 4153557
1616 3932427
1617 396081
1618 1352603
1619 747952
1620 901403
1621 1292873
1622 184249
1623 1167733
1624 229076
1625 797832
1626 145722
1627 947363
1628 3007911
1629 592231
1630 99029
1631 2575156
1632 904511
1633 431821
1634 3956304
1635 2499629
1636 193339
1637 2453755
1638 148320
1639 463144
1640 841571
1641 808531
1642 1890568
1643 175042
1644 878110
1645 6135555
1646 1131385
1647 1715137
1648 1467414
1649 502240
1650 3550065
1651 571487
1652 1038203
1653 250057
1654 1375548
1655 453847
1656 2940952
1657 4942733
1658 1021220
1659 103081
1660 1060167
1661 543382
1662 1720406
1663 1861813
1664 2802970
1665 1365637
1666 264504
1667 578600
1668 1343424
1669 847563
1670 4365048
1671 863620
1672 1686234
1673 3364649
1674 470462
1675 736772
1676 8123782
1677 2446943
1678 1444565
1679 1906271
1680 449000
1681 4886248
1682 2699656
1683 1215141
1684 3362303
1685 752651
1686 1946752
1687 2119046
1688 102648
1689 317278
1690 303326
1691 665581
1692 1051976
1693 592130
1694 536437
1695 710257
1696 1085802
1697 4860186
1698 5106698
1699 3229120
1700 1500506
1701 3920686
1702 1526577
1703 14566
1704 570810
1705 516384
1706 1436975
1707 3440062
1708 1165088
1709 2192836
1710 1024047
1711 1090542
1712 124512
1713 2577026
1714 443641