1000
439 531 808152477
839 531 819935379
570 839 521767092
508 570 150166939
833 531 837036223
88 833 35109045
835 439 346071903
823 570 115306195
218 508 399344169
873 218 203044093
906 218 265283497
445 570 241934904
461 508 132717793
650 873 541705914
840 906 358069225
904 833 225617544
871 904 179204049
148 839 316210497
357 833 228847425
585 439 506996482
799 585 421951929
642 840 141943525
988 839 421151078
110 445 907489123
690 148 883649901
627 445 407628773
808 823 756484695
289 642 519031290
586 88 748811395
86 839 562875843
302 461 278209536
810 650 229491762
787 810 240033014
271 988 873790523
437 271 868467816
458 461 368588631
568 808 117372608
648 839 617778614
433 289 471710845
221 690 986072601
951 302 747058496
318 690 631478034
44 787 779985656
185 642 551034263
487 508 354759532
631 799 694223306
526 531 258805172
652 487 723555103
969 461 594255909
348 318 371624194
379 873 367438445
991 799 613181881
859 487 938505736
479 439 663190154
941 991 191236402
429 839 715654941
3 289 626880039
339 86 135605819
16 348 834822331
776 969 130617703
651 808 517848889
66 690 594206131
681 526 948601217
498 690 859702654
933 991 986510590
108 357 101251402
782 526 625926013
303 16 830861189
768 586 37345939
202 651 415832788
641 799 902611983
297 941 863247067
752 641 203181295
291 652 393816613
22 379 373450245
386 650 520774546
944 289 347893120
496 108 443845611
371 840 469603110
101 22 846263948
691 904 55805634
163 944 693456931
525 218 328306199
813 202 125662216
258 185 11645038
373 823 837565962
201 568 970520247
107 373 899382344
43 318 695048192
382 941 994096798
29 289 363071965
466 691 133652027
817 43 452242755
438 631 432869632
838 508 86910609
617 651 170041985
227 991 368158706
552 823 772087149
506 641 68727152
178 691 566610397
583 782 38692323
151 258 33799882
257 568 473357755
657 768 328970854
564 570 595212866
881 525 412508000
638 833 150874444
697 991 319088694
528 697 447585139
392 297 260107553
191 651 24174072
367 638 581688385
667 526 48511445
829 151 728052931
349 386 763076371
856 506 258546882
527 525 211323547
408 88 703221728
814 379 119552491
176 617 729569308
401 856 497418670
837 382 910370831
887 697 674450288
366 525 405961034
783 552 771591504
412 357 317413910
699 318 548900105
644 627 459298848
453 401 597522725
380 667 637079407
857 29 637974742
353 382 681767865
983 568 509767754
244 871 744560523
612 648 974031641
197 429 436403619
287 218 507452403
739 289 447422840
745 3 713353801
517 829 996225133
744 768 178441908
762 525 630725234
802 437 770304128
118 201 207800278
884 107 820413028
763 650 695781306
720 257 632932830
215 652 835375534
454 739 267694544
177 586 778283624
877 525 7199874
718 564 535613897
738 856 32767254
484 163 401373578
759 202 600354556
209 151 296675077
501 392 77947478
761 763 328188101
619 887 629982370
92 22 1062477
539 221 167146554
114 799 357924165
304 906 169354976
464 641 950105065
905 110 413102399
467 108 265835777
781 289 316186348
792 429 506821501
323 118 141187425
288 877 677553528
811 176 433409484
994 209 214941818
486 107 839315885
789 3 206652293
868 163 445550560
636 744 110528051
757 585 480350031
47 814 884599391
189 215 113130843
950 479 386992611
537 642 905711415
219 461 197407345
96 768 704135555
483 496 160197970
269 881 999757357
751 531 283486770
145 690 298986741
300 88 787469599
559 353 307489512
522 303 252918017
468 941 275580040
940 627 416297309
55 585 840732961
615 454 433126845
105 215 853312975
637 994 466547957
948 382 425142958
265 641 813967110
727 29 240251282
908 92 727431933
580 868 129149266
251 453 346604543
267 96 197845813
854 691 44724779
395 55 823958454
274 22 488655654
979 586 857413883
141 271 382909294
278 269 63699163
340 151 962900353
909 367 639874958
485 988 409577788
999 697 587094818
920 667 421857310
640 86 892806809
143 813 130822256
465 367 19595693
436 143 363417587
236 999 19355024
228 979 611911309
974 641 730403519
299 3 827327667
707 47 415778421
383 974 204904050
551 401 358242596
523 619 549610030
793 118 651938189
263 768 139654675
473 551 659644933
252 857 239191578
87 201 359899146
319 522 166184296
891 994 663143899
878 641 117857012
646 904 345955843
960 527 648785816
377 55 548455137
682 118 55339056
590 96 981255709
275 484 674755711
714 999 445266373
956 141 379992505
888 799 79540322
225 201 907622109
806 877 868903436
732 969 387240810
469 177 386012030
444 288 467391072
26 269 140516647
384 263 873652098
12 837 852062916
449 551 692243044
624 839 208387696
499 583 783105421
416 782 78758486
100 991 89826168
778 221 46087155
696 768 373645228
249 859 800395620
170 380 962686012
607 667 591336170
618 96 450353928
405 439 582253074
747 392 271470325
200 47 216058521
779 948 729426273
709 483 509456075
19 96 701591534
597 691 420629813
519 178 654902784
581 618 583650185
89 416 445323040
939 437 198241831
213 835 969962458
59 227 463217550
23 650 999039850
914 707 546317236
39 392 546372039
509 278 689298788
435 877 219341548
128 267 239872493
95 437 545137915
440 714 361489974
409 218 837717871
327 714 661051164
372 941 192133963
592 650 532906886
510 395 801188969
369 461 212390696
64 811 712800989
8 570 20768465
828 720 290866613
192 859 413879037
324 251 208585597
330 274 10717125
15 372 373817841
968 16 130860106
74 590 682248266
885 759 767219477
945 525 203278714
171 856 24331475
11 641 899119642
632 289 289080417
492 66 152824844
370 835 511660230
942 506 882180184
282 699 307089583
183 271 156101438
554 267 393004801
532 499 449144295
512 948 139826149
233 885 755619103
281 379 328906538
513 747 750293093
591 525 567935271
474 612 846489518
664 289 499784389
924 469 436367347
846 473 105798236
549 888 569896077
865 537 426364822
79 233 583113532
48 696 749927178
195 617 126492107
503 763 600866850
614 854 786967489
812 278 125309819
959 11 661410112
343 377 951058007
556 209 557921992
819 143 387592807
845 39 529164018
542 392 406325817
683 914 832227104
557 384 473215753
978 738 267577220
430 22 333597914
990 195 990267637
862 107 38430086
310 752 373174534
830 570 332715776
989 732 125018253
28 652 676871722
794 752 97705788
232 939 201632757
689 278 382600537
231 380 792454678
716 783 964362868
986 265 852628575
952 324 73283122
753 324 486346087
626 512 221775749
135 865 252173547
109 383 976554154
152 510 300928702
633 591 492196103
600 839 215714191
893 802 547822496
770 379 512515785
928 885 11697651
800 151 905534349
982 888 181747362
599 412 190666502
398 557 765740696
112 487 775321887
149 370 156683548
826 828 874616717
85 499 646606860
567 151 588794167
604 251 851118435
620 499 974384698
378 568 470833977
285 944 79156504
254 570 685197498
365 974 972713924
886 218 620959522
25 928 239318408
661 585 544951287
932 799 398929050
156 747 118860535
936 178 614382807
769 689 486035630
610 510 321453960
919 783 693575891
180 249 844544140
804 526 624912727
875 800 954055181
6 89 723739888
264 932 595609018
788 638 991712700
394 506 22485226
296 956 792267255
704 409 181307423
354 274 811650768
125 282 897641827
995 859 22400879
660 871 647608214
279 727 495263570
726 11 952786999
396 408 550661142
75 503 721176179
870 865 103950065
957 318 781752245
735 624 648667898
958 438 878615100
322 3 356095839
588 632 405229787
772 933 512049736
543 817 885432854
520 512 295676171
242 510 303255115
446 370 700308390
511 854 726742472
679 304 707121665
194 366 150508824
987 467 328801669
947 607 567880378
595 564 594138136
360 794 7253071
741 813 547086662
308 607 328734900
674 727 446030382
594 974 902173657
596 999 99896495
901 453 225932864
345 380 503954615
913 128 679288078
119 908 189215269
698 624 167309485
385 296 716354066
290 664 258686876
166 944 871633948
670 310 329576577
533 596 513292975
317 278 930184412
45 913 831148971
245 322 483579522
863 55 901981316
414 382 221827210
298 650 785769760
208 429 674422315
943 289 728208290
255 135 132287257
541 445 899064495
407 839 439336434
351 513 794053227
750 118 667228380
630 446 984099598
293 412 138152291
654 433 167256093
375 367 522642243
773 667 199080280
391 596 376888929
261 994 356416030
388 254 986252308
574 249 380629690
493 667 949977773
894 88 956687048
448 12 846302306
20 440 301669512
295 109 385651137
623 617 960659880
514 590 857308484
165 793 805007523
524 914 743706567
930 385 242908659
42 448 393910019
972 322 613926163
475 783 568826471
320 245 671183976
1000 386 926889077
765 378 415694934
535 15 538566650
272 528 86736335
355 868 129311579
406 552 475806774
836 287 279400019
338 543 55047979
796 924 680664142
608 6 598545765
953 828 236837407
204 474 992989096
13 349 489743397
578 388 531013727
737 802 228881301
222 202 673127440
723 564 702223250
515 799 240318379
748 626 626655967
68 479 58315144
658 85 673900754
677 619 492009378
325 836 769082919
362 108 305408081
584 597 452070964
133 379 238142627
981 537 850992023
655 515 729441388
916 453 323969529
457 689 716573586
56 382 1518342
687 165 395319401
153 839 564767018
478 664 238311692
849 865 640186883
32 542 160943692
305 904 771842887
76 586 355673596
490 857 102456333
266 787 354148127
827 170 424695422
795 405 642051784
240 23 88754262
104 118 925123716
224 222 208901713
334 492 797459746
954 271 695344966
404 318 109883924
589 498 757659477
635 849 754542756
115 556 38404848
425 118 872029743
784 954 959065737
576 408 178347618
692 631 398136049
60 445 562643921
214 994 225102159
984 819 12503837
144 618 631212914
758 295 134316946
844 584 983110691
883 349 643785190
700 26 773683696
565 439 594054920
534 378 15936637
335 707 508370993
555 667 44920248
561 982 153517559
306 386 642940483
962 75 267999439
921 297 744080983
544 800 614640366
756 591 410759261
459 288 636948753
97 888 769660410
573 15 770134498
206 943 441684667
902 279 997841821
423 437 909031182
31 800 914802437
164 631 458245723
946 29 262349040
329 744 223712985
102 395 543041307
550 614 875131625
611 570 897563019
785 108 966191121
342 373 587024343
417 96 220374151
824 840 392960884
518 840 306565173
132 856 925874380
120 340 472233072
175 145 224793249
816 60 678926585
869 362 670160999
113 650 507768341
33 437 371729244
934 68 952980376
482 416 354477471
243 391 519421518
9 877 526301629
403 953 790485388
284 641 696202397
154 537 298501501
61 868 695830677
230 940 523175946
52 745 88655426
775 697 23252561
548 163 911914070
992 271 416168950
69 510 91730229
472 787 914404333
807 592 164272663
93 202 424911950
14 288 815227267
579 306 303240892
622 204 193791568
809 325 113202119
896 658 837028315
504 697 449857731
116 991 142936664
907 255 198681292
538 483 819153827
73 576 90098958
205 881 441535175
736 814 885138619
4 583 299822652
606 377 654126531
805 624 87316903
603 690 505978736
562 395 625394143
477 624 330148083
277 905 141105694
140 263 395088311
390 960 311213817
238 354 206749296
253 603 607246758
963 384 941380844
62 619 131128111
434 692 369902835
673 434 742566286
190 584 956011910
41 761 700029146
121 886 266525266
500 515 276427072
111 943 596301850
529 808 133694202
212 636 153241090
198 979 31756271
575 833 540345798
605 370 254171979
65 394 971155153
949 487 181502467
53 683 323241566
117 317 963740708
918 618 112772523
931 39 212385765
207 218 345167856
780 524 334482030
179 308 821251881
442 805 508328180
35 111 117338427
426 202 322893692
495 633 467298976
672 778 350421573
248 377 770254082
172 43 208629279
286 108 993722294
843 528 116046651
387 579 688234614
733 870 897505283
250 195 22569335
137 261 967878254
127 533 905249360
427 529 486178321
876 916 457081177
307 865 789957140
122 4 76879688
798 11 793849230
184 120 609870578
463 26 474109220
40 512 484241382
237 218 432772127
337 495 76182358
239 780 627975627
481 13 38047421
653 762 626348955
634 277 637884401
722 826 820364845
639 89 47614331
419 250 121546811
571 905 322606860
922 143 144097988
609 300 968841442
818 520 604093710
821 622 683983700
553 963 288763817
123 916 181456047
740 453 979637673
321 527 39282245
966 506 147227218
67 401 185992097
313 324 902571644
710 533 47700127
217 338 63655025
50 859 170703222
867 580 789568774
126 89 293971498
774 844 573999763
139 467 479477650
376 166 622500207
926 436 728159077
146 871 764425420
880 829 74849094
938 644 561878075
656 922 204318798
712 768 637702539
663 295 279361453
37 45 606276798
210 297 265243293
601 531 403485683
5 192 262330196
521 995 119615366
77 737 989739830
491 214 619590690
971 745 758994669
311 739 496217494
169 119 302146136
422 517 125950210
58 266 331949703
38 796 759308905
715 792 658044997
724 300 544038189
852 954 666956481
879 366 903377338
94 813 675769473
168 942 782277368
196 463 62713948
106 947 746694960
142 781 358435119
684 466 804269810
717 611 359706108
49 133 496229019
83 111 633978821
162 579 853637878
703 454 851480097
186 824 627979711
970 782 870391486
892 932 657308888
103 600 866868149
558 648 343701465
455 202 173316574
268 748 620009375
895 689 139975507
188 47 592185317
147 603 878964667
441 123 9637033
912 340 222758773
90 382 218195402
678 239 881663203
882 873 120434942
350 960 78638084
910 116 314824554
754 436 634925632
516 92 112367139
616 249 70117718
911 902 209326932
721 835 787624479
431 440 647321034
460 982 668406322
964 263 974900144
659 576 923969803
897 737 820454078
314 139 903314846
159 395 653632409
925 204 456086572
333 846 745721478
78 50 95621330
276 321 639845780
187 108 997370480
462 295 412550842
131 335 26558378
150 266 334507056
547 89 291717794
418 541 787191370
688 286 791263747
331 222 556782221
505 663 927954108
46 114 350584167
410 28 423895877
903 512 792186816
476 250 7095282
645 295 648061120
260 886 515430799
917 6 11036235
247 784 107463056
262 282 382602928
832 528 371295539
825 908 685541479
71 812 411428347
685 419 343219590
24 630 429208292
797 759 556722909
2 154 817254674
57 684 274988689
199 159 898611673
560 430 617551169
675 733 535110745
708 532 404422879
731 418 663039403
777 387 442755446
965 38 266291191
494 777 254016990
229 957 773802649
280 840 37066614
488 630 163150215
927 66 58656016
270 737 452301562
18 481 654454327
853 62 366520833
80 655 107088788
899 911 741881243
432 437 234303395
181 954 763656235
174 109 181446679
647 495 56409582
447 231 491876145
415 408 685106131
497 228 938410334
157 517 806143058
82 244 318683866
130 148 174718160
326 641 926991258
767 362 286616376
955 521 405823787
399 672 15609213
713 313 196530770
470 87 331218692
450 675 548998046
246 297 191375507
400 93 426348979
649 970 413751346
935 633 852393730
996 180 39391434
10 558 661552359
216 526 467039187
220 646 356141505
686 897 353293990
341 957 101028108
898 920 938042109
743 942 721455955
872 15 109686034
34 991 368849409
937 823 557144884
36 683 986081225
820 36 56584404
393 127 722401911
283 16 295748545
203 689 236059858
452 681 746423753
51 957 966282535
292 580 460466574
725 68 522937478
851 8 71429181
502 293 332290671
764 366 605324974
480 369 820280939
546 71 164501266
358 396 48314249
587 353 142457297
30 918 616412457
27 296 321041190
346 739 297366242
91 403 325522687
211 448 488104320
975 461 383551683
842 414 151918968
273 951 691526291
755 986 391535466
860 937 986463852
70 108 7728559
309 885 534115560
666 487 603544657
730 692 13721641
84 510 358365283
760 700 80866057
693 287 1593315
742 550 71985109
923 8 13810840
235 115 88117473
861 392 877739332
420 116 479324787
368 243 794945856
889 930 25869522
628 163 462089920
7 838 93498556
841 812 328277856
167 539 359916979
421 420 709332504
790 950 700620643
702 798 111370925
451 942 842180154
998 59 862279823
182 180 375589335
160 496 790473708
381 174 320918285
124 325 965282338
241 684 381109184
134 445 652074764
855 962 731076617
676 314 192387099
363 232 95491508
625 560 574772915
572 319 282650586
815 468 686119933
822 91 669545321
771 157 56992475
985 186 897847798
336 134 338954405
424 896 56234738
706 31 795296079
332 896 733718868
17 912 886710369
668 594 897349704
193 724 441553753
402 137 472080346
961 886 732110192
374 776 131019255
428 253 997417802
890 815 455944093
361 849 802370656
850 813 540059688
734 371 221051446
669 47 953304104
973 317 159037833
874 366 955345978
858 42 107764424
471 80 146483401
866 808 927479276
530 833 97586226
234 216 870763282
443 617 756226525
536 38 992164555
98 75 144701864
507 305 302988597
997 844 560611371
621 608 255136464
356 73 353029403
563 797 30027106
929 260 836960297
786 906 914497595
226 871 779151043
980 452 556378786
629 100 101344654
662 444 722363198
967 203 712271868
223 334 680434759
602 776 34991517
582 868 695293721
136 113 45970524
413 327 162683205
1 293 331894607
746 863 228642553
328 232 341750639
21 424 214380478
138 995 13923212
864 8 185067526
301 974 112979755
173 298 359461601
566 912 424302778
977 70 437921639
749 566 280412364
993 58 727609511
791 86 571671064
256 205 284933322
847 931 303694692
161 827 475199709
671 854 2135538
155 428 316158302
613 932 467152690
347 996 880548822
99 789 621125388
577 603 484683122
352 991 995330924
545 499 161304024
711 730 732157926
359 432 951310016
831 378 274689965
915 984 354964776
158 868 466391965
316 361 962619382
728 541 254293849
364 685 891882202
129 605 582619503
397 177 727404272
294 911 349128219
976 622 350235275
705 662 431107411
694 830 619444389
344 60 798068577
489 46 930274775
312 967 296794070
695 267 838526048
729 971 775884456
701 676 263927205
665 138 452929119
81 681 590586958
315 288 258426849
719 425 945614320
411 489 134132413
834 231 759853913
54 452 976817369
680 918 473248852
63 285 255371444
598 171 795128568
643 563 645218838
72 904 490095736
848 665 297426690
456 808 896113295
259 509 327014272
900 864 533069537
801 103 326211774
766 160 105611197
540 456 784505197
389 293 680936467
593 181 566158551
569 231 686626275
803 337 8204737