1000
809632136 407240865 407109800 134480048 549855633 939918129 407110433 671490608 134218664 545521697 675545360 415245112 415498649 4326281 943727512 143007760 268829576 4595736 805577128 411181848 684073120 402662304 679748352 679748264 415244456 272892728 268698521 549725064 411050520 281411633 143000321 272891928 537133329 138551432 948306225 281026865 402793016 549724976 402653576 952246553 407249408 281157888 147071880 138813488 411173433 268575256 814088633 541328177 679477913 536870953 549724464 147071121 541205040 813826560 403055401 814088993 8659512 134348800 134619649 537272624 12853776 406855721 407240872 273031984 549462192 545530112 134357560 12976904 12722216 134217912 683933969 276955161 411042105 277094824 952107929 683803185 813826745 12583736 818020625 675545272 281018793 549856049 146932505 541074305 809632264 537142016 415375641 268435864 281018632 671088800 683680281 8389257 402792872 549454137 683810864 679879224 402924177 684073504 939664185 809501337 143000320 809771528 8397472 12984625 4194712 262561 4587577 545661832 818020640 671096984 8781961 805569416 549462409 276833192 281149848 411050409 805699864 273031352 402784920 671088648 411312785 545259552 406979465 4334345 415498281 146800913 805307065 536879544 813835009 679608753 415367856 675545649 272892312 541073840 818160136 411181753 683680153 549593225 549453833 805307321 683933993 406856209 683680001 549855873 805569312 147063449 277226129 537264680 805569168 805446272 402915881 805708592 8369 536870912 813957560 281158560 813965473 402784929 939926048 415638280 138683304 134611592 415638328 411050808 262312 4333568 952508592 671351561 675282984 818151593 805699889 402361 549716665 684065152 12845625 4194313 142614689 134357040 411181736 675553456 12853801 138551441 406856601 403046440 281412153 407241265 818283048 415367433 268829081 143000328 549454000 4334473 134349104 4194320 541336473 809763112 545522081 281281024 813957688 281420689 142999569 549724209 415629313 272900736 818020352 818282912 268698376 272630145 411304632 537133872 12845728 537264425 537265056 277095353 393640 276955664 541336232 138420737 939787152 272760872 805314697 809894537 549462937 411312512 943980833 281157928 679878673 147193897 679477929 406855985 947912744 541467017 262281 9121 281150001 671228032 805707785 545652752 805569080 4456600 268567057 545390864 671228817 541335585 411304488 541336352 273031480 948183857 809771409 671481993 545661729 541459096 8389049 268444200 818160553 537002553 541327376 142737809 683933833 268697736 939663753 939786544 8592 281026713 536871329 683802625 541335736 12853513 138674992 549454632 4464912 537141545 4333952 671350816 671088945 268836888 541073585 277226160 545530673 943727240 273031944 549724801 813826488 146809225 411312281 415506825 272892808 814088240 147071001 262417 809508888 402792841 281018769 671351560 805699880 541204920 142615424 536879264 818290952 8353 406978816 268828833 809762984 142606625 142868865 407249672 146940689 541073849 276963865 805577113 805315497 411182001 415506688 411312777 142745601 671089289 813703305 8528425 541065912 683679889 268435608 134225937 4334489 268837145 8397584 671220497 139808 407118505 813826744 134349073 537264152 679747985 406979352 4333569 675291833 809509040 4203193 12977024 948044576 12984993 407240737 271105 415367296 8389289 134480520 679879553 411181449 131113 8527913 134619656 679739961 142607145 679477784 147063305 671490104 675283249 683671601 407110144 134479880 411050297 541458993 402328 142999977 407240881 809640353 545530144 277087104 952115712 952369161 401561 805315241 813703865 4194969 536871553 671490984 675553705 268706088 134218424 683933720 143007745 415638297 813826232 675554200 268575656 684072992 406847496 142737569 281289472 943981448 406987409 134480552 809763369 143008128 272900664 549585801 545260441 268567097 146940816 138674313 142606353 281149480 679748232 134488457 146809097 545260072 671220633 277095297 952246928 813957376 545399353 948044584 805306497 537142169 268436273 138420913 545522352 805314824 415367737 813966129 679616921 809640360 142999576 549847944 8528256 134226192 268837129 541336072 545390985 675545745 12845873 407249665 268567041 545268273 281150369 805438352 537133336 268567440 4194488 281018417 952500537 679748009 138412456 273023000 537010817 415499160 281158153 138543360 683810864 8790304 671088929 671482160 142869048 4194824 411042057 679617441 281026560 281280648 805315489 272769184 411304872 939786913 948175113 403046537 541073688 541204648 683934097 268443936 138551345 403054728 809632289 407118505 147071928 813965744 403055009 805306753 415367321 407240728 675684616 683933960 411304249 8790168 277094689 138412048 394008 4325912 671351168 268443817 411181584 675676712 549847192 134480680 272900392 536879673 679748400 679748120 8397496 947921553 683942280 138412032 402915496 415637529 407241145 411181968 675684352 281420680 142746385 671220136 407110169 684073000 805438001 679478184 813965744 12845712 683803561 805437848 943981465 675684617 4456873 411444097 142999832 134488321 276832809 146801025 537010841 675554200 545522080 952508801 818160161 271265 8782608 809894184 549453849 276963864 268443648 134488120 411050265 549593761 277094417 537011096 277086641 415498384 952369312 402785057 402793120 818029065 121232454 415630105 805315489 281419913 805438209 138674465 818282640 4326201 273023513 671228305 675676673 537272337 4587817 276832640 8651009 536879497 939786537 281412224 671219720 281026745 146932128 402662160 143008128 549585080 675545128 675414960 4326016 675676416 818283401 139705 138683169 671228160 679485448 276955264 8520464 683671993 947921704 134611336 675291145 939787065 536871441 541336329 805307297 134611256 268575161 813695529 406847521 402924288 939655297 415237025 818282680 134349473 671482376 549585193 134480161 411050016 805306497 549585569 814096424 138420744 146931736 268698145 541335697 541466793 142607025 549462833 406848128 407110328 12977025 805576849 679617177 142737969 805306528 944112145 402924208 281149457 675676953 402653985 143008521 809639993 415638057 142868640 549454769 262969 268574744 813826721 943858232 671097785 276824321 12977041 809632024 805446424 549855673 939926192 817890209 805446560 281026712 545653641 4194361 276963977 541073696 679486232 4202496 281289241 545521808 683672456 679878673 8520505 675292064 545390600 147194041 683810856 939664273 401417 4202880 4333697 415375744 411304841 809763345 549585033 684065585 537002120 407249288 411312528 406987177 939664048 143008688 281150121 406978729 541327361 952500920 138814224 402177 411042456 952246433 146940049 675414432 809893921 415506577 402661513 814088504 146940296 679616568 8651161 268706480 277094913 401441 809771833 143008393 545529857 8520216 4202640 146809641 813826064 549855289 679486224 545259688 536871193 12976521 817898145 813966097 8659721 272769968 393737 952500233 952500360 939663504 411304345 813704073 684073265 684065033 805707905 281149960 809501073 549593480 272638113 134218137 541466760 262185 939926057 549847344 537272465 545521929 813965712 272769425 683942281 4334113 411303993 147063609 545522217 411050128 818028720 411050168 147202568 952247193 809640120 147193881 12583465 276963857 675422497 813834240 549585193 818282936 281289528 138543920 4464785 277094409 683942281 805314857 272769184 805700129 132008 818028544 549847464 943849473 281026865 268435849 537133881 814088496 817897521 138412065 402915753 679617056 813703968 142999728 281149712 939794448 679878817 268436152 671089025 818159793 415499177 805307313 537002248 134357688 818283400 411312513 545530040 671220641 805438104 809762816 943726888 138674688 541328185 407241377 12582944 671219968 138674577 817889297 407240968 138543888 138551953 541065345 134349113 818290961 12722440 140217 406979096 272638392 281019273 818282896 142877601 143000337 406848257 545653152 805438000 134357296 411304249 809771032 818283168 943718680 675685153 402915353 809771192 814088337 411304849 268435625 406987288 679477656 277217969 138805512 270985 12853793 393529 805700497 138813456 268829593 809640121 8650792 393393 537264688 139936 683803449 142868992 272769209 276964240 537141632 12583337 805568913 671359009 809632561 809632153 549584920 411173521 281411585 281419944 545652784 281026689 276955784 809902480 805708048 671359129 8659225 142737584 8659216 411304632 12591249 537133952 671220497 671351040 142877576 683680169 12853920 549847737 276833057 545522585 545522305 140032 411304329 407240744 679608592 809640840 952246944 671482265 277086512 411443752 268828720 268435600 134357561 545259520 138420504 952500512 545653304 272630696 406847521 809894688 138682553 402792881 281281185 809902361 402785169 545267880 671490873 273032121 138806168 948183464 813703480 675684920 406978616 939787056 948314168 939663792 679617064 56 407241001 281149617 4456833 818283176 411435953 675422769 273023273 268435712 813826824 4333968 545653272 12591264 809894832 805437737 683934473 549715984 939795385 406848273 411181497 146931736 809501104 545661224 679748481 537133337 549847433 809771048 679739393 675423121 948044545 8520080 939664152 272630560 146809512 407249840 276955672 281289088 549856024 683811225 4326320 4588304 947921696 814089136 277094936 402784664 805437848 12591544 818159889 4464680 952377760 268575657 406856377 549724592 541467520 272900105 272769928 541335721 813695257 411435569 683811200 805445768 147062792 4596120 134619961 277217441 281419793 142737824 952238497 4595896 4457272 671228721 549585720 139784 809508920 818020609 541459241 415630000 536871200 272629936 138551465 952500512 545530425 147194552 138551321 809632153 537264552 406856096 537142040 415236224 4334376 549454520 142737577
2 1
3 1
4 2
5 4
6 5
7 6
8 2
9 2
10 1
11 10
12 10
13 3
14 9
15 12
16 9
17 1
18 4
19 11
20 17
21 10
22 20
23 13
24 18
25 6
26 18
27 22
28 4
29 28
30 23
31 10
32 12
33 14
34 31
35 22
36 22
37 7
38 33
39 6
40 10
41 12
42 10
43 31
44 23
45 25
46 10
47 25
48 16
49 9
50 33
51 29
52 24
53 45
54 26
55 6
56 17
57 36
58 52
59 20
60 10
61 7
62 5
63 6
64 13
65 34
66 16
67 22
68 19
69 60
70 1
71 8
72 64
73 18
74 61
75 46
76 27
77 51
78 53
79 7
80 41
81 1
82 53
83 16
84 34
85 17
86 80
87 29
88 53
89 60
90 23
91 50
92 28
93 72
94 70
95 66
96 77
97 96
98 72
99 25
100 40
101 18
102 20
103 99
104 85
105 40
106 52
107 97
108 88
109 19
110 48
111 2
112 105
113 31
114 84
115 48
116 78
117 67
118 87
119 72
120 7
121 25
122 36
123 60
124 98
125 7
126 116
127 27
128 26
129 100
130 89
131 58
132 61
133 72
134 35
135 38
136 95
137 100
138 120
139 136
140 56
141 63
142 96
143 121
144 89
145 139
146 56
147 83
148 75
149 42
150 105
151 8
152 144
153 146
154 119
155 40
156 124
157 142
158 116
159 12
160 2
161 132
162 95
163 118
164 65
165 42
166 20
167 136
168 106
169 96
170 47
171 113
172 171
173 16
174 53
175 19
176 56
177 121
178 32
179 95
180 16
181 139
182 46
183 82
184 156
185 70
186 161
187 121
188 116
189 169
190 184
191 12
192 13
193 118
194 183
195 39
196 179
197 91
198 4
199 158
200 124
201 139
202 73
203 70
204 19
205 72
206 88
207 76
208 116
209 89
210 83
211 101
212 18
213 120
214 175
215 10
216 110
217 190
218 13
219 26
220 169
221 124
222 139
223 38
224 184
225 13
226 108
227 60
228 77
229 39
230 30
231 77
232 111
233 3
234 74
235 117
236 137
237 103
238 154
239 175
240 8
241 215
242 61
243 230
244 171
245 216
246 201
247 198
248 110
249 63
250 191
251 24
252 79
253 6
254 65
255 227
256 191
257 157
258 9
259 231
260 242
261 64
262 168
263 232
264 17
265 211
266 107
267 241
268 103
269 58
270 208
271 15
272 134
273 125
274 91
275 28
276 177
277 19
278 56
279 126
280 103
281 119
282 216
283 32
284 217
285 131
286 233
287 185
288 226
289 83
290 278
291 266
292 116
293 127
294 38
295 47
296 82
297 278
298 12
299 140
300 15
301 218
302 110
303 213
304 59
305 87
306 216
307 146
308 204
309 26
310 152
311 305
312 13
313 180
314 205
315 54
316 310
317 22
318 213
319 83
320 307
321 43
322 172
323 81
324 41
325 99
326 261
327 152
328 257
329 314
330 305
331 41
332 324
333 215
334 175
335 196
336 163
337 283
338 41
339 263
340 152
341 7
342 229
343 22
344 312
345 105
346 74
347 1
348 4
349 76
350 5
351 278
352 292
353 155
354 19
355 271
356 184
357 27
358 239
359 313
360 263
361 211
362 336
363 60
364 70
365 226
366 112
367 149
368 131
369 269
370 293
371 268
372 22
373 160
374 216
375 85
376 332
377 303
378 151
379 364
380 18
381 307
382 81
383 323
384 326
385 227
386 64
387 329
388 153
389 67
390 191
391 128
392 212
393 354
394 328
395 60
396 45
397 174
398 106
399 124
400 25
401 229
402 305
403 283
404 13
405 371
406 222
407 188
408 374
409 91
410 150
411 17
412 381
413 243
414 17
415 137
416 286
417 377
418 279
419 279
420 324
421 200
422 368
423 193
424 365
425 156
426 266
427 303
428 344
429 421
430 374
431 296
432 377
433 291
434 98
435 143
436 8
437 171
438 214
439 76
440 24
441 358
442 182
443 202
444 385
445 329
446 112
447 250
448 213
449 110
450 373
451 86
452 396
453 397
454 89
455 176
456 19
457 38
458 359
459 13
460 411
461 124
462 18
463 9
464 165
465 389
466 460
467 305
468 206
469 17
470 348
471 311
472 175
473 14
474 21
475 28
476 312
477 24
478 299
479 106
480 71
481 215
482 318
483 352
484 158
485 56
486 292
487 90
488 124
489 413
490 122
491 246
492 403
493 230
494 480
495 415
496 447
497 96
498 323
499 482
500 61
501 19
502 407
503 395
504 66
505 199
506 304
507 152
508 14
509 132
510 64
511 201
512 43
513 140
514 489
515 342
516 370
517 466
518 338
519 158
520 448
521 291
522 347
523 465
524 390
525 105
526 381
527 420
528 515
529 453
530 525
531 406
532 340
533 362
534 244
535 43
536 389
537 115
538 144
539 502
540 278
541 136
542 115
543 484
544 92
545 64
546 261
547 6
548 381
549 249
550 445
551 182
552 174
553 135
554 226
555 255
556 98
557 461
558 62
559 148
560 226
561 390
562 366
563 220
564 549
565 519
566 59
567 258
568 298
569 381
570 460
571 188
572 368
573 47
574 328
575 43
576 254
577 258
578 373
579 5
580 364
581 396
582 539
583 158
584 30
585 331
586 308
587 134
588 168
589 158
590 391
591 262
592 444
593 401
594 576
595 139
596 492
597 358
598 259
599 212
600 475
601 337
602 142
603 517
604 431
605 227
606 254
607 321
608 82
609 453
610 448
611 416
612 36
613 127
614 596
615 53
616 309
617 339
618 309
619 350
620 106
621 108
622 83
623 407
624 249
625 15
626 263
627 138
628 470
629 324
630 612
631 622
632 484
633 89
634 375
635 512
636 142
637 367
638 320
639 303
640 520
641 12
642 224
643 506
644 439
645 180
646 408
647 552
648 31
649 209
650 641
651 616
652 184
653 316
654 551
655 116
656 650
657 10
658 574
659 200
660 224
661 573
662 401
663 441
664 659
665 180
666 476
667 476
668 129
669 472
670 195
671 377
672 612
673 335
674 523
675 399
676 138
677 544
678 570
679 346
680 154
681 187
682 659
683 299
684 607
685 615
686 660
687 325
688 204
689 456
690 447
691 561
692 684
693 77
694 486
695 190
696 546
697 627
698 445
699 172
700 139
701 516
702 606
703 437
704 226
705 280
706 45
707 472
708 556
709 658
710 383
711 234
712 548
713 72
714 609
715 500
716 325
717 607
718 450
719 542
720 300
721 189
722 357
723 178
724 412
725 366
726 152
727 471
728 692
729 616
730 49
731 138
732 648
733 91
734 550
735 549
736 134
737 183
738 414
739 271
740 17
741 91
742 529
743 154
744 331
745 596
746 150
747 244
748 739
749 723
750 178
751 469
752 633
753 256
754 432
755 210
756 35
757 675
758 745
759 667
760 446
761 383
762 40
763 330
764 730
765 756
766 403
767 176
768 420
769 690
770 521
771 413
772 357
773 310
774 518
775 276
776 230
777 730
778 243
779 395
780 629
781 171
782 566
783 47
784 241
785 757
786 212
787 392
788 379
789 527
790 98
791 531
792 170
793 694
794 457
795 494
796 192
797 325
798 689
799 496
800 394
801 87
802 105
803 600
804 305
805 59
806 121
807 642
808 134
809 432
810 694
811 717
812 275
813 512
814 568
815 528
816 197
817 533
818 70
819 464
820 437
821 764
822 630
823 695
824 611
825 621
826 191
827 586
828 512
829 59
830 739
831 599
832 59
833 659
834 616
835 430
836 167
837 1
838 13
839 505
840 576
841 787
842 21
843 463
844 435
845 281
846 596
847 836
848 418
849 507
850 60
851 390
852 477
853 513
854 520
855 180
856 688
857 42
858 713
859 616
860 472
861 63
862 409
863 519
864 636
865 702
866 570
867 349
868 596
869 90
870 2
871 795
872 403
873 819
874 297
875 79
876 472
877 554
878 81
879 747
880 338
881 597
882 876
883 452
884 317
885 789
886 521
887 527
888 350
889 812
890 24
891 678
892 376
893 642
894 759
895 893
896 134
897 285
898 716
899 829
900 202
901 163
902 333
903 388
904 248
905 308
906 267
907 46
908 246
909 359
910 399
911 139
912 116
913 905
914 143
915 907
916 504
917 699
918 66
919 165
920 108
921 608
922 278
923 136
924 198
925 41
926 795
927 900
928 662
929 54
930 553
931 180
932 107
933 799
934 732
935 459
936 835
937 832
938 549
939 750
940 748
941 209
942 336
943 310
944 140
945 858
946 904
947 932
948 222
949 178
950 326
951 497
952 172
953 453
954 539
955 482
956 579
957 250
958 104
959 547
960 930
961 811
962 70
963 856
964 227
965 542
966 639
967 964
968 243
969 437
970 228
971 967
972 508
973 498
974 334
975 833
976 345
977 769
978 809
979 573
980 601
981 292
982 898
983 731
984 607
985 224
986 71
987 823
988 99
989 587
990 126
991 406
992 751
993 364
994 73
995 424
996 697
997 761
998 540
999 923
1000 602