1000
291 754 517861567
626 291 410229920
10 291 336720402
402 626 484321506
516 10 372259571
706 10 450539148
95 402 533142440
275 706 210552638
783 402 230379208
101 95 610056382
940 626 674839986
413 95 832012526
514 940 608851641
183 413 413101304
886 275 823940136
67 516 851541369
864 706 159745554
679 275 864753207
664 886 630390569
787 413 175973560
390 413 21790431
414 514 750006738
456 275 637597496
3 626 797065457
1000 864 97942781
881 679 390252604
119 413 967275116
284 706 656772990
255 390 523733857
827 284 216587459
450 456 124429881
910 414 10663636
254 414 506259797
310 910 927834365
301 291 324156618
142 456 334737085
146 310 202058977
55 940 574520213
701 254 281296732
80 701 411036363
371 284 281595714
332 450 693639953
578 414 789442774
77 754 204017762
103 95 693525893
579 284 170914561
225 514 692209004
763 1000 629378618
558 119 400417017
753 390 943085121
768 706 998009471
856 1000 844431661
974 255 112628218
549 768 745136501
96 578 116622038
359 787 818457435
676 359 616005890
640 402 963124452
164 579 163594199
222 701 146221068
211 768 350758095
987 864 694151128
449 881 579011988
187 706 584175225
262 886 478107807
535 390 691929801
366 332 220930861
548 676 923993238
227 558 322105784
25 664 257469202
395 77 145394694
274 301 303949464
63 414 360381454
848 754 660034955
645 664 51006877
686 284 815685531
788 3 302250311
253 366 772879457
333 864 436736707
614 80 628535258
647 787 98175332
166 449 776895120
865 886 207485788
230 301 648200182
336 253 300911922
42 449 130899331
172 55 581975021
581 864 88503675
895 640 21135899
921 42 682569219
338 284 136243935
868 647 804172117
988 974 880830863
201 25 641604799
437 275 54147517
14 291 926320121
611 63 479484634
85 255 533958375
385 787 130524506
256 187 660147716
18 222 950338057
971 359 407950393
964 284 234887947
807 211 66248073
277 988 489228750
296 275 671674129
129 256 18787730
43 164 223169232
494 971 590306985
20 402 643059274
285 679 617649211
64 20 217291963
441 864 684623311
403 10 880018145
365 626 832987164
46 768 113223957
234 763 222120153
705 222 14253380
513 910 451370864
120 548 679772749
125 85 144598719
990 254 458425631
908 437 86940839
132 788 98049885
743 895 134310239
16 763 72851347
245 848 705567729
269 402 553347661
476 338 988797795
23 513 932019977
235 578 304740862
488 96 848434581
306 18 546409232
197 940 212408126
803 676 296436189
58 230 615321330
898 46 329375650
321 645 965241912
282 535 588032918
389 743 805432164
786 645 444159573
959 611 794954855
431 275 683235161
453 3 155997688
191 686 710717237
206 58 3347008
316 686 385668171
290 336 494081575
830 437 751162002
202 16 712376358
571 558 155768663
845 403 325125864
327 310 980741412
39 548 690020311
312 103 741393039
891 548 967337052
565 132 922182588
396 898 635471656
483 558 929714101
153 55 278186291
950 234 622006712
615 142 124217049
502 365 297814345
412 166 652143777
259 245 572770374
681 502 67254771
652 441 98555683
358 647 400413194
147 783 837694010
196 886 818013444
163 291 709199764
766 172 32207704
609 910 553555903
661 640 332103209
355 786 131199770
577 275 908594482
785 830 783553224
793 766 834598181
363 254 465875738
779 202 766399206
755 355 781258509
648 230 226112781
943 336 309006516
364 971 561559854
616 611 758206977
627 648 784743237
210 987 827259454
293 338 208912780
629 293 686007057
459 259 386555693
946 96 812020509
86 950 103683527
140 921 73001933
193 626 633566956
36 365 669708129
944 437 296433568
369 275 786968583
938 910 319816579
628 783 853617302
88 681 901550851
767 191 680394011
917 119 294281703
28 172 380420490
295 864 729897440
319 3 567547587
447 284 852532005
688 327 147032902
655 64 244832082
438 449 18035674
21 284 911711455
568 129 14230236
819 359 551844574
541 359 478065656
632 819 164986337
342 964 924232450
963 938 666809087
302 648 502063759
352 856 805750503
875 632 942146606
544 86 661400485
675 502 545458567
426 856 474275616
989 163 192491044
115 120 703257822
870 140 695815026
130 222 890239509
762 396 152825979
226 120 997030417
425 227 276625296
667 413 315564283
685 753 182866006
673 85 981385077
466 963 706477264
651 125 499582697
99 197 583444728
200 483 578137593
622 447 274944691
419 291 300881524
659 414 442847829
863 183 66313587
309 275 138869862
182 456 119476513
691 788 868138887
850 352 333459260
517 701 471002065
349 768 289273533
584 369 660043614
997 85 486219056
180 352 749769404
133 706 14749031
214 868 171086056
370 64 47281002
662 676 792354597
34 787 483162567
597 23 111892695
789 166 35824020
127 789 41131847
406 321 279036198
78 336 105506695
487 597 238848560
499 803 644294661
491 95 646766403
5 579 374295217
956 571 918860126
620 488 459376762
122 614 741964714
902 64 989883837
677 688 757737692
15 459 845700007
315 578 185475715
467 259 899700594
458 201 654872141
81 459 11433322
261 254 182605028
90 659 70031310
734 921 348352998
229 494 841604487
690 571 347372818
65 365 172538967
1 450 734116111
841 254 255035209
533 891 244107594
554 441 770174543
337 447 901648536
877 870 827636211
303 365 227122200
583 819 239606855
772 103 921366585
607 447 203659848
926 234 925045624
69 548 881086477
375 701 974772182
606 466 503247047
91 743 58063958
379 541 781856332
271 459 208661609
435 803 754578480
298 303 425960835
587 69 835278875
716 15 191599417
446 3 413741340
13 303 281073348
764 222 815447153
59 513 974138671
952 127 17646626
495 926 873638237
907 132 911630952
524 868 411945690
386 196 382681749
465 202 796729913
932 379 627208628
116 225 669490562
804 254 83041727
519 379 722589074
61 211 61779704
948 568 809290472
885 187 369000115
134 64 41874000
70 234 997481022
826 406 981494203
708 23 192031637
760 295 964592101
860 675 649401284
98 69 429883971
41 628 254411970
347 64 824839796
846 61 498778596
304 78 298533215
503 932 914388599
68 902 479210837
428 315 734224094
717 645 390854765
635 755 217989353
876 763 424213314
294 197 76933197
633 487 606211470
900 230 257511710
451 652 821964874
22 20 920223539
186 68 205134723
114 347 674498422
911 342 917392619
236 675 950269424
562 347 788362366
247 333 533848635
66 180 11347857
324 85 723778058
154 163 439209480
83 193 704326717
75 673 950847210
167 406 737942301
56 681 226061051
485 306 857054041
37 226 176883065
901 358 96306138
374 256 74481030
159 662 828280593
387 635 858412897
811 365 477650028
928 285 918667648
613 629 563853695
280 701 175448632
980 940 593291823
161 620 763547543
100 558 84504334
993 191 123053076
73 206 49142146
730 628 634986156
94 449 219449900
732 22 760393454
394 485 212769832
532 881 639832136
335 61 838194802
638 96 280658913
657 172 22973663
209 280 629046550
329 209 357674376
931 827 216403169
106 153 620957221
852 80 617192555
559 183 168489019
169 275 58689780
831 209 404150749
258 907 427899669
283 688 655270052
992 338 855943976
912 946 421885018
757 1 654998373
404 201 461816580
816 803 763008147
761 932 567615858
204 329 554784028
240 116 575182086
736 783 177567333
325 309 807605092
47 456 94396065
345 254 844164967
155 15 899841466
473 701 45079878
916 852 344262050
12 632 694834389
314 755 162971298
660 793 572078371
542 366 134862525
966 568 446135130
273 754 528171132
220 275 214641887
775 830 672800129
331 134 801799383
550 827 717195670
873 706 770099480
381 61 528996310
806 659 330709143
462 743 262453441
401 775 816651889
781 779 148221043
286 61 448672780
454 352 654277502
598 633 301584900
749 167 635579103
862 524 695636457
267 363 594304244
833 295 259020324
913 227 595880875
653 587 169293500
972 412 77033269
733 465 107798603
410 227 582954603
400 321 205623363
678 950 804824839
837 294 360551375
50 256 537875336
141 786 962663571
540 3 184702850
976 660 217664258
24 734 69851406
195 294 668592662
464 254 469860669
953 187 977021123
729 789 322076349
815 15 422845847
617 535 993084772
572 134 752269075
697 449 103851249
592 310 172325494
299 229 30700568
144 64 758970947
102 258 266747545
162 283 763032386
758 441 814764788
361 732 374893839
380 673 885118734
105 768 780077070
279 675 425460133
113 626 852662016
348 783 202787626
603 64 274223815
264 928 263648737
813 606 159879152
712 873 528743948
752 458 263607769
719 3 33479067
53 592 770877514
641 314 841938237
537 13 666547974
668 34 107663144
720 862 53538957
923 172 353137932
469 404 804697003
268 993 952008895
17 73 393604353
31 846 44748537
528 542 119741240
212 850 100244958
468 811 719101171
630 453 731549392
397 729 373175137
991 514 96760022
839 337 966247968
74 419 979725842
112 609 274034714
126 214 922194116
999 220 421561513
189 36 564138754
958 677 119533686
982 226 233177344
994 264 434532457
430 256 649672893
463 540 562971359
644 767 646174092
960 685 194310189
612 301 595839248
853 743 417285800
810 519 419799287
429 98 219149099
445 286 751119257
823 758 621366075
747 5 956234128
443 280 595255807
160 75 155139845
165 483 4937973
434 991 509264531
521 833 176556061
843 80 864762591
727 516 91769157
545 463 522642579
139 312 742825369
689 901 249244668
536 214 521282178
742 876 515647070
97 210 660546671
4 90 568447950
124 816 819419348
694 622 665136723
224 946 454758346
257 503 353930086
484 182 507453287
656 13 684110481
237 963 714450945
8 431 883731502
650 428 199377668
892 394 711241192
472 78 962237562
181 754 370936583
601 514 319030261
713 366 264778320
138 536 796909613
457 609 387721083
955 78 655728544
7 355 435333633
289 597 928917664
373 579 757478579
699 916 852676786
887 732 753111099
51 760 276432709
666 271 453633934
538 83 972301324
417 259 675203878
949 202 948696963
814 321 713305563
643 302 153080698
382 660 435044530
791 1000 158968709
580 749 709806073
305 327 766087745
308 337 882785452
423 237 188224496
906 598 421685086
799 565 679684446
939 8 887696191
391 306 482496533
455 441 38186605
266 66 612390371
945 463 515543753
582 644 472958863
246 521 16864065
244 236 921289212
520 296 500865021
188 181 306111853
776 126 767329509
777 262 567099946
89 337 122893975
890 713 95748061
802 95 658286115
444 705 73246625
560 53 496617957
82 464 295819099
618 371 768114693
669 495 637606482
137 640 289488439
525 206 915943143
504 327 725003009
634 247 513983886
970 364 696788663
175 277 698165565
307 258 43359713
148 159 875428571
957 53 804933210
84 611 659518761
57 803 200237583
411 843 183266496
461 476 858910781
30 325 129273883
942 848 454533260
919 148 474415560
318 697 945508641
588 379 977275152
32 976 46310374
751 587 599824435
879 458 577379878
216 465 135042090
557 216 971328217
925 369 161627469
896 677 695156037
855 578 145454429
383 601 525681340
272 517 464115496
221 383 374414242
718 119 706764762
573 167 12567351
566 644 364037535
884 955 85084422
377 766 675560873
534 764 553027178
692 902 267956273
320 396 230286426
26 554 424472819
340 116 750043578
586 755 251721511
564 891 542814460
600 587 394543376
388 488 124210677
300 206 625287085
979 201 131877963
947 146 526826084
840 516 42889478
828 64 393041966
344 95 115270653
857 312 825152221
72 705 27297119
973 717 869086992
408 988 748561884
822 657 151148905
744 690 329318033
798 662 265805839
834 438 479476328
981 600 456297496
510 394 108489766
334 394 350330192
27 743 44050797
961 638 79227603
576 651 608412134
492 612 504940772
104 1 768225949
704 958 558975523
808 10 406580290
506 734 607342716
93 971 683675265
941 441 24762728
60 840 453882273
322 616 761829596
883 61 668925913
418 495 541531340
977 678 601682194
178 325 107598140
489 240 717987350
858 21 611137473
795 793 718287513
179 966 695806615
11 391 522732865
527 656 762101585
861 576 838410739
515 179 400379908
933 783 689544244
242 632 345489323
930 643 92540283
731 598 906270398
703 138 329128957
975 788 905208507
49 444 532838474
217 451 176230139
76 451 802175526
265 74 812761790
531 795 610605782
199 395 251615718
171 358 95449097
880 846 141763542
851 549 764043819
780 70 252378901
392 340 590668727
553 753 855615708
415 10 57024293
920 532 271862121
170 414 696059678
871 81 960542405
439 125 364112300
996 310 701366666
969 408 758030937
654 66 939850385
384 961 132059610
368 316 511468194
118 340 697216543
529 678 829118612
835 763 876956172
149 104 334458316
552 542 652937304
194 179 221378193
354 830 558773643
631 200 594732135
121 280 18602920
842 887 727599547
745 966 426794640
87 584 803194766
2 745 254347624
936 541 975165394
184 161 673354757
215 444 407268450
722 160 376863173
281 22 403203755
818 719 984725684
590 314 166388490
501 852 739052198
421 581 25210041
700 875 139019905
470 791 638730773
158 883 551762576
493 491 718344923
353 358 828123554
481 694 364439164
251 77 428038183
203 181 188070490
123 921 249563095
738 808 789731166
288 742 112854128
109 57 270896032
507 18 574789115
824 727 276527469
625 203 894749063
918 77 562801957
784 369 922026077
904 644 433788647
893 628 796423484
174 514 938130346
693 395 886353899
671 525 698095124
986 566 554393972
497 544 869705215
623 444 724656596
721 411 78788653
847 999 925150324
797 871 185322456
260 178 529584289
270 677 152523643
135 280 244372858
765 571 398090217
108 517 220058618
984 975 316738424
207 262 310625724
471 976 152863584
715 280 997935351
637 520 722554616
509 451 822347957
859 32 82377511
478 307 269672248
475 609 759091809
591 207 387074999
448 928 960350279
782 160 774099547
909 679 692902381
156 444 86064623
422 113 710269400
339 811 20901113
849 144 49994411
378 979 69875008
770 755 403437080
546 182 501486357
330 973 828904111
805 413 841558924
556 819 781898992
177 195 165179068
889 572 406020537
54 648 938129390
771 931 714664061
854 982 185021347
152 265 952328374
915 209 130898446
372 73 54008550
759 372 895126264
723 559 156326241
709 853 675304425
176 516 686531151
287 242 68721129
249 304 338905475
500 788 669584510
687 788 25153494
198 843 469954303
530 584 609052418
498 222 395919502
424 617 645151756
801 153 657878597
317 997 72012121
276 380 432759043
490 337 361036114
241 736 428837528
894 11 819415861
511 751 101432887
228 992 366363070
561 734 923704487
714 125 27736932
774 314 980713747
967 321 462408617
658 336 240423295
107 666 299272872
356 184 975816431
323 90 330230022
239 330 832364299
480 76 183610640
328 887 143174657
695 816 609299966
433 643 852075277
110 265 895273083
79 401 437847801
551 601 371098983
486 392 552609742
897 281 225343338
899 848 917996362
460 761 456248023
185 826 645160808
474 164 262163865
954 997 490922264
505 24 85855349
574 675 574580759
832 734 756018552
223 110 330299058
292 722 711832188
829 887 758836446
131 94 453473930
636 438 318824271
800 408 57386246
599 997 547341099
569 959 109005832
45 31 19856801
589 340 367951219
477 753 354365266
739 289 110640533
409 997 64327010
192 377 783099347
522 691 432539127
794 166 409999064
707 655 414767781
672 105 864235462
914 980 153828772
711 700 806811910
420 591 42327949
399 625 302964019
313 752 479189422
684 804 445105229
663 941 796156399
40 84 281364899
790 37 369997705
311 164 369094701
297 814 112164089
44 765 127923386
874 875 858012245
19 591 507136146
208 169 422618657
111 434 699804794
750 958 47294634
602 139 103371872
844 74 693134307
698 102 541752679
619 747 526573947
596 114 229796562
838 105 510584831
357 537 126206033
62 616 694761263
405 300 771621004
927 113 584519829
778 716 502990400
649 846 874322591
882 669 578590587
796 562 892366511
398 358 794105752
605 164 910923583
341 89 663229300
173 315 5848793
682 51 18104832
252 201 465352455
416 786 562428626
621 284 50866929
665 941 764368568
539 532 442168557
575 105 84224065
937 942 543879846
482 477 600824324
821 296 728625750
983 396 989938620
702 767 802044314
680 552 505860642
639 497 97373777
92 833 397337514
726 493 617537957
746 141 743919366
33 963 127086383
683 172 884572420
604 682 284227616
452 517 813197977
205 571 588488280
136 719 738602984
740 431 385656564
143 707 799501889
157 327 460673058
756 111 267259219
773 428 415529009
190 2 993582257
998 839 398985504
117 921 210246198
748 486 104357413
670 615 65662225
360 669 201375199
48 82 64859304
934 645 751330500
674 373 369680642
231 401 261742781
518 800 230189064
595 716 44192796
436 244 751872547
248 777 254940871
929 519 943182634
523 235 435491801
250 824 454771877
496 505 113936794
543 123 335897953
825 166 708372769
376 738 198663722
233 129 660975887
151 887 611733635
243 733 731581555
741 980 907285298
393 207 65184070
985 31 192214653
326 597 451018781
440 187 880608431
346 816 788579402
563 521 285209219
407 411 589484744
642 658 711676711
935 970 505910869
238 921 944889765
362 388 138625729
219 719 720363813
585 609 507789235
872 715 516124526
696 599 787243205
350 849 381532948
150 387 18333183
35 197 573585098
526 653 712624055
792 543 233533681
836 294 91367870
820 928 997826329
512 258 698828508
968 5 361472439
878 602 849377410
962 123 733552914
724 205 921375765
710 198 181949310
888 621 694873846
213 245 92169643
866 306 113738779
978 189 239706531
610 253 301049880
442 673 722353994
735 125 400986011
728 219 189063349
867 371 822082388
725 782 785566168
71 482 488420380
52 866 108060728
812 726 560496294
903 603 846486014
547 79 752190131
367 239 384317933
218 693 237395433
567 53 811459234
555 291 387384481
432 311 230594872
624 325 393529484
817 501 437007233
9 777 242564641
479 407 875868270
951 962 852127290
343 44 855359147
593 985 964756862
38 138 573691727
869 445 509277411
351 46 131203604
427 519 793881179
232 728 227269668
965 86 260908545
128 38 250960650
608 747 158981786
594 682 887364300
769 284 64453604
168 342 801071410
6 541 499932123
922 958 932748842
905 441 247936872
278 948 385980165
646 952 186087895
924 461 338333386
145 555 210143955
809 374 329119515
737 831 794864504
29 507 184939324
995 625 578306427
570 437 458449122
263 624 244469611
508 287 716174040