1000
37905024 705693740 201599016 168960513 576086021 139470888 239487621 201326592 173039652 676743204 676752000 34873513 575021216 739377805 101974693 608330276 138830377 642787877 67136001 202777093 708853920 538208772 541065893 641990785 240257192 239470596 638855180 605446281 139599873 139856557 710041768 168968193 139747501 106326669 608445101 571630221 542255620 139856008 157704 675676677 27137 138676749 39069832 710174852 638984864 604381224 168181804 134613128 106055684 536879109 33570981 206570017 287273 542378628 672408072 206586381 542523437 608446976 541212705 538069641 100927489 537289256 604121221 609640609 637559437 676465189 605186093 604006409 738214536 1458184 138420356 201719969 538061352 206702728 604383756 5521544 575668236 105908749 172368516 33826980 173425317 100672169 202647584 571484845 138807812 235020968 738460293 39067817 138569764 168839168 574892196 235168289 671359109 201719977 168954377 4325892 168951849 637954729 604398252 672401921 205676673 105269928 106195468 541215264 710306464 675693224 239086245 167788553 671088812 101066792 106307625 68577953 541352076 638584845 676726916 33832993 34890281 105922693 205668993 4606088 33565316 608592549 708848137 393261 33824904 570828844 742523009 138815524 35004969 104876717 709126701 772940460 608315917 139485709 672401541 738355361 34734209 67256489 33712804 240525448 739272709 236085764 675545124 71723145 205662344 704774177 1441920 773079181 1206953 743590404 643178536 34873901 739519109 234899501 202377740 205521028 743727752 100690593 202779144 168848041 1329696 71590061 234907820 100950697 68553348 605431853 240394797 672539273 173017093 102000684 101982756 5636133 139724961 33695776 738484873 1179656 604252321 541483136 675291308 710295560 239477249 37765284 236331680 643178533 708856360 574777380 570425985 168978569 106062508 201728684 604399660 5401128 538189828 676479524 38797829 135675937 206981792 570845833 772162088 604258440 169083392 135547021 72499884 135421985 202377728 710164516 239216776 605169828 67266732 172362276 772802561 605299361 201599009 68577409 642787972 38038177 643179169 570450469 537141384 705839136 202377257 575037996 575946881 537018400 575941129 536889869 575824525 236069504 709101605 643170433 236341292 638863525 609626277 609370788 33570989 675424781 642007584 138420229 542114433 642803881 395393 642918404 537027208 639002752 235938436 675291300 71305896 201722529 71314092 202514948 542122633 708837376 39217156 105261089 571615749 17029 609362081 4350125 4483621 704923649 202795692 139463328 239356424 709102244 5530284 1452077 67502756 705046540 570442381 609380868 642138240 71723136 173410436 39059497 710279296 672547333 706084909 171991084 772040740 4194341 570572841 34619528 67267112 67266733 5384741 575801481 139870893 102129829 4221064 33564809 575815716 575023789 638593705 106324613 604268717 38930469 705054884 638740493 642129921 709108228 641884161 541205161 705978504 68307084 704774149 710158380 541466669 236218401 704661513 72493705 605315200 39208960 173287977 168167585 574777984 167919657 705972353 743834277 675291136 672153761 775954476 168053388 637534757 604129448 739401857 672295436 538339337 676602376 240404521 4604453 4221097 538183717 158241 102000685 605299244 704798884 168189996 541213353 672410149 643058217 39086636 642932872 35004456 671091213 638864008 642777224 642138276 575808168 105144324 604383400 676487720 135531176 134220416 709902500 676602496 169093633 202655757 33966085 235160097 676350597 4344449 777011372 775954989 172386444 138438700 609241228 771777036 1075337 105250948 541089796 67250688 773087905 638584961 777134217 637935789 538075692 641991301 637798528 538200236 236331533 676489768 570687521 134619688 37890697 33563140 605448709 33835532 33956013 206989352 138698913 172384809 1196589 201468428 605159945 171991045 135684608 139881100 609239177 641990789 104882336 67127429 637560873 8232 206962852 609503916 139739180 574900257 167791137 537002657 206588461 542517289 704645761 704931973 169213984 202785284 138676237 67265033 536898181 738347173 575694981 35014665 201722496 639001225 570706092 38011433 101058700 236331052 541483168 608454688 775946280 704915468 675547296 205529733 33833128 637954592 608461440 4205221 642001037 134357004 38019597 638863524 239479436 570425349 206585868 5376552 202793480 135529000 34752684 106326568 571632289 71696897 206989352 542509737 167781036 575948801 537026689 704776196 5531648 168960552 296326482 72353961 706101897 542140461 202506408 608316076 168960521 68298789 574906924 240542213 605160068 168829056 206842496 134488104 738468353 604244000 235154053 169230880 676472960 236325409 139610148 609380393 609509412 235012260 743582380 605161517 638984329 72482948 101982217 705972741 571736104 538312869 37880453 710035597 240140964 206702752 642017964 72378885 106301448 643064460 603990181 638722217 33826976 605440161 206569512 71330345 418308 201746568 537150085 100952100 201353900 173033481 38930469 67108993 201476100 638732961 138691113 37904896 671115297 742664192 168821380 135530625 236061189 743571588 641992712 34881576 541092353 5522080 106185357 106195625 38038017 72493064 609361933 135528588 173294208 38021773 239085613 101999108 68569772 538329097 705061029 672164012 4606633 172368005 206848512 34619908 201736872 102107169 206856736 102129701 105005580 239214637 68291108 100674181 604110889 537266212 742793224 5267456 272557 738599084 638845484 574646784 33825320 709904420 739508781 236208172 173146272 169083041 641753133 39078437 705694373 202514980 38822024 571867685 705956384 671238153 173301773 239356584 33581572 173171333 236349961 134348969 202777093 205531681 609239680 1075713 138813477 4219433 202647584 575678624 608305185 105916460 571615877 570821257 33685645 638609921 236323488 105015941 173154469 205652005 235143685 67119757 102000801 240519689 638601740 541458572 135555205 542263812 173163040 202531368 240140964 72354341 742393857 101728929 68575237 5384873 676727296 168045196 675424900 642124417 542122669 2561 609356324 773218829 739256481 605159589 206708864 638591620 571877925 642777773 541458945 738222088 139618852 608583821 168173605 239209128 773210788 72354309 201345576 642801804 72769545 33841833 34619557 71565445 608331909 739270825 642122240 202525345 173304356 1313321 574628513 605448365 637552801 235143852 642123937 235145740 4604069 205940877 676481572 234907649 206596617 201334820 1450125 138430988 101059232 235956353 574908585 5384864 101845000 39217804 642785804 743465089 100794401 206987268 100942349 575930892 138568229 68446221 4605996 571605509 236087341 240396972 605421568 236202144 138693157 608330240 671115276 672286725 239077380 38027397 538069664 772022785 135528617 68553224 201589284 4457001 570687529 575015049 739256329 608578053 135539241 202506793 134629925 743858693 638872192 37879848 637807104 135414445 134375977 168831648 72507937 418345 574761637 605317633 570818565 5400608 675422348 676594336 605162116 67521036 289441 135668224 1320993 105916424 609364137 139864705 169083013 743440428 135678592 235037184 608174760 168960513 33826981 135415809 102105645 101081093 71713445 34605740 34613889 106168485 643178541 643064328 605300744 4481184 138682500 705708684 704921645 72745100 675545645 202646157 72352429 571891753 637683721 537149992 236218505 100804653 605308928 135545345 72484900 709255685 67133608 5384713 235285029 139864224 608577540 173148704 571752608 235282976 708854316 68575269 705824800 4333604 5261865 201351213 1312769 72614444 704800937 167930496 33571461 537944200 239468584 574898817 33825413 638992425 104882209 1188485 4221609 34620073 139750024 236348037 38936705 173148716 641730697 34628269 541221029 637928100 743710857 638599204 537141796 538077857 608305152 234881064 609511460 642122413 5521921 542253737 642148872 638984748 138698924 134488105 106194944 609484845 240403104 206981252 202515085 68575789 205654176 205938724 139591820 705964077 772031145 240124044 574622340 38152836 642910721 240541869 772809253 37765764 675700741 672399496 173146792 738222241 709896744 149504 1196545 738590753 570706085 777390240 609241605 704907404 5507717 206964900 575668776 105267213 138821801 169085444 536873132 570821280 671369893 672557704 201343624 571869868 637823660 739516973 239206400 172376581 5523465 134228649 542247428 67389448 642908160 570821253 1321601 135275176 33835533 38955649 139469348 537282569 236202125 168847521 1460352 576071685 240132777 538077320 772817572 608452644 68298893 138436769 37898921 72622752 638599716 542124193 105121800 205662721 709126825 38824460 205783169 168182437 672530468 68421760 240282156 149509 135276557 4341893 419977 637551144 236323332 709888172 134621221 68166276 72755237 604136108 538061484 605437992 101714061 235031084 240132640 4481669 609501353 541067941 68289156 541065729 135669764 706101792 609632940 710041637 671361581 33826985 105915049 206586409 264868 206848168 604111400 100821156 173416621 570565133 235030540 167905408 106056328 172245505 576078464 171985448 772818988 772022309 100936329 205529740 671369260 4466821 4589569 72485004 604121645 704651297 206587917 538313220 172114605 239224868 570425508 542400517 739641353 538337953 638861472 604258816 675694721 708970660 571605505 173427365 4205221 609501193 771752589 173042213 206989353 37888132 68289024 777396356 642132485 138543777 706109965 67397665 605047456 1313292 202385961 167789089 537029293 38029353 777005221 637937705 240134144 576064013 33819173 240394380 675307684 570688040 68446757 705962529 135424685 704645672 67248648 104884228 4336129 240396972 671228065 206850697 172386948 206848133 105250817 738607241 239477412 1050657 675678248 172114436 172376717
2 1
3 1
4 2
5 1
6 4
7 1
8 1
9 6
10 9
11 10
12 8
13 8
14 13
15 9
16 6
17 3
18 16
19 3
20 4
21 17
22 10
23 6
24 23
25 19
26 1
27 13
28 3
29 20
30 7
31 28
32 8
33 18
34 10
35 2
36 17
37 14
38 29
39 36
40 6
41 36
42 7
43 14
44 6
45 6
46 5
47 44
48 42
49 7
50 6
51 25
52 10
53 20
54 15
55 24
56 18
57 26
58 47
59 18
60 59
61 21
62 52
63 19
64 39
65 61
66 24
67 66
68 3
69 5
70 34
71 42
72 46
73 37
74 65
75 56
76 23
77 68
78 44
79 59
80 9
81 75
82 24
83 63
84 51
85 45
86 54
87 25
88 83
89 26
90 11
91 79
92 28
93 85
94 55
95 72
96 13
97 93
98 47
99 91
100 53
101 29
102 28
103 40
104 49
105 8
106 20
107 86
108 41
109 80
110 9
111 15
112 83
113 22
114 98
115 65
116 23
117 87
118 45
119 50
120 57
121 73
122 99
123 38
124 19
125 60
126 121
127 56
128 101
129 74
130 41
131 49
132 130
133 101
134 7
135 3
136 77
137 61
138 7
139 30
140 71
141 62
142 12
143 16
144 77
145 59
146 82
147 117
148 136
149 79
150 51
151 112
152 42
153 102
154 127
155 99
156 83
157 139
158 31
159 21
160 4
161 84
162 79
163 143
164 152
165 158
166 110
167 72
168 141
169 43
170 106
171 167
172 86
173 62
174 112
175 147
176 71
177 1
178 81
179 82
180 17
181 108
182 101
183 154
184 48
185 3
186 60
187 64
188 158
189 64
190 27
191 109
192 59
193 48
194 100
195 99
196 176
197 153
198 193
199 114
200 96
201 57
202 162
203 52
204 59
205 154
206 10
207 91
208 129
209 73
210 88
211 120
212 147
213 158
214 176
215 49
216 52
217 134
218 152
219 101
220 185
221 166
222 203
223 91
224 201
225 182
226 173
227 56
228 191
229 52
230 87
231 180
232 175
233 56
234 233
235 216
236 165
237 2
238 53
239 125
240 189
241 196
242 82
243 65
244 20
245 25
246 119
247 59
248 148
249 93
250 10
251 165
252 205
253 186
254 60
255 69
256 163
257 156
258 51
259 222
260 198
261 142
262 158
263 57
264 55
265 202
266 202
267 160
268 235
269 108
270 58
271 200
272 75
273 80
274 265
275 225
276 16
277 150
278 233
279 165
280 128
281 14
282 110
283 41
284 116
285 284
286 55
287 20
288 210
289 265
290 84
291 3
292 106
293 145
294 231
295 165
296 31
297 291
298 124
299 225
300 138
301 93
302 216
303 224
304 138
305 88
306 279
307 268
308 62
309 222
310 138
311 95
312 67
313 94
314 71
315 153
316 41
317 51
318 177
319 286
320 273
321 175
322 124
323 270
324 177
325 306
326 114
327 146
328 73
329 34
330 316
331 174
332 171
333 104
334 104
335 137
336 279
337 244
338 244
339 117
340 202
341 256
342 258
343 216
344 163
345 153
346 220
347 147
348 253
349 16
350 301
351 142
352 53
353 278
354 207
355 138
356 149
357 214
358 329
359 261
360 92
361 78
362 38
363 164
364 207
365 357
366 348
367 121
368 15
369 157
370 35
371 148
372 159
373 308
374 230
375 143
376 324
377 285
378 47
379 5
380 272
381 142
382 164
383 28
384 112
385 28
386 275
387 121
388 31
389 35
390 166
391 94
392 42
393 208
394 40
395 205
396 2
397 71
398 324
399 62
400 344
401 256
402 71
403 14
404 247
405 153
406 184
407 383
408 374
409 28
410 397
411 373
412 280
413 231
414 149
415 307
416 251
417 183
418 237
419 120
420 292
421 81
422 146
423 86
424 59
425 183
426 254
427 413
428 85
429 231
430 404
431 416
432 72
433 308
434 395
435 268
436 427
437 436
438 390
439 332
440 177
441 151
442 228
443 127
444 11
445 135
446 167
447 235
448 267
449 129
450 38
451 304
452 79
453 247
454 338
455 82
456 239
457 414
458 75
459 436
460 146
461 53
462 279
463 170
464 324
465 31
466 358
467 140
468 94
469 413
470 99
471 5
472 204
473 39
474 360
475 434
476 135
477 53
478 169
479 104
480 334
481 341
482 237
483 167
484 2
485 419
486 303
487 277
488 394
489 140
490 346
491 346
492 287
493 226
494 90
495 129
496 386
497 259
498 259
499 249
500 277
501 398
502 325
503 334
504 344
505 232
506 390
507 499
508 271
509 271
510 187
511 283
512 166
513 76
514 157
515 131
516 65
517 300
518 306
519 422
520 164
521 201
522 106
523 2
524 419
525 7
526 271
527 248
528 165
529 26
530 34
531 380
532 55
533 448
534 256
535 298
536 173
537 73
538 209
539 135
540 263
541 450
542 441
543 295
544 536
545 100
546 240
547 343
548 59
549 98
550 39
551 300
552 424
553 32
554 178
555 371
556 217
557 550
558 121
559 66
560 115
561 263
562 149
563 334
564 344
565 394
566 333
567 272
568 319
569 11
570 49
571 382
572 334
573 160
574 296
575 569
576 297
577 421
578 365
579 360
580 448
581 121
582 561
583 99
584 534
585 270
586 229
587 557
588 246
589 572
590 296
591 150
592 74
593 277
594 258
595 368
596 459
597 67
598 367
599 35
600 542
601 298
602 596
603 503
604 438
605 571
606 231
607 478
608 559
609 208
610 290
611 58
612 261
613 513
614 90
615 52
616 354
617 23
618 16
619 598
620 466
621 295
622 134
623 416
624 446
625 212
626 214
627 378
628 544
629 164
630 94
631 515
632 78
633 188
634 102
635 518
636 554
637 277
638 164
639 569
640 455
641 539
642 528
643 565
644 555
645 609
646 567
647 574
648 283
649 388
650 136
651 532
652 44
653 270
654 641
655 21
656 270
657 352
658 16
659 627
660 119
661 439
662 498
663 362
664 126
665 123
666 12
667 157
668 58
669 446
670 504
671 426
672 401
673 153
674 84
675 76
676 324
677 455
678 58
679 254
680 569
681 10
682 128
683 584
684 251
685 591
686 483
687 290
688 75
689 307
690 376
691 152
692 302
693 179
694 231
695 79
696 365
697 158
698 685
699 572
700 624
701 171
702 257
703 224
704 514
705 5
706 564
707 213
708 536
709 187
710 170
711 434
712 654
713 362
714 646
715 404
716 345
717 629
718 212
719 9
720 374
721 45
722 56
723 174
724 252
725 458
726 243
727 160
728 192
729 46
730 2
731 676
732 194
733 383
734 522
735 332
736 698
737 643
738 443
739 535
740 145
741 606
742 151
743 608
744 571
745 597
746 337
747 156
748 275
749 379
750 216
751 469
752 313
753 52
754 232
755 562
756 620
757 298
758 612
759 577
760 377
761 704
762 417
763 75
764 624
765 635
766 356
767 408
768 13
769 57
770 597
771 497
772 107
773 41
774 719
775 203
776 748
777 512
778 187
779 140
780 116
781 558
782 215
783 557
784 218
785 211
786 465
787 343
788 674
789 287
790 664
791 353
792 74
793 6
794 378
795 4
796 224
797 252
798 539
799 76
800 496
801 518
802 545
803 792
804 675
805 716
806 415
807 728
808 68
809 327
810 461
811 9
812 619
813 192
814 764
815 649
816 314
817 32
818 52
819 713
820 289
821 404
822 460
823 417
824 550
825 338
826 617
827 812
828 457
829 738
830 269
831 544
832 201
833 201
834 533
835 602
836 733
837 382
838 24
839 313
840 236
841 295
842 728
843 428
844 249
845 328
846 768
847 449
848 496
849 367
850 723
851 608
852 138
853 437
854 794
855 193
856 8
857 504
858 239
859 560
860 591
861 402
862 121
863 709
864 182
865 808
866 156
867 245
868 305
869 406
870 744
871 713
872 233
873 805
874 249
875 442
876 309
877 720
878 866
879 737
880 106
881 599
882 737
883 743
884 15
885 356
886 229
887 318
888 107
889 622
890 73
891 73
892 456
893 523
894 791
895 809
896 119
897 790
898 356
899 29
900 136
901 856
902 430
903 673
904 681
905 659
906 734
907 564
908 639
909 733
910 44
911 802
912 614
913 674
914 870
915 799
916 575
917 894
918 295
919 907
920 852
921 374
922 75
923 668
924 527
925 418
926 601
927 765
928 829
929 900
930 477
931 157
932 762
933 627
934 388
935 864
936 353
937 337
938 525
939 279
940 232
941 906
942 925
943 491
944 369
945 527
946 221
947 70
948 874
949 184
950 597
951 689
952 424
953 453
954 668
955 123
956 473
957 280
958 640
959 190
960 765
961 931
962 900
963 333
964 43
965 779
966 252
967 747
968 659
969 15
970 624
971 224
972 669
973 407
974 517
975 745
976 583
977 474
978 107
979 836
980 771
981 924
982 908
983 853
984 884
985 551
986 837
987 876
988 602
989 191
990 465
991 396
992 813
993 913
994 577
995 566
996 649
997 884
998 190
999 444
1000 68