1000
851 52 493634913
772 52 741723041
262 772 719775034
333 262 910592001
643 52 351124165
842 333 85866591
844 851 813429891
109 643 222627283
391 851 64523540
705 333 180587279
139 333 72889903
157 772 555728381
848 851 575978654
350 844 534331692
733 333 335907109
477 52 838584214
936 262 626141368
438 109 871836882
403 391 970964406
363 733 603501858
308 844 795842919
628 333 965654944
425 772 487816142
907 363 719163192
947 363 437378227
406 52 10511122
734 907 867078928
375 705 763351125
801 936 446921045
51 425 919574809
421 705 573854430
519 734 548519187
445 772 677740970
511 333 319007558
62 406 49955976
712 350 969033769
339 62 159262124
102 628 125243062
457 844 976641958
124 457 704008965
850 628 409876958
764 333 22716087
742 421 448617900
892 375 815637819
293 51 564336099
893 406 332147459
154 62 249785509
852 51 135997292
847 643 814925405
240 892 22963597
661 772 928762319
993 847 392393284
83 511 175877875
336 154 508579034
999 52 108713200
237 102 256622823
159 851 764411784
766 848 600608250
226 438 933181291
68 907 959204762
433 102 750417534
630 293 793794539
146 993 376966364
39 705 545205237
559 705 933512798
117 445 786412721
104 438 443619933
212 993 379363626
478 661 177502167
760 478 229991976
222 993 974099900
800 477 856281958
380 844 415564211
1000 39 147852266
223 559 998759073
426 406 935544069
383 764 797309797
40 336 603506821
144 712 947083757
176 907 365432417
343 102 263902517
155 109 792035983
912 293 756953628
837 155 880631583
381 661 462676281
591 800 35835902
593 51 108051522
656 766 74420260
826 912 234176552
30 51 909378178
314 801 603367288
607 893 105670019
446 1000 689341090
106 314 978684845
402 1000 27472545
14 154 811764999
448 519 372542522
356 83 297827621
370 102 991086297
90 356 871764531
963 336 614863689
916 314 976085699
81 314 666853837
242 40 816888123
973 159 285628644
728 381 63083814
527 51 369615509
611 159 579842504
198 848 117015564
218 643 745961712
315 39 303940218
177 30 290728359
253 705 357933507
151 237 358372743
655 30 789121934
18 253 565027705
697 448 56879030
34 712 489192020
587 628 109462389
20 157 611096993
170 826 402306110
899 993 136487448
923 630 237799423
37 800 892217934
935 222 463077612
156 477 22170673
473 62 810840563
754 630 327216888
539 109 902366160
748 39 802112330
731 402 920599010
970 643 442247462
822 253 255000513
440 772 809018927
726 159 327774776
192 90 490508210
216 473 29644061
444 593 6926632
49 198 133548262
481 842 24332765
605 177 873490008
540 68 283089462
415 446 459048080
500 527 129584917
579 822 586417381
881 444 238149058
453 51 695231230
650 242 742494517
575 237 277403061
131 448 886739669
476 363 821174853
967 766 669062464
853 947 921955282
828 822 503615301
393 62 3413479
958 336 812829378
610 540 310579920
526 237 518863253
910 155 688812498
372 117 98222371
352 350 516377505
795 352 696356004
542 801 754808011
148 372 748783913
856 726 965405762
313 83 982139711
358 999 326075459
738 336 460685312
82 393 374582066
326 967 984837514
797 425 476377669
793 476 162335110
454 326 763681464
773 146 770647829
568 593 739843350
411 198 771871867
872 760 212951013
583 881 515570192
180 433 625372831
33 438 381568099
12 155 197989826
818 34 165579392
758 372 469532530
442 611 780977184
992 643 401064100
47 425 46859681
700 51 916476699
516 370 850536665
332 936 768343472
675 795 236697533
125 758 18783528
757 643 592996113
221 314 279764771
325 81 996622975
50 124 525764193
556 442 978868748
799 837 784992885
395 62 475493731
503 39 139959966
609 973 652902548
153 180 616561361
574 712 538348402
147 539 931804924
701 82 283094897
783 12 456099512
865 630 84025105
986 375 934266567
162 370 438115010
751 656 387084929
347 661 310058524
486 155 691799675
821 542 821011068
77 159 62960408
668 473 951758138
266 402 911893529
484 90 439171830
38 970 776945054
220 212 91874352
114 986 764478809
495 793 315446358
938 326 822757163
975 575 148428093
376 402 65015945
809 757 102155258
455 568 289349178
470 828 749225018
452 170 869453832
823 376 336521784
813 733 130673361
364 593 637329371
267 325 190133739
236 795 486000943
284 226 890756730
140 650 118872045
414 40 194982710
900 90 443935460
304 801 2680113
902 799 358031398
840 156 432161769
955 151 937597792
181 236 69222812
479 47 834766976
419 818 215736844
466 223 554364701
843 675 959168917
560 326 952560379
9 352 977129112
59 336 783378937
182 151 721551937
667 125 157948287
118 801 670791307
231 102 305853322
523 579 861638140
566 223 198135284
940 82 990870914
67 51 220892510
979 609 745750844
885 144 83704671
762 383 614596301
115 381 377688553
133 336 254143641
806 799 380702870
361 607 239962644
718 979 3502198
873 444 574997326
777 560 46022587
494 762 518408199
747 115 30342768
680 993 317487925
382 181 859004485
982 240 371887312
580 216 289972156
491 873 313792338
686 402 525470141
638 935 580112139
625 963 460512174
541 967 157998755
846 159 151305707
256 625 653471026
803 844 242319205
499 114 692727714
94 47 676437440
991 375 391209497
41 51 973195365
431 852 442742426
58 935 77283339
166 738 146618645
474 936 728948296
296 49 230755082
285 222 988105005
786 52 887626918
501 580 361789967
190 83 998289600
545 114 660759591
961 262 307461018
745 220 590277128
244 236 127000269
247 67 727621991
868 457 993950904
725 445 690267353
143 296 215179823
163 182 691622773
135 511 945050234
722 840 229192300
528 444 104005232
348 540 305666273
191 734 183531594
167 975 71098653
557 803 976735251
989 124 951493968
597 527 393843967
152 343 430816508
430 380 545788232
966 697 98454441
202 478 857434462
53 308 876187613
790 853 950622393
721 947 34650256
621 910 275376387
896 242 406446364
91 190 604466704
713 712 371741994
684 607 438438777
13 336 719394596
794 12 485364837
21 143 371310834
201 148 297961994
716 156 959836589
69 218 49887113
707 583 261444514
251 766 442964022
365 77 234482477
987 352 20745024
594 851 524995895
359 540 581719991
627 218 770247383
31 352 634766552
99 916 328024801
277 102 176882299
878 382 981412749
533 523 745295643
483 675 631357920
379 425 766562011
482 198 135046551
652 442 5518345
65 14 382363012
867 370 449872642
877 566 533185174
322 818 855058426
169 966 603697757
934 236 721975105
570 484 71752947
978 33 1971301
974 166 826217870
946 39 446361180
489 143 399599336
111 402 458454358
549 843 42168646
774 867 767966627
432 868 690497384
911 62 22447461
57 139 266389799
128 501 475680953
631 848 525927066
324 1000 280265874
468 559 851461065
405 468 685469030
633 733 837298777
183 403 168738422
860 247 214689795
759 18 494266283
319 851 189421982
281 21 477504464
859 826 654015082
647 712 383166785
320 754 81983531
736 777 505572938
819 356 377856824
532 500 75115075
302 143 710607028
355 523 377262391
929 486 946070349
512 267 816231434
19 131 851869004
614 162 109226058
496 432 129260336
708 747 275559329
142 848 98335072
606 946 944476293
498 828 542505354
863 448 480348594
123 938 394122762
770 993 211797208
943 281 529325801
269 993 378040535
768 818 6652486
46 114 565815589
522 989 808268826
32 647 298150431
78 722 725081421
683 605 361560091
706 958 485222571
812 115 978748688
954 627 176408495
209 324 684571927
119 403 638433620
603 281 269276089
206 302 852568535
224 170 289110766
378 954 953234766
802 30 107657194
214 432 49454620
784 697 932033647
693 912 882066837
215 566 815124694
922 41 723419029
449 285 814606508
493 762 116310622
849 625 715009269
578 481 110840036
295 707 200790436
704 313 136726881
368 570 961451544
303 118 229435120
932 793 824029952
22 934 74435937
789 545 895355421
612 611 714737289
341 760 783218647
394 444 947721476
195 794 272455220
678 631 474593489
543 457 726632241
213 992 192342978
763 364 711222471
981 625 181625630
641 543 856237978
642 963 641682422
815 454 137978594
561 21 527382235
110 900 856539312
136 381 526502864
866 163 964160186
92 974 859432210
558 49 759200292
913 83 771133083
508 140 849389338
717 125 839053106
664 40 243624070
423 376 998921018
901 445 910277264
624 364 924543704
666 628 306260156
880 442 475425443
537 853 566651896
518 970 876396903
487 395 958902034
577 111 900834258
270 847 440264268
676 844 784676074
342 713 287386942
199 533 699960691
458 153 631211514
252 266 403335733
404 866 207341282
17 603 595552009
42 954 34580313
399 380 201273308
502 378 452987161
374 419 234422118
16 542 960121464
608 9 513466874
121 934 640808292
930 166 945620893
56 182 920840873
300 477 949320274
590 736 489851081
492 684 538193204
225 947 513400096
439 42 221952910
665 226 321449824
931 99 273260068
689 772 920858175
836 69 280995895
841 182 108847700
412 342 600659569
76 603 636638011
584 266 647621280
782 332 711158614
29 1000 33294491
870 9 61195091
485 742 810126048
100 763 364401703
517 53 503636491
544 748 916370383
699 46 241529766
926 394 529918511
886 782 677440087
658 423 659172157
909 270 82471313
962 813 767277486
321 557 925511522
291 981 631101988
601 642 557635981
875 78 407395075
698 986 524237467
858 580 411323885
377 878 782717372
927 444 323506013
553 745 339640011
883 293 749183727
193 700 928040063
386 841 292781085
207 865 968771075
480 29 910052634
534 57 573715388
531 766 584332929
765 901 540456399
563 910 872931575
710 782 823227909
388 148 285804899
301 926 347024660
249 489 648820826
460 989 294258687
80 541 531734142
944 222 749629627
702 893 474558229
654 495 780587951
776 700 574352136
316 560 204343770
409 844 497612604
615 80 483951446
976 987 369859785
660 631 504076737
435 962 189149881
688 394 457465544
26 553 284820529
234 117 58283600
636 647 19709417
299 190 404093626
562 650 283486760
338 821 301367804
467 139 19070603
952 31 573196508
750 896 377356014
437 641 83488055
640 686 752106731
306 404 869457751
116 118 556633743
582 277 110733778
581 1000 734149409
241 220 466879494
45 140 22565511
286 750 369610137
753 759 959203520
882 370 931864112
417 365 711506730
462 508 615551396
24 125 239491391
735 803 411627765
401 668 191026756
618 414 900588891
369 999 948640673
505 698 946029952
418 202 965820767
780 590 134786740
690 614 762355092
161 474 747084109
798 169 457438283
305 423 884801698
345 532 107987
895 49 564770946
829 223 779126454
160 979 211189456
396 159 380690076
271 296 813766126
168 704 80827365
969 717 264196128
730 519 618165480
504 49 343012978
165 821 496799285
416 922 834955823
984 372 319085430
27 180 148488011
971 722 432439466
211 285 228708885
671 223 445559324
831 423 181421101
709 411 366267433
287 474 913489269
164 379 111867577
86 50 568592511
288 470 585533427
884 218 319225958
854 213 466272452
898 355 868308734
44 426 268827790
171 650 18149915
422 987 648648213
506 293 197243029
187 935 355629502
741 29 136231441
746 523 698903614
424 487 933157976
839 750 504711884
550 455 425884634
366 699 43788006
463 831 51728019
871 683 260820076
8 527 586213642
921 539 869986237
530 989 862150113
337 269 87720648
634 256 667088874
808 733 658297400
268 503 708098905
456 754 128093195
536 916 123433164
835 146 209622331
328 658 100165765
173 182 973865701
196 899 277776699
282 641 383225577
85 553 131390001
434 42 625862448
97 299 385142501
891 477 752629205
120 963 495413193
939 665 789663055
620 801 333514985
257 650 571137179
681 689 102432840
427 19 70851642
890 932 671648606
949 611 608148517
965 961 75008624
413 65 845625814
598 899 954119072
555 938 554024701
93 762 182224166
510 734 695358770
280 80 593529886
217 45 809942847
830 676 327149847
520 498 483781899
309 421 629439603
997 463 526921133
275 624 660520161
514 176 922506819
178 650 431591344
569 365 546976714
311 333 491656871
197 664 153714113
600 321 171065377
613 909 801109626
919 842 805631505
357 9 397146985
838 784 735841939
995 14 839659505
327 556 346942086
258 215 227122033
397 698 435369522
547 271 94643054
2 215 188607648
816 452 774889709
648 658 765532983
447 327 914001752
185 758 990751216
250 593 715412879
767 534 994024813
775 655 275049590
925 359 742472610
616 404 930416077
820 247 801961902
292 147 738098354
855 643 535248276
385 722 735441959
72 772 570436313
219 815 461573098
330 500 943334613
210 795 896123447
64 543 335359246
874 419 153710016
509 336 815957206
36 613 797553831
420 431 990472272
914 483 994474863
54 878 595299985
804 963 177185348
228 999 399046064
451 678 714854979
861 665 500122780
814 958 488187214
695 86 935181276
384 322 442305086
960 218 395649406
546 927 612166195
107 605 112095983
61 848 271416535
465 790 125620998
719 654 437393727
619 773 720157145
755 747 752635704
565 20 232226478
729 658 643047450
951 539 342007029
443 760 579192647
711 829 568883195
692 76 327881432
461 840 998146868
956 405 258135410
869 324 999628182
450 448 907447786
928 140 57888767
278 142 749345223
488 514 867551140
340 939 227859711
687 217 746716554
261 27 258958786
334 898 977648523
626 847 533232022
535 492 99707138
552 794 686435612
274 579 137018627
122 1000 700380592
351 358 6603301
79 388 705947337
694 361 562429411
235 193 814416096
129 124 636889399
998 822 192006132
673 660 905042970
108 375 801052966
265 979 675482989
11 183 921650994
889 688 743289011
95 676 404274088
623 654 126848355
571 345 653571361
827 244 237560
245 938 906408851
272 523 908402810
942 539 695979472
354 153 274312229
188 30 23862864
824 482 780773065
227 958 964416786
138 831 234249937
950 170 407820800
441 224 530413268
63 115 713352086
635 850 950312770
515 467 56235478
894 195 458662058
672 381 625157902
232 334 805529933
353 119 793961299
679 418 351790804
586 765 683277316
318 870 876551116
622 424 695932219
957 119 774259766
141 314 744085372
703 383 931794056
297 620 755522778
887 44 732168597
771 348 225230410
548 660 460511764
937 800 612705081
294 532 735245535
933 337 551990489
398 764 812379657
906 53 366480327
84 83 126426575
521 690 521041788
204 730 97223878
184 680 33980381
994 195 655948247
696 210 988164762
5 844 544365763
651 536 461809998
186 144 696521889
646 197 955807528
273 217 490060003
617 26 643034734
554 380 624066161
573 84 336393988
817 51 162528581
331 569 989037836
538 532 387382210
335 936 194111402
857 63 848887645
175 476 243778304
663 148 372771968
98 79 373223644
639 570 613932535
73 258 635044505
137 379 197072328
525 975 488005120
724 421 61729026
879 741 79879953
428 519 507306502
208 890 705852730
807 638 224736303
389 183 227466132
915 338 297107695
845 370 609112233
105 528 707663412
715 234 610694807
589 851 290871793
588 683 40807629
796 892 174603809
6 651 551553448
127 579 425672423
238 5 208582805
920 789 105903394
329 620 871670599
408 621 602151413
739 593 222690174
312 227 983230097
905 569 211717900
980 725 531554486
714 42 786342124
941 155 276672131
791 214 494131386
371 21 993667189
126 905 41580956
233 951 33179039
472 906 955120983
918 484 608296082
744 105 691156974
246 450 135510651
4 98 29391129
682 268 369009528
945 835 757217449
264 82 243672088
662 394 64008916
392 80 182444418
243 202 823447500
28 748 967395820
346 425 270005162
260 880 819277753
263 731 607402977
172 840 688801419
436 334 101234367
112 890 101292442
649 772 78388477
471 553 402307196
87 479 772944149
189 455 353023007
132 523 173939089
924 435 121672489
130 963 645393574
670 707 831201561
35 768 401938929
96 144 759940759
203 600 869344356
834 522 156895417
685 336 238237749
645 759 512362440
88 309 162198585
66 539 79723238
749 91 422390921
964 613 392395682
60 823 650789040
674 64 544501590
567 9 562882754
953 501 215645032
732 624 39801067
279 728 872176968
785 124 11551162
888 274 437022589
756 120 587159765
592 519 273712316
113 715 322385923
25 435 673673782
349 182 34915300
145 412 30484662
743 190 435071131
769 397 698683995
23 388 564467723
149 821 771641172
752 527 354789241
787 397 718492490
677 807 76840514
596 380 256461396
903 131 255125755
10 370 591800297
585 621 444764621
70 195 304016549
400 915 701128468
3 56 812025296
897 403 589384692
604 375 875124094
103 6 324457892
811 552 794842514
150 614 943702158
15 321 753692804
788 955 273445633
988 519 980926984
862 675 502175168
323 449 741800923
205 842 350794471
904 574 866171633
259 274 101172771
778 37 129104906
972 60 756160677
825 21 922647608
723 776 526149880
740 519 44978833
908 180 920823240
254 750 587206183
551 845 532100577
833 9 576579262
653 863 6561382
290 206 451897079
737 26 582332797
229 847 180698765
779 99 632132005
179 416 94515327
507 809 165260362
657 949 119590855
996 34 146329024
720 393 481905677
475 348 341895551
459 88 779546887
576 183 737631812
599 716 125265615
344 647 813612927
158 72 312406357
48 862 94007745
497 730 633896848
524 494 497220292
255 894 554445998
55 907 232276715
669 865 551353330
917 915 448484849
985 549 61917604
464 883 349170848
727 22 864661416
239 915 268656319
469 776 866252015
595 383 338669177
637 474 398175902
983 412 357050721
74 458 822160363
805 974 563962917
572 983 34453384
71 840 74577025
629 523 889126066
134 102 206366186
283 813 657215377
792 5 609776839
89 818 858691678
529 904 386927146
387 727 768025497
289 614 562025524
298 597 469527584
781 77 98967664
959 14 941756203
101 617 720041329
659 913 756804108
977 397 809557128
948 181 467843270
310 206 844665030
632 715 713934668
810 15 847888383
429 333 313173063
317 397 769389977
276 807 394521305
7 413 706321312
513 597 332428652
230 133 652120385
367 470 112775797
174 33 424762581
564 560 404260343
832 723 113545203
75 880 96151257
761 509 896999548
1 208 199734431
691 313 150078281
194 530 979007467
307 235 602411801
360 442 299996139
407 468 362904813
490 242 417563021
410 332 740996222
200 445 757482810
876 748 628362194
990 831 927362860
373 348 894278214
390 814 135467941
362 198 538213518
864 469 152436026
43 367 467967692
248 619 872201607
968 391 807143150
644 286 888067680
602 550 344906677