1000
741 689 818136307
311 689 412521140
785 741 773606497
314 689 945326183
464 314 298593215
71 464 192103919
247 311 673075734
894 785 726558687
32 464 420514491
747 689 547411076
533 311 819324587
767 314 134354168
727 894 957295228
557 311 330067042
756 464 516108769
356 727 279909856
634 533 153009816
327 727 577929409
593 311 986812654
113 533 466201165
284 557 703021563
342 741 308930695
290 327 339139584
939 767 723198034
350 767 984981604
250 756 490077350
157 689 963181971
305 71 189329291
321 533 865239789
436 157 15201599
662 741 545940986
677 785 971908858
614 533 222562029
292 311 517286431
813 290 276036225
698 327 467446550
854 342 595991366
836 677 860893037
154 727 746504993
625 356 814959347
393 290 82539411
523 939 252196037
528 436 134208711
197 393 59697619
198 71 712763232
207 677 629501872
373 32 208792063
358 557 543614878
926 939 967645529
483 373 835678897
223 284 155863569
263 250 351016835
221 634 456380531
526 290 308751435
971 894 3006705
859 526 203670446
185 836 540984559
789 926 214159146
585 785 885879531
964 185 34045013
9 32 797993547
161 483 754829624
864 593 652326118
860 747 25412568
627 894 525110145
240 741 693828340
676 305 315082614
697 614 901467650
360 373 165250819
119 207 141809760
427 464 569969569
414 677 669995195
889 593 480952796
618 247 448484273
355 533 222163329
170 689 810901473
150 627 633882295
998 9 73522283
303 662 358063249
802 414 750016603
679 414 499076588
142 662 819630403
654 185 666270461
458 221 575448089
141 321 33577656
38 864 332747885
824 533 936937788
400 756 241628682
509 747 851372972
932 756 116202826
549 509 858142655
271 676 823163943
443 523 432315928
348 263 686936495
179 223 565572824
88 314 892082853
387 250 270926640
274 679 122887628
98 932 379768341
106 585 956082579
541 785 733788209
160 593 959576388
910 698 936334276
542 350 295110077
489 971 164886204
786 654 731751
277 489 999488249
272 859 192435186
236 662 645910605
848 541 528234150
986 824 981622948
6 789 452860212
922 654 413487500
429 627 550543647
878 71 564914741
496 679 307448089
928 427 116965820
395 342 872266593
783 727 970776415
140 756 713528010
674 305 722642413
902 250 225780178
646 342 418713057
231 496 403379017
819 350 313380307
626 741 873487315
604 625 666690244
424 654 584625419
330 998 404324766
684 240 973709000
725 71 821178396
406 677 98690663
575 330 658082969
109 932 747290800
538 113 501227285
282 170 627383289
246 160 583859457
586 971 499272100
206 939 403567464
408 526 195320698
41 785 854234679
85 727 449144036
36 38 655453287
354 926 387882237
708 986 442697644
316 342 500935269
658 314 598387518
227 350 648177917
712 541 27964479
346 528 658147850
112 221 477546516
663 677 874926243
451 727 855508387
703 427 372225261
981 698 831466097
99 614 922972692
51 802 889027938
572 783 66435375
352 41 12420523
947 400 461177947
637 813 856494466
982 697 333286681
479 894 335131696
26 708 626770953
693 161 38830393
2 538 445204908
222 526 833966330
857 483 15199178
515 274 677843706
96 767 266794793
766 789 609097749
571 679 855933401
19 766 217346489
416 674 352008146
525 528 847822672
678 96 518969093
720 910 806699418
156 836 807209834
671 571 545163978
764 693 568135394
34 604 960198741
423 427 882753968
916 671 420793818
101 708 31453432
474 414 283254292
908 321 646103807
979 88 649456998
159 679 996442972
584 677 798478999
543 756 123912253
822 766 165861237
583 185 96361015
472 509 990015358
510 141 400036862
628 824 589368095
168 348 525564763
594 350 753187615
178 231 89188478
845 618 137501513
823 627 864608120
738 939 262940858
891 207 734002741
578 458 816552869
45 290 463054300
35 538 339096017
43 327 109428950
288 593 257047602
7 785 390405981
116 747 787255861
302 878 142741387
858 725 748003913
65 677 899051978
692 646 7795197
337 429 578166144
993 824 388001040
111 738 535296639
72 741 867818464
903 845 908708571
601 321 152576528
954 662 107703654
82 231 628247751
391 646 898730252
232 352 488156082
411 393 827334158
213 7 183274955
366 785 826959181
452 330 984340853
310 693 407671328
426 424 47935745
368 141 12513470
158 964 752037254
871 894 296181753
740 250 18686832
166 96 352559910
162 628 604519942
215 284 21575601
755 452 491903575
863 618 908413432
270 654 800760043
945 406 244822346
884 836 588161421
349 373 585733747
974 247 936826830
480 671 770287390
687 947 905487364
808 614 477795091
209 290 473769222
75 663 919397824
737 894 412280424
539 65 627933908
413 429 950566136
817 9 268203717
888 337 577502809
228 360 874806930
746 290 415915243
520 908 796526738
127 170 736513602
129 541 463351465
394 112 799808297
700 542 402554144
721 523 806729556
18 366 589814129
278 305 455034280
829 698 924369995
726 9 775809193
205 366 484380187
927 903 737714464
291 726 514845760
728 284 524786876
546 38 171172716
791 726 471019441
55 65 450132552
745 700 799358929
930 314 777015127
359 916 99643429
769 316 347237669
622 819 627336801
275 864 110148392
80 250 405426408
422 185 669749319
486 330 668155072
485 85 108326357
793 578 277909484
334 316 964228736
114 474 70300257
126 423 735160547
631 678 549610046
84 863 433096903
776 726 267330262
224 373 696050368
265 594 77276476
361 458 820297031
558 213 312507541
599 197 310012308
905 250 340093031
345 350 648976701
376 334 62521872
492 227 50634876
841 393 780394484
276 698 872790439
992 614 190373432
957 116 924163160
409 836 264113010
372 689 58003797
868 637 385000629
445 41 715153145
347 930 38626349
801 854 796262868
608 755 647572115
261 209 166104440
264 347 277238370
430 101 630729782
516 910 686561925
921 557 190162252
511 472 248518051
749 829 268184671
506 654 943086447
121 783 79997832
607 391 276301371
929 679 638580214
655 974 125864063
690 400 587052891
763 971 177385003
800 414 978914318
576 776 376805897
597 986 63176462
47 764 515651817
3 19 819263024
202 395 303490306
570 265 488728328
733 776 152536388
994 599 399566706
245 314 167621253
711 539 522557739
830 427 239087167
105 992 168597349
63 671 755234941
531 930 824359610
37 546 447281809
768 394 198748093
196 409 455431593
816 823 153527522
770 26 236779133
444 452 222009840
428 597 22819903
417 994 104631677
610 542 213923482
950 597 398914305
174 769 435785541
761 34 651917432
42 387 648272852
4 610 460161709
242 824 721247426
318 75 429328695
632 232 799101932
524 445 221814867
731 663 56706217
10 533 546304847
851 142 949923138
435 98 238866434
29 628 487856622
450 622 824631853
386 711 137514808
629 34 114617967
595 608 606793192
495 292 103175232
280 725 282857667
252 851 633553689
792 954 875600461
835 776 459231307
104 47 970499705
751 318 561075179
315 769 451737245
619 929 653800562
52 746 257145245
481 819 382287732
404 764 938729124
287 506 219717118
148 157 814605730
750 311 79301486
723 272 748186657
339 700 579325488
508 287 415198614
837 142 50821329
338 387 605924302
383 444 341278358
369 9 765093084
704 998 925460851
77 926 16700412
234 957 659542796
57 361 459830666
147 595 577136930
602 222 916045036
942 678 278108931
487 368 114221919
23 857 644275056
532 549 574640576
340 10 601298566
253 416 881325084
812 75 628327102
642 599 957988527
322 610 978655457
237 234 360431258
562 311 972365109
462 444 518233870
759 628 305986763
956 265 762212853
390 161 79313326
935 310 988836960
171 926 615326396
384 290 916554861
953 282 902777389
153 411 939981299
582 723 953869249
293 737 115941587
238 360 843479582
565 63 848237137
396 352 103503502
296 34 30628264
441 445 292312613
465 711 450030980
412 222 138554429
803 947 973043747
364 383 527970036
31 737 89592875
647 232 783604149
501 205 943252885
279 318 121379037
453 101 422187165
573 903 770431993
24 228 763404243
730 487 268700613
753 274 672833447
814 586 853630989
183 903 881708628
907 538 401505126
332 908 425555925
534 342 377850364
357 728 504283925
844 964 165501854
901 288 796481921
596 337 74206232
367 404 979139454
896 986 567638180
317 851 167634907
949 520 534528746
211 408 263586744
152 926 550739170
550 263 344940391
73 677 645537374
167 288 985971505
146 390 198920110
403 558 333901959
754 829 412342301
333 303 934542321
195 538 821964190
25 154 164920566
931 745 441533110
512 51 360260976
191 282 924444520
499 372 233803
826 801 475790485
401 583 141623625
641 534 301661011
306 830 161267929
958 19 866091993
656 465 711955560
649 338 817880977
463 720 106571981
20 435 524725562
283 783 638042202
999 47 767806160
184 945 788055031
143 105 523581165
933 337 406199978
794 602 402183027
544 73 583824200
176 345 420184909
710 358 525926175
189 352 427480388
843 575 779314861
972 279 126013262
780 3 575690301
752 998 776150642
694 253 540931226
967 47 663606434
670 557 549413130
645 687 260828296
341 908 215330477
219 755 264360820
136 572 69139877
86 119 452420506
200 628 297416306
68 836 323731720
962 733 706813620
643 404 587184518
906 65 313623313
838 237 141375530
76 731 419774911
447 36 593598307
559 205 135815997
579 733 840432730
138 340 94974999
100 953 244387934
856 174 724413182
295 637 335698689
488 860 139990773
765 602 166279084
289 916 956633805
937 928 166007463
821 472 778268331
30 302 322062090
149 198 839554273
244 183 988645411
560 346 461583199
363 528 665991777
810 29 796370912
918 655 461852370
867 730 140356608
762 426 814170590
790 284 743721623
825 265 188278183
102 261 803799166
187 23 278922393
139 808 679046810
831 628 57707226
281 662 111760510
966 761 673567731
556 753 338657727
529 622 885884290
220 86 183716549
137 720 654840131
92 935 509601531
182 674 707417794
787 143 961052315
872 148 831802184
301 111 898430672
613 150 32483380
521 182 272840662
117 291 146858901
164 687 723047026
885 534 43779810
70 817 685851409
719 767 620748189
163 413 478461886
500 290 105564040
519 147 92280334
438 868 841859277
777 972 383616285
963 704 531893884
259 766 280135188
249 76 324658220
609 525 514254983
820 249 901889238
833 671 357027816
128 71 444631711
948 143 420955396
784 710 137399972
702 845 870507552
852 964 824164463
640 765 898482781
439 906 762201365
410 889 946178770
307 438 874137528
491 98 566777209
615 168 703268807
561 394 951239925
522 671 248194477
442 163 563246516
61 726 272650859
946 202 949760585
17 747 872274031
630 710 908152846
431 401 641475677
772 506 749198683
473 179 370379449
335 738 386458209
807 215 519017566
598 99 803371926
370 901 542286740
650 720 468341451
760 38 784665518
955 121 228226855
513 770 924367864
145 558 176841016
95 105 795248774
155 409 180063688
297 155 279939132
12 902 785139160
379 992 693921133
14 355 561129145
563 156 738926180
606 354 860023396
581 443 858460825
218 80 420518369
781 150 505369972
577 282 259926673
691 794 203540854
722 72 653167531
251 730 440975137
448 483 149003936
611 101 708395706
382 23 788072796
27 565 15147993
255 619 677857319
226 410 398406749
876 702 74424590
890 550 736108862
325 71 437258808
470 164 642107196
299 658 435449052
799 19 910651608
941 435 673513821
507 906 250765472
230 837 789857492
735 703 872320079
743 261 430251545
353 252 792458815
151 363 289440292
110 339 324552670
165 287 707930760
208 355 76759850
407 745 175447007
239 541 938891787
899 750 825465718
504 151 950547754
951 844 260965041
50 363 326231176
636 403 361563568
133 723 97276708
913 563 804105616
343 171 978256592
709 752 231581781
621 582 560213640
308 408 818592569
204 903 287811851
665 885 510256158
21 321 354729714
172 270 381218376
135 355 357968333
639 363 480265723
375 394 571099981
732 906 165000855
920 95 863725964
771 808 92500150
329 755 460962024
892 395 890860999
715 747 201131651
605 238 162135662
518 171 232937495
667 450 99408854
469 443 698044847
122 325 776962712
300 400 72672425
233 9 218816257
298 168 552865663
28 18 97371026
260 427 925931567
537 19 496818345
713 614 890533940
875 95 169783249
477 394 474862379
22 826 74394782
553 671 838166314
973 743 955628905
476 598 497209643
943 510 376954916
969 105 314162862
490 239 298634821
181 876 92959302
94 218 260435392
58 994 187226543
536 971 27644328
736 642 269304788
914 501 676423513
243 727 873941784
456 340 96459845
212 428 455999424
673 712 757078230
961 549 439420285
385 608 410631173
388 958 228344037
130 146 860057800
699 287 970796555
657 738 500887856
995 327 385423725
862 101 340671605
620 410 953710449
89 137 777127697
748 622 358349816
248 687 933312994
968 986 561068253
666 370 599261684
351 50 934268071
69 610 209233879
446 438 278530304
371 245 274128317
707 178 618078141
313 121 55598361
514 149 765361470
475 670 389386361
592 619 643212368
241 222 883292067
778 187 755579173
328 453 181781997
855 122 540489906
996 549 971388507
672 721 410128815
897 700 613194265
714 973 548044501
194 780 711891583
320 878 487975453
40 240 634784597
256 583 390359151
67 666 552497868
729 393 623435276
633 807 284520059
415 372 127398412
874 439 703826520
56 663 341976155
900 856 369862161
849 456 62688786
454 709 254032553
923 105 168451353
294 801 266532944
93 58 836124028
54 428 495654475
659 954 135572530
53 148 562546553
997 3 493797430
503 231 493048962
125 68 504204502
502 447 955748642
804 637 22841143
983 261 582562243
540 245 367823610
173 507 830431076
866 292 744609862
175 927 97991343
757 943 638567866
468 391 90021297
497 31 305378818
225 253 623268139
103 207 325748842
440 110 281041676
744 642 26221279
616 594 848292671
944 662 311602023
795 825 852612269
312 611 903159956
680 801 815682100
81 508 775097692
805 279 684502996
985 264 262389599
59 485 79834516
774 360 16647014
782 239 715042998
64 489 346191813
842 102 459848516
603 676 650286301
701 98 776075699
120 939 487042155
773 30 147245538
421 152 690952229
397 137 10238819
686 390 803396368
718 327 360325718
433 183 470243645
269 536 261814678
437 821 83964295
644 250 720447859
779 570 46461947
853 807 474925329
5 766 500562037
15 654 858043510
911 496 132191711
796 442 216491330
494 256 277702071
839 17 665674391
266 481 246419284
484 68 685252183
304 88 364503947
959 240 807880224
988 864 822611192
734 899 441519005
377 610 344875546
79 25 485653747
108 151 297624949
742 388 239672807
33 920 82728022
591 116 305003389
419 891 562826205
580 179 61653851
651 657 3200401
806 322 958582561
566 791 842802894
883 727 249298515
828 158 647731959
977 896 412869374
695 316 92732481
652 75 975789185
402 311 69900738
229 387 131727793
48 727 829048396
49 452 604565136
797 175 936654231
840 440 230530687
46 690 802421195
683 373 810952649
449 189 164016787
1000 773 206521973
617 575 546495005
984 480 55743946
466 82 824192557
877 342 618459660
362 393 240133190
91 524 216537836
432 786 301594401
201 135 360766882
879 611 971052110
569 176 736346160
834 977 352874966
39 63 824462297
568 748 119602572
434 383 420643268
83 596 700845400
193 814 273234034
904 538 216677842
460 993 406114803
420 320 663149877
535 366 928125227
323 888 9741614
809 813 921938279
895 419 686445083
326 356 89498090
8 699 198700738
912 98 943457194
203 191 461217695
527 481 430339688
192 577 529568475
574 830 969662809
548 345 909036584
74 251 935270450
478 200 221060891
624 748 226290142
398 15 5041022
925 583 83153985
471 127 836872569
324 845 795619387
344 715 914003989
374 178 258911044
11 293 842192736
934 595 780732033
144 992 936589229
623 611 66913815
688 282 678733129
124 785 622890645
115 470 9738415
177 150 658625220
467 414 126236304
661 100 517892898
273 494 365391357
706 888 67893675
555 526 192978596
846 441 737941014
455 76 718656003
739 946 914430470
134 282 600625530
952 85 361867174
118 291 427942122
980 163 113873665
669 160 308381872
685 366 342077251
881 64 517454420
865 436 165273908
989 117 585952777
60 949 283406535
459 416 603625034
399 287 748709650
870 935 1655278
547 436 85571480
190 662 569738777
668 382 735187785
724 791 863298825
660 30 141874553
16 422 276167469
590 129 649864385
13 941 964469363
909 749 269366644
716 734 208912166
87 619 177126150
861 163 355501908
44 43 452368065
978 23 344091382
392 111 548699473
425 280 751894
62 789 517020318
788 76 285618100
975 205 518861623
457 288 573624632
1 181 525355914
378 93 842972963
653 88 232676796
705 720 707549641
938 402 740573344
936 484 663440770
976 157 856530708
505 609 794542016
381 448 915139875
552 487 539883687
405 322 26963870
78 766 424591661
589 800 64451033
612 500 578856612
365 392 29722831
554 446 83502076
517 863 56366943
267 393 258937156
530 422 253507414
107 172 74491004
924 938 998976432
545 918 997975309
893 909 920869527
682 700 314580179
990 363 453835402
775 571 808462054
123 726 247241410
235 198 856904949
587 774 996251516
847 499 894878649
965 963 372880352
991 659 240771504
600 639 289262747
132 611 343598971
648 296 702505073
461 63 327223414
268 640 203962590
564 145 149003339
214 643 986174775
898 660 108957418
675 33 592762223
169 293 958052547
588 830 847294695
286 466 77685605
880 770 29788302
131 751 716750772
199 754 694744363
887 489 582183668
309 366 764928759
970 995 776375813
389 355 550142122
258 207 917074287
696 840 874957671
717 805 963906332
551 356 522965466
832 412 626615549
882 184 845220184
418 628 386984448
380 509 342639181
66 410 207917424
210 440 223499016
217 223 692375388
960 353 439962208
917 774 931473227
638 965 436257939
798 1000 816176636
97 922 220011296
635 149 699919332
257 941 726168819
180 608 326392998
869 997 447077788
482 286 260975200
664 870 818209607
919 241 55583873
186 107 684663957
815 508 776325946
285 186 162172573
188 43 440996587
681 436 305925336
940 777 705888844
216 736 445039649
498 11 37665646
262 806 300243294
319 81 613670375
987 603 202763440
336 521 157132752
493 852 346591853
886 63 765882126
254 255 708945467
915 320 507506907
331 552 842231257
567 271 215712232
818 631 73777996
90 833 3076315
827 326 399989920
873 879 294270130
758 13 503918395
850 55 872801671
811 514 646754512