1000 5 1000 1000
342193948 448026910 68644316 761511684 577068963 776799602 614126976 660759502 258243854 613898142 368575258 801348635 89458455 608459729 669369634 201863593 594630866 781089225 213978379 640173687 320042281 742525519 830693620 900583020 293649535 94883655 261044700 707979709 103940835 632633760 432640062 298651138 933177024 501284378 912679176 362762341 130600333 379322505 23521842 388844187 993220647 244613454 42709175 82679101 853073183 712078809 137059049 300220402 345684387 351037428 940394089 665726668 93562946 771087708 418826042 239728836 718487717 679870742 947708545 674944907 165020855 232864960 826112399 98197878 734149338 738791574 460960219 864749671 118114078 336998415 106110212 963851080 581611869 1335741 46530180 287201405 713414551 36105583 587421807 59098937 387143012 380332249 577341960 480705958 3936310 996168002 720434794 722424028 528555097 520659692 249885288 693575952 753524652 75997686 791773830 340190343 667305614 105250403 57456368 637936046 294765172 163566580 454303479 876377042 164902321 353350014 16094800 730833226 389455597 456032962 642448518 776598609 836365211 72306831 109820921 840301522 68474832 830255715 415241903 449546283 203431761 665127191 143122234 956956413 593641231 787412418 297146756 113463198 892662821 354603124 603915598 39944347 370686058 58219077 916321389 535588379 411569091 784932543 118937959 801024688 240965504 761386477 430139651 77330715 833693308 539960572 770148591 754684494 222732640 185390493 204230776 426164401 703034038 199869364 383120814 149191622 987281782 532783924 262654820 732460957 887387048 866570418 772405304 110589459 777305849 541243046 646177838 41391293 326175588 765115797 842415982 419657447 379018627 125071986 349504516 212711934 665032558 119653106 967396428 887765198 157559953 24143557 313929599 860593991 224012921 549566767 9785612 63811057 82350690 124956786 796272014 822254092 991527204 568677317 932843551 621349407 109920362 431537742 662740700 288612304 49169893 357673035 708269751 428188520 482745021 57774266 640900455 147777578 29943726 460813236 35542776 187503679 337473148 201988729 48097669 561486069 751555496 910399636 625297126 686422540 35356421 274085493 508676631 879399980 842762810 294036535 500749386 805199526 725574277 16006439 946328185 774744170 373679475 507114289 202932690 856424496 417404910 696349499 4202074 447348636 9679088 892261205 487368670 347152236 946766288 387982693 908638306 550838137 298382329 386451785 237260676 186255104 660537279 598453661 65655083 355816442 892490196 418920823 13532322 618064472 434927263 959860507 245324996 808606738 319491149 448257686 665031233 736896059 144607184 521749661 36761049 6802626 266527219 524129719 353954863 65809860 912112412 115109522 616647997 63011094 501561307 853908673 249266199 14614939 304878687 314921282 222947736 197368882 733842106 236480058 667949709 21285722 48856918 913274705 829892460 368348067 214048744 347440046 105244126 211172282 869189708 142005175 217974908 988233281 518651248 571929771 54043141 430763659 687039293 670691138 493774754 41116954 377116165 743040953 55731893 681994852 910478589 278679629 731880089 496837048 367676041 399829797 518122770 416532959 165620855 348015229 637397381 379669599 695455276 595157861 590841881 417161337 589679390 808816789 257910971 108330637 380746560 311954112 391610650 67785852 835161605 885385404 108902806 64794123 480942710 17151054 746788975 243937653 148347037 331185417 740774701 516023079 731015214 258897471 932556038 896636069 459429054 422469772 128822021 7400683 17627632 719663902 424562020 607307022 528480691 682472992 568154013 761743605 846943458 959764664 682045811 682105062 697666421 643464972 746899185 31125485 660616026 346204514 275063138 808963063 677389931 15837838 177502495 260921499 127251663 110058533 10073921 586680718 385044659 138895943 594081401 402672292 858559845 18643421 862495668 239556889 553632767 430649681 1300493 253092578 242930698 535862659 935197641 940597119 179327630 534613179 971722604 692460010 733334047 246785741 353939426 263240332 115139934 531441922 524161831 242391597 494016809 386752106 829072315 879061468 525648049 423153716 134250113 236724248 294313491 996745782 328797491 700462612 279911816 182614339 953555190 522842514 718476998 741269184 463439632 897804628 128398717 287678590 442780991 861732764 534464331 796720417 124973095 649604265 328162338 501651280 891995863 822179147 888403387 573584531 553756969 266567789 996738247 688007082 503292037 143568091 684752863 832089529 844030703 964664679 14703867 650102247 340023546 585697219 391371430 803463179 336018200 519770147 91141768 778799191 234019265 478122453 575519607 358992360 980243073 756198300 860643641 724755289 430893800 601563381 298339819 984650769 868131170 147594420 672657851 223939561 143678865 209927067 56029089 987709569 27108100 923249311 490328169 367131646 361462883 881699599 23111178 697481083 253986100 966769301 476280273 488005365 297408108 904316234 699514079 277651180 660514533 412674073 2406468 91408333 14237453 153262641 928575456 882368624 153373415 453749660 106308184 297052281 663676728 14853627 137278203 543301182 790619292 627606372 910432828 4598528 361822324 786060361 702079611 615808424 752829661 30876237 956330143 50237768 935192471 655844222 180405302 448223358 68518294 35328124 392148045 935272103 41107120 320723500 670157080 194480535 774473161 628981618 491532816 290666242 496351599 628811019 833967424 139487244 256417390 596916605 144085772 618239715 235493319 846165383 86564492 988322981 877041620 42894635 891077103 812234090 551255211 923998760 112973801 472289859 959326884 505121846 260078315 434003 825845347 930235395 47430893 452834861 559217012 538963709 596017457 55568610 167774728 282501234 47572208 276708472 879417839 191657980 894948187 114911158 37823362 834029034 955750493 914864982 729440023 699343949 579615426 133211587 475859062 692589227 605501446 287702300 50227427 865579762 140652657 876072774 648331510 188083550 181423988 60064876 727047260 777441445 115633486 894821988 59942678 15722049 24046813 791876871 207380029 918995001 759304383 245203392 605540388 567571229 12584727 334980410 119431532 444716507 468191997 595290594 137305734 926209797 882992894 40049515 644305912 23645551 916122289 292637422 64245455 950062631 352702298 791292715 580020429 320852138 538631056 492479461 336574187 562677870 136872685 543954217 334189224 896177069 641673963 939729612 316264651 654258690 127226375 288212537 98975197 595418372 883503132 88797285 374144522 619012379 128846800 18450434 495174284 897485443 163604210 559419740 700064427 516306508 203228808 280084855 689675000 741859865 772564316 26249187 304537734 909437001 422719758 638726958 658130423 64393720 430972923 826911429 571168764 558199298 115123965 522660315 6134023 851143451 463973954 380278545 322672184 445337108 398728979 817846468 195338904 562333189 229782561 895403331 931156051 433011370 28004539 620831051 27387588 653085209 499596592 331925322 415038564 774832704 823168634 73168986 691742778 254141556 752596769 115427895 812340854 867720735 638088211 818474877 571380539 954578519 51269775 894052723 252431981 449998755 564415545 447770885 864848298 794198106 195690570 796004349 79725829 76211463 269351753 107113417 729296673 621464699 291555093 144335236 396297402 114723726 70020576 88040179 221381636 822617346 55984428 33722489 542854434 694072639 704713720 114234972 501167512 755983496 860804050 753599493 58498604 425219594 53886731 923346902 71934053 249577301 571867604 4176237 325788765 693735711 111289654 55085437 315200409 402844748 51937027 564014165 370084828 121957603 504570698 591466465 797091303 560555127 477705308 192462090 107144119 34935382 159213417 608311631 790918878 20017466 361911123 701933836 297753414 415797855 477797091 222203821 517891510 49664695 226380058 843680275 595916760 337669713 751282066 911117170 593030815 655735447 327647688 963115643 630209405 832218387 554582107 279817061 392773513 32287415 472279152 499917632 67222797 484008923 108229263 710658029 356542743 322656740 265108218 654296157 590970949 742905309 876499978 108862459 645086358 102880036 805059088 241003118 293066103 408857508 4636641 886096918 64592954 332284329 701728914 694802359 17019069 108827375 974619421 409792582 141114790 299414926 762226569 60853941 783423849 722972186 624028324 139966591 45628925 889136542 646779102 489116229 484558204 375795433 597978688 129644562 331191823 255554129 223164034 476774280 664411637 227800675 215387551 729004592 412601358 917116466 276323304 429620428 25943840 103459078 839413010 19574984 255390358 454155932 932945280 38814206 177128117 409489957 31297151 75273397 151142852 530592607 564389626 635701056 758904395 14884667 765345618 90096217 270438796 988509652 419386852 934850434 68826680 634774403 516371379 481428039 551890868 645211037 911048467 430351062 748670116 602977830 449926046 4060473 57133762 235387679 895391035 86778233 644877636 779204540 14567984 796020488 162313501 578957610 431721544 921217896 446358631 49583515 863830467 716797428 890609522 135733672 504164215 959436202 770508076 873051948 293380594 174915297 518262984 56945414 605266360 119449453 512439599 55192405 976026282 422089715 143096439 723933670 508867948 787974075 355654563 523435933 583994563 517968064 954909897 868232461 291702313 401268528 917815976 8049134 970582310 660941851 143782806 327262878 472894407 914290882 200314825 766275001 89206179 571094163 675736770 546988893 690543617 188176368 454697652 519086252 610266083 597794091 243019921 971650385 385768166 598674484 347602671 822279083 969158903 302512568 690511543 113377569 556297450 460843872 121426703 526879759 121785723 117725864 854142637 447196484 32016745 906973816 65987838 973739279 478067978 741724608 373244525 21127948 929900976 827942178 540214200 392683412
269 862
151 474
313 840
871 373
391 125
785 248
993 406
953 377
706 772
554 631
111 398
86 716
1 489
392 2
141 211
96 590
421 431
551 413
69 442
950 215
542 940
6 591
930 599
605 460
607 192
441 279
904 436
162 783
843 247
939 82
500 716
99 531
282 455
8 137
778 450
517 462
399 534
208 456
539 459
317 943
29 726
866 962
990 935
542 526
934 967
521 360
517 0
709 548
976 272
207 351
28 755
426 551
952 23
108 860
504 359
638 573
536 744
818 686
884 717
63 302
193 541
606 87
909 271
214 714
32 759
639 705
498 315
840 960
404 981
293 541
726 342
793 864
140 87
140 486
971 201
548 209
140 168
227 721
821 89
935 700
215 219
618 801
696 380
867 591
112 581
361 139
796 684
101 729
766 992
666 296
797 719
607 374
720 958
338 44
980 249
450 616
904 588
612 439
232 177
53 49
991 320
182 119
274 911
77 215
229 500
482 98
309 454
667 543
628 5
626 179
983 769
507 161
497 211
191 46
950 788
425 302
716 3
433 552
595 707
382 818
605 996
202 863
658 826
647 580
227 432
598 806
350 273
153 280
928 723
281 29
293 422
524 340
666 472
999 58
468 377
438 824
951 230
340 542
214 813
952 606
613 320
355 166
360 536
162 517
557 490
871 772
502 598
212 56
704 725
134 969
297 710
950 194
918 200
562 715
629 16
926 977
768 891
557 650
494 27
473 688
867 432
253 149
91 12
242 819
677 39
672 277
653 582
927 688
264 647
56 515
355 883
840 717
967 791
308 201
821 973
864 337
477 788
762 873
583 411
67 257
733 480
939 918
713 726
310 283
707 450
927 472
52 448
889 107
868 996
833 59
682 635
731 812
167 321
79 943
850 377
363 622
238 453
673 78
520 868
633 269
53 598
641 370
31 652
829 285
784 225
942 55
711 178
626 441
518 271
982 668
557 302
303 944
352 551
451 653
664 103
452 738
349 384
527 465
680 24
281 121
370 814
932 548
248 762
313 647
968 93
487 400
344 325
673 870
471 805
273 14
561 165
206 47
522 579
644 303
442 982
20 291
500 319
246 944
214 267
218 834
558 626
60 475
200 736
655 546
562 587
511 606
5 32
738 20
155 603
435 652
659 185
761 818
759 219
259 23
919 72
508 565
887 248
437 368
6 821
815 244
21 196
396 879
748 941
258 994
517 660
204 848
500 25
688 787
973 865
585 449
129 387
75 637
14 491
456 338
956 639
293 720
950 870
708 219
824 217
305 358
12 297
869 441
826 309
476 285
857 40
397 833
506 467
355 500
40 195
246 988
435 858
974 107
581 27
787 542
0 259
98 560
305 261
229 596
877 950
636 466
470 334
424 854
561 488
201 197
296 629
597 235
691 612
821 217
957 669
29 42
405 816
674 202
798 321
546 367
312 398
113 980
919 852
111 971
22 626
433 24
112 792
401 462
658 321
779 482
535 876
278 359
639 843
2 488
560 797
465 155
83 409
7 365
820 408
835 321
782 660
864 726
4 325
401 576
192 586
630 75
340 19
667 590
213 433
769 465
571 372
997 860
516 194
9 762
122 999
235 75
818 867
503 831
718 991
188 275
85 903
638 476
79 503
109 223
679 583
417 883
464 747
609 456
771 970
374 982
167 739
503 66
709 859
511 234
911 741
690 146
871 859
127 4
985 408
947 17
467 352
619 386
131 645
968 478
199 499
149 22
304 518
56 282
658 705
145 946
619 26
271 810
515 433
497 686
338 480
869 272
160 323
441 369
69 940
547 20
104 27
987 115
700 851
125 640
962 631
280 441
457 396
128 981
5 503
825 110
421 89
501 252
887 479
874 98
704 188
929 297
469 880
568 197
663 246
879 443
316 861
912 974
415 572
746 807
18 343
117 495
321 737
373 281
913 87
870 75
372 216
777 928
420 941
362 265
390 401
413 785
754 311
832 237
70 435
294 678
853 398
583 646
382 639
735 509
556 25
264 440
109 395
474 58
90 931
316 241
431 752
891 30
111 225
58 385
653 31
325 873
116 673
32 722
866 884
497 756
77 535
407 870
506 1
419 983
71 971
781 700
170 690
39 505
747 716
815 10
154 671
610 616
401 839
121 374
762 569
394 351
732 763
730 753
683 869
891 414
590 398
608 281
48 565
745 720
449 113
899 467
405 332
226 566
504 140
74 333
319 508
810 251
621 625
346 754
395 178
411 52
262 722
449 666
19 838
810 287
107 837
424 456
571 276
670 779
998 398
694 563
916 795
425 177
749 257
547 633
361 537
481 732
682 737
287 264
829 221
874 965
807 744
152 666
949 878
806 157
919 556
969 184
357 975
725 930
517 448
603 387
935 967
855 244
71 954
671 718
591 780
188 672
844 821
482 547
162 782
445 698
141 864
269 849
512 682
308 790
971 61
612 117
52 734
875 171
961 589
23 302
445 290
304 332
903 310
787 531
426 21
851 587
998 113
769 723
818 935
891 363
693 129
399 463
323 280
220 989
174 242
190 677
158 982
260 363
632 605
821 844
279 125
330 230
154 566
139 471
233 187
466 935
239 753
376 898
140 32
551 622
192 177
933 524
939 26
116 889
945 781
334 978
629 841
206 583
819 882
460 345
81 327
332 823
791 677
586 113
657 608
598 421
231 472
905 383
430 833
94 848
321 737
952 960
796 472
438 388
857 316
21 861
824 732
610 440
413 123
251 840
686 727
625 956
734 926
793 414
903 49
243 812
20 527
527 15
707 316
136 791
215 856
854 712
214 773
358 0
364 427
51 348
812 538
25 789
558 80
766 660
57 903
38 601
557 965
598 866
882 20
180 70
244 465
840 184
202 655
790 853
160 462
322 672
869 941
222 621
517 448
241 869
350 475
356 153
196 87
524 158
40 115
879 421
443 730
447 536
269 510
916 185
431 26
106 129
289 37
432 988
669 751
733 143
656 328
279 102
395 36
282 679
859 926
424 167
232 427
300 759
460 530
283 346
807 520
896 242
423 943
255 696
705 808
816 356
781 856
565 989
250 156
963 479
712 487
116 176
962 788
445 570
984 597
18 313
823 108
592 394
946 505
394 464
539 649
716 168
9 997
848 833
832 262
73 954
255 681
840 717
957 782
992 943
719 587
437 217
629 531
492 748
580 139
931 350
449 470
791 730
633 832
70 340
506 599
714 282
36 861
331 186
193 339
286 462
686 106
806 622
456 728
244 394
536 738
859 93
527 418
796 393
993 827
331 783
713 463
613 143
304 169
446 405
620 178
761 153
160 983
326 361
865 583
357 16
450 936
91 249
571 371
490 324
457 93
768 63
923 891
623 319
30 255
77 289
154 30
661 875
406 937
634 443
910 708
377 281
912 288
689 1
708 609
751 297
705 152
688 698
606 286
208 824
733 462
639 411
475 274
905 225
991 522
505 889
235 848
965 595
55 139
982 234
187 361
282 169
606 329
225 994
986 604
200 876
70 369
311 278
843 574
779 292
109 612
440 485
222 71
196 34
413 115
394 676
264 237
196 426
998 431
434 902
206 676
409 822
178 784
526 125
641 762
561 612
293 318
799 551
759 897
145 35
525 291
124 926
215 994
12 815
94 928
903 181
786 213
633 85
88 261
338 794
168 347
832 114
605 221
681 772
978 689
241 850
366 237
646 229
390 283
499 376
809 479
842 533
418 998
560 409
339 549
589 719
502 46
673 560
757 219
823 386
532 859
591 610
134 169
832 328
952 602
713 382
438 700
709 494
383 974
67 396
871 544
581 418
430 667
833 59
312 750
274 233
424 640
95 706
807 401
435 979
611 896
873 806
56 717
609 733
203 925
865 932
333 680
152 780
405 768
302 952
606 511
914 845
147 467
679 490
289 743
418 310
967 270
653 955
225 138
166 115
292 535
206 252
829 836
281 121
47 391
656 559
676 856
512 679
580 114
130 629
10 360
215 856
191 776
704 773
95 858
548 696
901 653
68 327
817 697
669 532
261 559
607 522
896 936
113 457
16 810
402 907
495 744
356 236
709 293
454 152
283 616
983 160
460 232
619 478
477 635
845 457
966 822
27 328
277 620
395 809
87 26
319 36
26 558
268 727
440 0
243 442
428 164
611 604
102 171
870 765
224 814
669 717
873 640
109 396
541 986
443 128
639 382
211 783
494 156
471 487
258 827
9 492
853 507
279 107
555 899
238 483
218 815
322 68
660 964
593 155
287 668
829 680
502 167
28 941
576 411
930 918
215 793
872 229
264 945
728 979
654 929
951 275
578 100
667 638
408 526
439 452
296 796
691 218
365 315
147 726
220 25
775 965
721 774
855 838
799 969
508 281
902 717
677 800
436 337
70 320
951 230
891 923
833 904
403 867
303 311
491 665
331 956
310 154
618 261
741 168
453 968
223 287
61 164
539 942
949 243
694 802
174 33
510 378
169 728
558 875
167 558
699 373
21 196
904 436
878 677
818 686
598 806
390 51
587 190
862 560
890 254
793 346
494 377
424 662
272 410
839 580
735 795
642 200
430 667 846 56069747
833 59 900 1000000000
312 750 902 165738269
274 233 884 153159426
424 640 894 58388807
95 706 872 24549439
807 401 875 22589683
435 979 886 256130665
611 896 890 29002709
873 806 848 24669017
56 717 922 105670080
609 733 894 159573046
203 925 892 531247682
865 932 916 107141668
333 680 923 129070223
152 780 918 82202987
405 768 909 10031385
302 952 912 0
606 511 899 20015046
914 845 909 101459560
147 467 926 125440890
679 490 866 83645344
289 743 916 121756332
418 310 902 40953671
967 270 889 6646653
653 955 921 509378550
225 138 931 79207990
166 115 896 96584578
292 535 905 277101058
206 252 920 19636824
829 836 908 33082375
281 121 920 103434213
47 391 905 102451890
656 559 910 113695124
676 856 929 89931352
512 679 918 19138455
580 114 911 33339587
130 629 901 659728
10 360 892 59292259
215 856 933 86141776
191 776 892 317683394
704 773 910 34253021
95 858 933 8998520
548 696 927 23891120
901 653 919 509378550
68 327 914 662650
817 697 887 107188439
669 532 934 134652899
261 559 939 113695124
607 522 937 17787925
896 936 928 29002709
113 457 904 2664683
16 810 923 659728
402 907 942 699809962
495 744 906 1962672
356 236 912 42024144
709 293 909 21997398
454 152 939 49860087
283 616 939 9431874
983 160 946 284938109
460 232 944 2447187
619 478 918 179372283
477 635 946 296219300
845 457 905 86315815
966 822 948 136273297
27 328 914 12524433
277 620 920 88119286
395 809 945 40260172
87 26 917 5472185
319 36 925 494007
26 558 910 25551381
268 727 915 121170009
440 0 930 22438868
243 442 943 3546392
428 164 954 497394033
611 604 911 261070066
102 171 936 34498485
870 765 919 21767603
224 814 927 614823014
669 717 957 24415078
873 640 946 52359069
109 396 940 14650309
541 986 955 21997398
443 128 923 5298353
639 382 954 57127817
211 783 945 11018827
494 156 952 29537561
471 487 957 22143946
258 827 962 89347714
9 492 925 15949625
853 507 944 76442156
279 107 950 36030867
555 899 957 48294432
238 483 957 143392346
218 815 940 24865501
322 68 951 176440791
660 964 960 192959515
593 155 947 654271557
287 668 967 33764672
829 680 967 19564042
502 167 955 76029265
28 941 962 230335447
576 411 944 19260902
930 918 968 31344443
215 793 944 6816270
872 229 951 320567748
264 945 950 4906792
728 979 960 120337318
654 929 959 141349354
951 275 956 16540830
578 100 950 264451840
667 638 963 37389359
408 526 968 76618744
439 452 956 135005483
296 796 957 12331314
691 218 956 51040532
365 315 965 478140
147 726 976 37044430
220 25 964 49202117
775 965 955 66218765
721 774 975 13275351
855 838 974 306592601
799 969 971 260124378
508 281 968 135796712
902 717 969 95980108
677 800 961 362595000
436 337 961 96566561
70 320 967 2982640
951 230 971 525032021
891 923 982 1000000000
833 904 980 58607003
403 867 974 23480653
303 311 974 32653434
491 665 980 253879677
331 956 969 55733070
310 154 976 49519248
618 261 979 64951787
741 168 977 26607771
453 968 977 71795612
223 287 974 33764672
61 164 982 497394033
539 942 982 115925727
949 243 978 52155022
694 802 988 270358631
174 33 984 137864154
510 378 983 260825685
169 728 987 120337318
558 875 985 25551381
167 558 983 12686785
699 373 989 81131783
21 196 990 0
904 436 992 574142806
878 677 992 12424341
818 686 992 39097605
598 806 991 109630208
390 51 993 58218742
587 190 996 604614034
862 560 995 29108124
890 254 997 204783713
793 346 997 6816270
494 377 997 15258369
424 662 996 58388807
272 410 998 87412207
839 580 998 26815211
735 795 999 15196870
642 200 1000 220181860
571 371 857 176983216
632 605 656 6920120
983 160 924 284938109
214 714 461 451819963
442 982 543 3546392
871 772 521 24549439
426 551 120 97369097
952 602 895 69999290
215 793 946 6816270
781 700 543 37320471
939 918 218 146591710
214 773 640 451819963
930 599 178 174326243
511 606 610 49670049
653 955 881 509378550
857 316 752 18217384
154 30 772 49519248
516 194 394 15027575
673 78 535 211610023
70 435 596 256130665
433 552 206 92698240
933 524 718 75271223
5 32 374 42972403
585 449 326 296876059
326 361 826 81360786
681 772 884 24549439
238 483 936 143392346
539 649 712 508626093
271 810 505 79975607
548 696 898 23891120
517 462 127 42971265
875 171 752 34498485
949 243 982 52155022
501 252 641 172531914
916 185 730 45851605
29 42 341 221274913
70 369 786 38441188
350 475 640 15423599
708 219 435 124936471
87 26 907 5472185
192 586 523 112109365
214 773 768 451819963
449 113 485 279588978
239 753 588 333113664
555 899 936 48294432
499 376 898 108725158
873 640 951 52359069
623 319 857 20556775
576 411 951 19260902
70 369 805 38441188
716 168 725 8914915
207 351 121 368245501
508 281 973 135796712
56 515 397 264738057
0 259 648 45141667
787 542 446 21089654
196 426 784 0
435 652 395 32540685
26 558 924 25551381
134 169 876 79142843
215 856 622 36492619
525 291 815 16687194
4 325 385 132927481
605 996 426 53828202
985 408 663 468225829
711 178 402 192563724
22 626 540 50102826
682 737 614 270445033
269 510 811 142661976
239 753 620 333113664
53 49 440 295228646
9 492 935 15949625
732 763 478 53886731
807 401 867 22589683
340 19 471 75271223
260 363 703 1766634
656 328 679 568228901
733 480 517 93270831
81 327 632 662650
833 904 975 58607003
283 616 909 9431874
706 772 55 24549439
293 422 518 21997398
682 635 508 551017006
460 232 943 2447187
498 315 468 428008752
112 792 559 358568120
968 93 271 534268397
919 556 723 49202117
725 930 635 174326243
215 219 136 124936471
494 27 373 346516826
153 280 462 295159110
140 87 335 74092518
213 433 660 92698240
460 530 665 2447187
279 125 759 51631187
903 181 878 76892912
495 744 893 1962672
589 719 892 24040460
58 385 598 32534528
928 723 175 661197925
215 856 922 86141776
748 941 622 262326026
70 369 810 38441188
857 316 771 18217384
260 363 698 1766634
829 680 942 19564042
215 994 808 22573261
912 288 769 333034687
104 27 543 346516826
761 153 778 102886311
777 928 586 298085871
235 75 381 4094147
303 944 308 324643743
88 261 871 387930736
5 503 683 7231778
293 422 414 21997398
21 196 988 0
709 859 573 76371193
591 780 558 83087432
296 629 536 659728
746 807 611 610836751
595 707 273 46258740
21 861 699 265751239
633 832 713 35412874
766 660 765 152279213
269 862 257 142661976
98 560 433 24450895
909 271 101 79975607
656 559 914 113695124
512 679 913 19138455
107 837 504 36030867
477 635 919 296219300
912 288 793 333034687
791 677 672 4228764
218 815 934 24865501
714 282 768 95470422
48 565 677 94739726
260 363 587 1766634
9 997 728 151229981
716 3 198 8914915
8 137 78 526688689
426 551 408 97369097
589 719 859 24040460
454 152 897 49860087
592 394 761 84270620
691 612 468 735509965
497 211 213 509977404
871 373 228 51522051
355 883 300 250458231
745 720 494 275186494
134 169 852 79142843
316 241 560 18217384
85 903 468 393190172
548 209 229 30719580
113 980 357 169845665
437 217 738 29556520
460 530 757 2447187
56 282 589 105698108
557 302 444 71089778
919 556 736 49202117
271 810 603 79975607
912 974 520 333034687
450 936 811 99328240
193 339 813 366594786
356 833 700 230780317
180 773 495 1000000000
832 298 848 1000000000
259 903 163 1000000000
450 579 864 6472011
462 269 597 128548978
940 378 222 1000000000
806 703 608 1000000000
979 698 457 1000000000
59 363 515 280556530
661 947 699 1000000000
361 279 767 4304271
857 552 189 1000000000
57 189 649 1000000000
573 497 506 123258224
437 215 459 70872518
386 582 623 20734611
961 605 380 1000000000
921 924 904 1000000000
378 216 846 1000000000
894 984 145 1000000000
945 348 975 346235519
64 314 638 1000000000
253 954 911 184054752
254 930 635 1000000000
760 697 822 1000000000
219 528 300 1000000000
194 364 937 217353364
926 906 554 1000000000
830 930 582 1000000000
29 753 271 1000000000
174 209 674 4164146
149 226 582 47198450
139 665 900 1000000000
51 586 438 1000000000
686 129 118 1000000000
860 721 184 415743929
161 741 211 1000000000
450 611 511 1000000000
4 29 189 1000000000
938 76 114 1000000000
562 702 335 1000000000
236 623 621 1000000000
819 671 511 104247856
71 758 656 1000000000
861 378 912 1000000000
979 185 740 1000000000
515 606 763 3936311
78 121 416 573823818
589 495 899 37465020
131 106 412 1000000000
245 498 98 1000000000
932 455 286 242266617
553 576 966 1000000000
417 531 344 1000000000
425 970 761 184869840
337 309 39 1000000000
430 359 829 186582839
193 201 70 1000000000
609 459 668 649424739
860 347 556 1000000000
272 618 6 1000000000
723 916 692 5420742
9 470 550 185976918
327 661 830 73823683
672 357 620 707169561
433 126 742 1000000000
824 689 731 1000000000
654 507 446 1000000000
76 191 455 1000000000
96 767 243 1000000000
652 312 628 297350645
658 249 946 48489594
351 200 817 70449612
253 836 809 1000000000
83 635 874 411344682
56 975 980 31279888
150 41 165 1000000000
881 877 246 1000000000
679 605 937 1325520
135 719 488 1000000000
378 44 663 1000000000
7 796 562 251500069
953 150 822 1000000000
122 964 57 1000000000
931 206 669 32615946
157 127 714 53140442
489 756 935 249454173
6 452 811 75000516
253 852 467 135806978
190 980 867 46057644
30 902 272 1000000000
45 672 984 1000000000
607 206 750 446678783
429 694 770 1000000000
839 794 873 144252009
508 867 384 21794944
574 192 693 1000000000
509 25 235 1000000000
672 590 456 552196092
139 799 165 1000000000
359 417 252 1000000000
631 474 346 169747011
967 505 97 1000000000
718 864 970 204352396
488 669 126 1000000000
713 992 791 62261286
97 90 945 1000000000
142 443 458 1000000000
729 207 224 352456499
537 429 532 1000000000
702 108 870 1000000000
306 6 606 1000000000
4 640 301 1000000000
101 877 425 470045091
71 964 741 1000000000
549 263 916 1000000000
340 183 666 1000000000
638 479 925 14450664
96 760 856 1000000000
321 439 279 74242193
853 935 61 1000000000
76 868 827 1000000000
34 193 208 1000000000
335 831 659 1000000000
112 199 950 488972210
205 369 306 1000000000
122 648 759 1000000000
788 508 706 87478801
713 694 734 209537346
921 235 299 1000000000
553 210 567 1000000000
966 472 494 1000000000
793 497 777 27883872
353 510 809 1000000000
364 654 617 1000000000
666 38 975 73653556
972 372 673 1000000000
83 29 361 5646240
141 888 145 1000000000
875 437 251 1000000000
175 546 562 1000000000
94 883 949 93371512
940 891 370 70182534
717 495 126 1000000000
527 287 346 1000000000
496 671 772 1000000000
471 469 320 1000000000
144 25 8 1000000000
505 96 409 1000000000
651 163 84 1000000000
254 383 663 1000000000
816 126 857 1000000000
765 827 197 1000000000
135 394 242 1000000000
261 659 299 22363004
959 977 375 1000000000
732 278 776 208460347
52 650 260 270163672
413 598 237 1398386
822 537 738 1000000000
258 705 766 181337582
922 746 889 1000000000
131 418 304 1000000000
328 652 84 1000000000
570 678 744 328241180
222 869 900 21323827
949 543 527 720357326
77 512 3 1000000000
337 803 985 1000000000
927 24 969 152799849
665 611 560 1000000000
784 550 966 1000000000
25 5 138 1000000000
329 585 796 74746979
765 68 68 1000000000
509 898 299 1000000000
409 307 614 1000000000
289 205 981 1000000000
292 615 762 1000000000
629 634 69 1000000000
951 144 282 1000000000
511 246 122 1000000000
477 67 741 57009700
967 433 392 37951805
116 739 614 48704924
184 363 58 1000000000
835 998 804 123012717
449 926 627 7418998
782 796 139 1000000000
896 923 579 1000000000
965 128 36 1000000000
600 835 277 1000000000
722 791 895 68328726
815 850 546 22370744
207 947 610 265066146
822 197 536 1000000000
232 751 872 141042872
36 589 200 1000000000
15 505 173 1000000000
155 19 776 30418157
734 877 329 1000000000
122 970 394 10161336
399 569 288 1000000000
646 115 149 1000000000
192 476 479 123838095
154 438 992 47595403
691 899 341 1000000000
915 603 842 1000000000
115 759 774 60043623
289 416 955 1000000000
417 208 101 1000000000
746 0 847 214153915
492 756 667 1000000000
780 542 654 1132571
282 75 848 6262357
761 529 217 1000000000
753 269 170 1000000000
446 730 159 1000000000
289 401 516 1000000000
415 232 380 1000000000
722 430 978 35691581
175 842 50 1000000000
374 585 521 91542660
41 885 990 1000000000
695 876 3 1000000000
896 942 171 1000000000
113 563 29 1000000000
283 488 803 241534006
794 744 44 1000000000
311 839 574 34695147
43 788 873 1000000000
374 189 270 1000000000
424 11 808 1000000000
298 543 831 1000000000
640 897 783 1000000000
644 551 201 1000000000
167 663 372 1000000000
196 129 341 155844801
999 555 952 302497508
43 138 978 1000000000
969 8 78 1000000000
194 659 354 368249209
817 807 5 1000000000
625 648 697 1000000000
808 283 788 125957924
944 228 776 1000000000
145 12 228 1000000000
517 624 964 1000000000
858 510 846 376054967
162 75 391 4414859
140 267 979 95581196
219 236 942 34209460
925 822 681 1000000000
930 332 718 50316082
979 650 395 1000000000
120 372 421 1000000000
896 437 261 1000000000
124 131 650 1000000000
440 937 391 1000000000
638 323 527 26743407
29 845 632 1000000000
9 292 636 1000000000
303 571 105 1000000000
984 411 904 39648641
702 796 159 1000000000
449 901 710 1000000000
870 998 406 1000000000
484 187 619 1000000000
134 600 394 1000000000
877 788 980 0
404 613 59 1000000000
389 797 708 1000000000
25 283 283 17494481
483 596 141 1000000000
387 103 330 225756324
546 369 287 1000000000
608 62 492 1000000000
14 474 173 1000000000
985 664 295 1000000000
379 148 56 1000000000
360 716 198 67020909
771 73 349 1000000000
831 18 803 161275281
467 810 593 447842155
608 782 85 1000000000
938 303 378 1000000000
577 464 542 1000000000
69 984 190 1000000000
242 430 325 1000000000
538 738 689 152236871
946 952 457 108370938
144 199 615 1000000000
493 487 150 1000000000
648 389 816 1000000000
241 35 221 1000000000
326 220 524 1000000000
56 846 435 1000000000
599 347 712 1000000000
141 194 974 81195495
818 421 263 48326250
507 821 617 43829218
965 285 741 14387240
932 49 697 111445014
82 676 120 1000000000
898 479 151 1000000000
471 282 824 35908891
347 455 74 1000000000
134 776 393 1000000000
846 1 307 1000000000
820 515 110 1000000000
435 184 860 43879872
404 6 105 373185162
146 211 844 691347060
843 377 230 110103714
964 754 210 1000000000
467 843 515 94372900
644 945 229 1000000000
718 244 542 32297585
464 443 997 2352630
123 972 622 1000000000
585 568 754 142046789
797 621 204 1000000000
903 50 585 1000000000
99 623 49 1000000000
329 884 114 1000000000
539 869 651 72403474
407 799 534 1000000000
988 956 904 41424325
531 690 119 1000000000
880 910 507 1000000000
502 758 682 1000000000
608 56 261 1000000000
812 370 987 1295497
398 188 908 9818823
799 185 793 33392647
913 842 849 672186260
564 161 550 1000000000
451 595 321 286644403
355 920 556 1000000000
826 857 618 239787451
333 640 617 740882238
15 735 414 1000000000
277 585 466 370355723
264 964 617 1000000000
524 406 98 1000000000
317 230 822 67405948
518 715 953 358390372
68 807 72 1000000000
389 32 75 1000000000
297 272 957 14581864
915 498 342 1000000000
885 281 687 1000000000
299 241 844 1000000000
766 867 752 49474098
383 500 458 1000000000
833 585 430 101360376
655 869 319 22247256
960 712 658 486024106
33 510 705 1000000000
108 670 578 337391093
65 820 784 1000000000
759 719 358 89496749
446 144 561 1000000000
643 744 380 1000000000
395 863 723 252236789
205 970 735 1000000000
636 343 266 1000000000
955 427 217 1000000000
965 815 205 1000000000
670 867 843 157921871
248 438 749 223266972
385 169 539 1000000000
95 233 629 1000000000
9 495 485 758321662
741 357 77 1000000000
817 509 854 1000000000
552 618 286 169847986
170 398 679 31689339
739 655 457 733081868
297 864 343 103084452
140 574 999 26760662
241 442 62 1000000000
781 311 275 1000000000
410 861 780 1000000000
896 675 383 1000000000
325 256 192 1000000000
179 907 989 815766109
817 495 741 1000000000
497 737 811 86961659
306 858 551 1000000000
2 248 891 15904964
1 727 617 89345769
415 734 438 1000000000
690 131 620 277669130
822 226 191 1000000000
206 38 932 5201066
750 818 577 1000000000
740 910 392 1000000000
481 459 299 1000000000
644 1 503 523712
195 684 200 1000000000
439 664 786 760743556
56 548 505 5547826
494 131 634 215500248
114 346 12 1000000000
657 549 66 1000000000
589 409 300 1000000000
518 104 351 1000000000
911 468 603 7750349
562 160 161 1000000000
66 760 722 1000000000
266 843 635 1000000000
404 570 964 40807408
261 533 983 66265239
247 593 176 1000000000
259 583 576 5619761
326 39 726 442012722
626 589 616 225626254
329 448 691 1000000000
932 349 59 1000000000
445 592 327 1000000000
167 422 33 1000000000
155 566 796 302713793
471 914 404 1000000000
806 161 479 63184989
982 251 563 130118693
558 662 236 1000000000
284 492 780 1000000000
252 370 235 1000000000
944 754 605 161849331
355 650 40 1000000000
34 456 94 1000000000
68 838 903 260504088
216 63 974 479691513
620 262 292 1000000000
451 501 221 1000000000
14 608 829 69340638
603 714 414 101093953
383 358 329 1000000000
971 574 527 1000000000
576 679 171 1000000000
616 711 687 240349168
62 235 5 1000000000
966 256 147 1000000000
292 154 94 1000000000
936 394 24 1000000000
157 124 513 1000000000
338 538 638 173939333
753 787 367 1000000000
82 477 689 362022547
961 518 70 1000000000
133 943 133 1000000000
172 452 617 1000000000
177 49 316 397408233
676 931 988 99874246
771 977 112 1000000000
147 159 602 1000000000
12 136 47 1000000000
2 121 523 4651172
370 201 675 104253422
59 416 50 1000000000
481 130 394 1000000000
614 802 153 1000000000
231 987 229 1000000000
900 750 598 1000000000
888 791 902 1000000000
352 611 364 1000000000
306 98 517 1000000000
353 404 422 1000000000
229 887 410 21947955
904 841 359 1000000000
306 947 793 1000000000
53 633 751 45890599
206 132 886 1000000000
787 703 50 1000000000
385 939 337 1000000000
288 231 772 560951623
652 707 571 198460679
521 620 20 1000000000
944 196 192 1000000000
354 476 422 1000000000
65 134 486 1000000000
210 674 164 1000000000
961 987 425 1000000000
199 122 939 574085889
250 731 341 1000000000
939 507 447 289228458
711 329 212 1000000000
634 333 979 226884507
655 76 678 1000000000
847 322 282 1000000000
621 644 192 1000000000
459 733 155 1000000000
623 829 676 1000000000
401 200 336 70671793
340 36 30 1000000000
681 128 364 1000000000
480 805 351 317881896
693 166 211 1000000000
24 334 15 1000000000
702 194 525 1000000000
984 309 452 1000000000
528 628 237 1000000000
35 780 687 1000000000
711 618 984 7535921
48 848 236 1000000000
430 125 75 1000000000
795 964 329 1000000000
498 508 218 1000000000
61 658 762 326564027
428 48 857 1000000000
953 156 574 1000000000
405 113 750 12578024
994 313 901 1191801
681 742 102 1000000000
17 523 994 1000000000
253 105 920 1000000000
680 277 326 90420727
10 526 425 1000000000
228 465 900 1000000000
343 889 77 1000000000
200 840 591 153923858
774 961 634 1000000000
876 985 64 1000000000
778 178 205 1000000000
880 22 99 1000000000
226 274 423 1000000000
498 495 894 148260863
824 58 863 50097579
601 283 245 1000000000
501 785 703 129095357
579 194 466 127196684
522 385 986 26030734
156 422 852 676014029
572 803 399 1000000000
130 430 315 1000000000
229 869 485 209753054
4 402 336 1000000000
898 555 196 1000000000
113 993 989 92304765
358 936 773 18172802
61 869 462 1000000000
879 229 925 25982659
217 851 912 57896029
421 764 30 1000000000
820 993 731 238388557
487 499 307 1000000000
973 666 86 1000000000
309 212 337 73401359
857 660 893 584689824
847 757 951 1000000000
972 829 940 1000000000
434 717 452 1000000000
359 661 120 1000000000
624 84 64 1000000000
6 166 787 62607035
737 927 442 175689810
397 79 102 1000000000
483 681 659 1000000000
172 946 682 1000000000
65 441 414 1000000000
369 949 560 619592300
309 102 584 1000000000
761 287 178 1000000000
233 925 192 1000000000
298 256 27 1000000000
437 992 701 323507525
879 2 700 208955580
981 125 656 116316536
993 198 173 1000000000
27 653 538 2872407
441 423 227 1000000000
1 817 350 1000000000
938 345 185 1000000000
116 296 996 53704797
308 151 165 1000000000
687 187 72 1000000000
388 340 727 197392696
88 277 866 756631699
96 210 528 1000000000
622 518 256 600504396
160 682 705 232910129
387 528 464 1000000000
89 775 336 1000000000
627 521 441 1000000000
975 134 845 175324319
141 215 37 730312297
213 410 461 1000000000
292 78 867 280470272
158 59 265 1000000000
687 578 43 1000000000
295 797 614 1000000000
353 663 538 1000000000
817 997 401 1000000000
505 369 379 1000000000
946 142 666 1000000000
143 290 641 1000000000
533 85 356 1000000000
994 250 511 1000000000
861 630 115 1000000000
479 705 341 1000000000
874 281 727 6752380
840 66 204 1000000000
378 595 771 1000000000
131 213 964 248789723
511 653 485 35157962
177 348 499 1000000000
170 642 726 1000000000
878 438 598 16223869
742 450 628 1000000000
857 889 697 179645363
551 991 61 1000000000
278 157 779 589092451
835 197 17 1000000000
606 760 409 1000000000
922 212 451 1000000000
760 126 636 1000000000
259 996 355 24510246
338 671 420 1000000000
936 508 698 1000000000
564 6 456 1000000000
613 743 791 1000000000
674 234 967 555007110
805 142 873 1000000000
823 464 910 232937956
584 8 459 1000000000
387 197 537 3069911
23 759 137 37405286
378 58 616 1000000000
798 65 837 1000000000
497 129 620 15511954
305 955 601 1000000000
96 543 213 859662081
415 241 12 1000000000
288 82 417 1000000000
199 279 745 170048884
10 483 832 1000000000
547 761 883 36500462
36 476 920 75364393
653 63 245 48592881
842 694 486 1000000000
462 259 988 13195972
64 187 869 1000000000
629 913 203 1000000000
642 76 64 1000000000
59 716 509 63479572
156 45 341 1000000000
989 908 548 1000000000
224 304 134 1000000000
145 900 871 1000000000
742 926 456 1000000000
229 105 699 1000000000
569 745 390 1000000000
438 235 496 589298573
993 999 891 24014059
57 501 837 57559449
918 187 793 4269768
259 255 0 1000000000
160 464 892 295737587
294 590 436 362767880
517 699 175 1000000000
974 637 729 272633421
25 799 994 73122817
415 289 593 1000000000
911 785 834 55572534
155 91 487 714004724
992 762 296 27406436
