1000
187 162 687654004
936 187 607541266
308 162 637947029
678 936 667188422
958 308 965732431
374 308 898478235
516 162 308207384
99 162 261256368
776 162 329885197
247 516 220841281
916 776 674038520
297 958 67554161
156 776 834555227
690 916 312406410
84 916 865633655
449 936 459456805
5 516 739726857
695 374 176394183
244 247 128799215
934 776 766369443
285 84 813372824
914 934 389005236
818 916 862001703
298 156 767513626
451 99 712232133
40 247 10841462
822 99 838102459
582 374 63463770
296 818 690413275
338 308 118879702
535 99 560571072
390 690 528429100
737 156 491933840
202 296 673169470
861 308 644050161
923 582 848137074
644 916 510910912
491 449 23841617
257 916 312570886
796 491 367320751
896 914 316388790
866 338 178831514
908 451 478780329
929 162 128943828
197 535 17609437
262 861 201421350
720 5 288563493
991 5 702782728
277 40 852250370
828 822 357754984
762 298 887881153
726 822 269278942
784 156 922935220
477 695 763564881
324 678 569293081
628 277 761634895
821 914 831345475
751 5 319204791
240 923 306569175
900 262 401896236
431 796 888195861
705 431 613934899
69 374 769015679
422 99 465710986
183 69 682182298
17 644 382092981
639 644 291278091
216 628 218547568
411 451 900430754
812 162 460137089
250 451 82828634
474 914 454757496
72 821 862210338
736 923 73367078
319 784 133715181
189 934 523310396
440 156 29134240
141 422 643743617
153 923 901076678
576 244 962157122
738 189 118244888
441 916 331631330
600 474 509461573
150 5 344521329
61 796 876563120
410 244 861613158
245 431 814966570
106 720 133619404
165 600 333932598
889 69 319180269
993 705 552891195
461 738 376722975
419 338 168400450
344 153 452965847
384 705 740944074
570 908 546659504
804 384 717382492
159 197 282788238
939 861 650687841
453 908 449854973
621 84 492888765
847 441 150255123
527 705 800500881
476 695 229384106
126 474 202455624
423 993 10732672
557 695 455168356
63 72 869472318
278 285 232257886
995 250 43872117
830 570 411260003
341 410 624536940
23 916 234068587
606 162 4401830
447 621 584777205
863 476 884019930
868 889 792324130
152 476 817776769
507 240 866630899
571 995 986699879
364 796 533331125
358 277 424438407
10 374 709401180
104 762 12305085
479 847 785043691
724 796 944482275
177 527 95779993
45 995 76610801
660 240 941058243
473 262 723264725
353 423 334168735
803 868 255148272
87 473 76357929
211 410 794910010
499 991 605009070
492 262 288473121
135 338 395619999
315 449 569515435
761 247 191595020
702 250 673343025
626 315 778620891
484 695 174393269
959 189 464951146
133 527 468693983
595 492 58673262
24 17 47817373
335 141 951135259
233 863 772389158
933 484 534626498
345 705 171023523
457 211 893716045
164 156 277075627
617 751 957772947
522 477 55904761
428 374 613277247
711 106 504398320
955 484 269461995
708 830 983445285
442 245 847287619
504 338 99978600
226 617 820849567
284 796 246308695
60 297 32547605
232 660 415878531
632 866 779323280
420 374 223352727
892 344 753936032
529 278 761404418
191 453 91592508
107 183 260825639
27 576 575245891
592 183 379496018
275 803 429647442
673 491 649565377
304 107 467143628
755 705 98984306
980 308 178900767
681 296 730452434
18 284 503466881
833 592 312187385
36 995 95216253
495 183 227712327
43 929 398349355
862 796 188289131
114 141 485905564
990 570 675860141
884 737 624348506
323 639 134683298
973 17 922691838
388 828 193140071
180 447 23622555
200 211 12513798
629 40 377081832
633 576 677674857
75 711 68925783
382 75 420721923
65 245 146394715
692 410 919463673
435 104 120127397
514 821 97863381
108 751 18636169
28 866 575871922
675 65 959322305
544 24 457924665
880 226 450233165
615 233 799399784
614 453 273731308
173 776 904420394
630 821 379072422
348 934 865550804
945 675 494531108
598 191 832454130
22 958 970264404
490 491 440085819
722 250 883884745
222 324 870830084
792 516 734604365
647 592 584128689
1000 435 519728121
915 630 432204050
698 358 177115082
719 516 143130105
253 126 578170743
848 822 835374245
466 776 233526736
302 929 481031479
406 61 718152049
142 491 217956607
322 724 817272700
577 880 799061451
999 406 808536843
161 461 218664143
415 344 235864632
519 477 683200530
772 17 142488063
88 257 669910092
54 991 327036009
917 527 378284462
520 776 816537525
361 868 372676224
309 277 990822900
940 24 720017086
778 973 570250774
418 477 589396438
8 88 665187730
924 863 202641018
434 647 168325995
236 298 632097058
332 520 466213176
725 476 302734702
432 880 880452472
539 582 431402521
607 61 540282384
657 75 692833916
541 828 643809125
137 705 619404817
800 917 835638237
379 244 735422575
994 571 263105022
201 297 826101726
16 108 950910946
860 705 807203435
658 435 223595433
128 800 950153300
89 678 596345455
313 309 387161426
611 364 176967842
103 84 195292117
445 736 169753117
506 419 160481633
523 435 264083705
465 245 885630014
400 22 371555357
485 523 289901541
770 24 651383204
989 796 806668247
721 822 131958248
139 87 399168508
930 69 175911281
976 945 23128576
763 449 40886287
270 18 976010996
813 202 302220331
481 285 268097292
742 201 649907135
167 114 222644863
672 364 604134104
573 936 603070722
310 89 730089252
974 474 847142903
840 721 454472542
851 24 466870091
205 348 227473778
906 725 310073924
237 164 123489476
542 772 103558644
810 908 576260801
90 161 332491439
635 284 107113100
56 629 328525345
680 126 610070991
76 22 851533698
292 570 325968618
816 247 82001842
545 833 636267050
366 722 98533354
687 453 733125540
588 959 515459932
585 8 861183044
455 277 133500965
651 945 737798732
328 88 702405113
181 388 377307375
368 106 769433719
416 382 288407925
295 23 336809322
2 725 774045803
882 541 209518823
584 253 387600177
512 816 9852446
745 784 27751131
391 929 576919452
558 585 561132434
656 451 33568760
653 10 768425878
928 614 350851524
988 8 17014369
706 319 76304940
642 379 22142400
464 796 246031676
185 738 96724955
25 250 727604639
417 863 478118684
33 495 509872360
340 181 721498320
254 191 336858608
386 499 79689453
210 976 701070644
943 1000 780176916
946 28 776675128
723 295 75712559
534 629 439154663
116 89 968255233
393 165 718998722
518 695 199219466
39 313 915698954
96 943 835509172
260 72 783392632
234 366 716968147
997 465 168684602
458 681 570254656
112 632 695039132
117 647 492580275
605 639 476734195
227 570 80944784
616 833 224069657
795 973 410744367
179 481 166852753
81 344 499678035
14 418 194531991
622 449 96866710
385 916 871689021
70 391 877040385
787 323 552339941
110 622 993675555
548 385 195822849
790 939 892418754
218 114 567273525
905 940 886867879
251 236 983240670
701 159 86337304
734 1000 892595346
841 72 150645510
670 232 877369295
188 473 203929879
398 724 655077535
654 933 819304832
729 539 507051848
832 295 318730809
515 139 678036063
12 5 578621715
293 434 129288797
264 285 206695206
949 654 530434203
26 914 157266944
291 1000 143406899
528 296 714356576
969 262 398844339
859 810 665197848
853 863 617890350
149 99 54966492
975 484 407698090
904 770 955630421
446 165 671311215
30 449 345738379
356 2 378637722
870 323 734272034
757 116 959290466
326 933 312127721
986 298 618209921
748 270 755096038
105 830 936473027
184 284 992147954
350 455 159130823
454 499 218409301
691 159 844128114
46 822 611628677
378 116 942108098
730 577 562578914
271 822 92268676
208 428 359431145
437 449 168130573
703 479 843379758
329 431 650514510
274 398 625530812
193 896 766697521
20 310 657367020
587 995 142173701
321 76 451109442
50 326 387296252
532 701 139819083
35 193 31462698
19 940 73939767
845 2 901949101
228 644 307558880
119 784 352166949
844 795 279246120
327 458 460368971
911 232 902491485
37 755 939098323
809 830 578624726
634 135 274409772
229 446 584755795
662 896 522332757
850 748 693725688
789 292 551424511
727 89 969723544
811 61 76075280
749 293 789340195
521 270 693831426
486 356 831342315
151 17 700019513
48 240 113868798
204 969 799198916
9 159 469287895
312 720 402716571
170 441 909388209
578 651 169458820
602 63 386704591
231 904 417408056
962 297 258837858
785 254 770425861
965 687 887953774
157 25 835520976
77 416 307502109
597 523 137389184
525 520 116686382
549 830 20028886
867 126 47560882
412 90 175649281
574 48 877349802
32 428 934147194
696 173 127735574
878 200 436642734
566 236 593430494
855 678 85279932
954 159 773570991
677 936 90187666
59 994 317099802
124 344 849937621
41 384 169664633
553 518 780766827
733 566 756413925
333 628 547132368
909 832 122875927
305 986 716778163
347 437 363048545
176 598 61358577
134 180 302872748
537 904 78797951
876 201 727514345
674 165 807896777
213 738 530147938
268 41 130694438
413 600 422785161
215 976 175811426
764 28 152945442
780 382 2819342
426 813 135490923
147 324 152781794
425 458 567780032
438 813 865561892
248 990 418399066
641 585 946110732
985 810 870025362
957 787 758919589
890 691 284136917
436 48 482413273
550 96 751664257
508 845 273369444
823 892 702432269
781 955 641639540
941 302 307143904
769 614 791866044
115 680 649405840
336 81 834984938
97 117 883375432
899 312 201814481
572 800 776411116
775 415 153344136
618 284 770217100
452 479 311419968
15 915 772445275
182 955 221622943
568 986 4056487
575 386 141987707
307 639 137066275
984 99 216436214
865 644 617558454
511 660 533919212
290 816 544497248
299 391 978241
303 156 137978941
131 180 341432242
938 738 929209425
158 436 651183040
530 164 14424452
563 464 128764383
754 147 660812407
31 630 197273891
4 900 551912443
196 781 883789773
689 413 494517804
362 928 787241542
396 544 478267925
130 896 382788339
424 201 995345950
620 677 422844173
562 518 435317264
970 196 156441257
903 398 965158592
67 629 727608572
624 149 991889479
694 270 563178345
375 764 35704884
663 525 154412683
559 432 811036254
704 385 561748865
502 878 906466791
283 606 434663368
682 59 107759142
565 162 903717688
1 828 325966532
700 428 690534225
294 523 531504004
483 984 477861138
363 341 458313243
102 391 403490961
448 332 899820312
259 428 245039256
21 985 126012930
586 476 20872847
893 24 986290650
676 985 649998714
752 458 886741063
649 103 625751387
429 818 263321643
470 69 486433548
979 514 295080432
510 576 536835639
281 218 269357047
223 35 20023070
367 15 77325042
747 868 554800547
648 678 196191215
569 270 499112674
79 761 492066073
857 905 461469500
849 821 350328706
561 499 137611343
337 406 460334413
51 20 101360046
912 976 405367969
306 447 944689164
693 662 871728118
875 165 132857732
746 832 917484295
261 660 848046188
609 422 434023200
901 597 234007252
827 893 3201897
439 271 433143479
224 107 407578081
987 153 300209730
249 413 800923296
531 796 88224562
443 277 731060143
44 976 862153896
783 81 438741325
786 912 275992629
627 48 120721580
7 56 290369154
246 191 409981210
120 970 305745509
856 102 273042663
252 654 902979629
951 849 557536821
640 415 862153698
825 77 955257373
265 521 803997100
791 21 443063558
886 302 672254632
942 63 751450536
83 222 268613601
144 704 816543060
913 653 778856279
898 818 200428066
314 115 997689284
203 120 8199670
394 523 196165385
282 333 930316857
610 523 325304265
269 115 819739190
873 107 442595017
760 202 653386382
272 848 157578239
596 141 953658616
405 150 58853393
6 21 129995256
468 245 108632775
78 576 819596268
918 75 178011953
961 205 187899519
891 420 944786641
339 126 44809381
643 975 253293647
263 227 21315343
944 569 222623405
666 626 365798778
744 736 555112752
594 559 351584696
920 900 977450285
817 800 549941133
967 185 114539562
895 722 453037603
753 607 492923138
843 975 739309140
469 644 235601690
148 632 402532718
538 490 41712145
207 27 221143988
68 21 651167770
826 702 579242517
688 943 777938276
966 828 350594566
669 662 990892533
925 379 82291997
927 630 907815295
166 441 710269418
926 558 490328020
168 254 662986992
972 941 624595013
82 669 119585218
330 166 772740183
320 491 21034589
555 76 865084149
95 868 885929217
978 720 757933094
766 516 79133051
258 396 826969710
11 999 787545583
771 926 917254995
952 967 766988164
49 30 820996527
637 539 854609271
902 483 646427162
869 44 494089672
981 304 479336306
756 890 648684845
243 570 335103258
125 191 259006699
409 904 840550752
983 776 825451448
444 170 409867604
888 182 634035162
921 791 874471705
652 538 61767356
533 196 112484854
235 200 898419589
824 641 341988416
543 940 970344575
212 144 949422608
741 469 804652292
497 921 292367605
815 563 238626423
667 933 27662320
794 326 524180841
604 438 863092689
894 424 811595255
62 95 66241100
220 703 894690316
948 115 967748184
968 749 582683503
318 368 489431690
122 757 556652168
94 673 289242495
881 243 99306615
864 780 727159287
58 695 107496936
773 999 686670777
53 690 885380481
852 764 681040330
552 102 805076656
793 848 357414366
998 701 672953780
964 527 623105620
288 967 337910138
613 330 490118847
472 648 971108311
29 10 719178827
802 987 419881466
767 310 140955723
109 924 247076023
579 693 358249164
883 506 967589018
214 793 16838380
427 654 812996692
397 734 162441669
743 702 313949037
408 756 268681416
118 397 455082171
684 282 456032447
661 202 136894509
493 941 327787645
355 866 471993158
935 903 741848460
199 306 333147299
100 815 390151601
556 330 229385045
685 626 232324030
376 252 165145019
505 102 691871456
402 308 645878305
242 464 513545140
225 545 842880748
145 159 659497942
38 23 670329428
143 150 384971024
123 283 467936787
567 637 303422935
714 915 485475052
758 264 140760472
750 632 473273221
971 722 183898809
731 823 676238993
937 853 852424586
192 476 892000829
414 621 904487532
601 548 673593964
645 620 523743842
230 260 895237708
190 746 931079831
494 550 206366696
64 345 353086183
91 706 593046592
728 451 319686761
885 833 327169923
276 545 485423822
797 190 567368769
460 965 640601883
536 114 878539342
710 904 224777236
599 862 651186904
369 973 106448168
498 243 699617796
996 363 580043718
551 344 120302655
580 4 638300175
782 939 905162080
401 297 886703887
55 20 779887966
659 741 155621272
819 491 348891244
950 58 63742762
342 916 607095287
316 314 669376465
798 275 211521939
807 242 836273755
383 652 336938839
679 432 261734639
646 249 999340305
735 227 524308999
178 414 786392998
858 46 134300758
765 344 332087390
768 844 653977250
814 440 871101572
806 660 318042795
463 458 772120134
581 36 692022347
590 828 826835186
194 254 639894217
140 345 952001243
487 159 882904605
155 776 122704701
593 429 907831657
171 161 358628742
372 508 491300533
636 38 801148298
707 979 966702785
500 189 592063986
387 118 730567573
524 998 693849880
311 36 670378874
433 924 324182658
301 120 841251140
619 588 898968069
820 415 456979156
732 67 233338225
450 868 575157100
897 178 392477792
475 680 352315044
407 425 255903116
186 765 362923103
462 65 839303753
877 891 919659664
699 204 754236334
132 400 953445630
73 246 295433285
526 263 308690624
480 155 336828843
219 426 713245251
631 971 355979265
478 582 190026295
838 405 152835085
255 561 472112673
489 474 426299409
195 703 374092174
85 810 756368893
351 934 30233580
352 586 30112598
317 205 334221395
717 44 591248660
389 797 245176786
509 116 768838621
777 180 185232736
113 544 827173406
267 778 688377292
977 995 70792078
459 433 724445057
564 883 541479327
206 848 511441329
381 556 305880307
421 441 764484921
47 864 148804408
922 150 43513232
52 965 597877035
373 190 42574657
583 506 844636272
111 264 217931523
404 291 63439340
872 46 703412883
697 980 29268925
280 261 431022165
919 857 126489264
496 983 591533386
467 43 624044488
837 12 907394913
279 561 556894109
241 36 159935791
713 913 837914810
665 492 955242584
503 128 485909702
175 737 779332387
334 397 407469992
716 165 694515982
399 411 854145027
217 309 614732210
146 641 201169436
956 38 37469323
359 891 803448403
992 267 112246944
686 166 472624054
625 342 960005365
395 91 81340860
172 867 407754662
66 751 686549206
221 112 967061712
300 881 231738514
346 824 249818722
931 180 119901358
163 607 856893376
92 838 997051843
554 851 366083268
34 26 544500939
154 611 935693634
788 798 658278403
349 657 617135550
846 686 493161212
377 883 54202146
325 641 309039980
471 255 777167891
589 28 27712032
121 340 357340892
808 311 648807597
371 582 628058576
540 341 827575836
71 659 835674519
779 66 614781075
273 939 739047578
774 318 894741680
953 875 296233483
392 693 819583117
547 965 737671244
854 411 407269802
655 652 823474824
430 52 674882345
169 196 277475844
239 84 763029805
874 667 714913054
403 340 586503901
80 497 693507134
671 587 532617133
174 483 690793234
591 271 346797636
136 680 13417324
160 442 610019029
331 254 112887834
370 535 203347084
560 397 306373699
932 697 578262937
638 340 854292266
963 350 580483774
456 211 357895008
74 451 75215023
198 221 849258139
256 930 420737656
209 594 104656978
129 230 973904052
799 480 304338180
801 983 48445481
835 233 366806310
871 767 315505356
380 312 111658653
93 29 758454476
517 695 568689178
501 124 125770978
668 656 96671155
759 811 558330009
683 921 831735675
86 987 870049786
360 309 375561647
546 31 514579130
650 648 920044832
57 46 61180833
287 190 567527717
879 169 131414614
907 985 26973690
42 322 101792681
138 615 499109173
712 250 718197338
709 476 630592879
887 660 6763897
289 893 866337050
98 933 247765101
715 319 427569187
266 257 686978066
482 820 881180345
805 73 531162265
608 328 581153541
612 24 364726660
740 749 71473882
101 666 350748365
982 559 350244968
718 677 288166971
836 942 938309299
238 423 4449202
839 120 944421026
664 22 732612896
343 734 712686288
603 580 364728426
365 557 184604095
286 733 421843244
834 216 925497713
488 522 400286904
127 306 944684502
3 796 964090863
842 313 21615822
910 835 956242540
13 549 981013328
354 814 212023130
829 685 290748793
947 406 682097218
960 756 167528376
357 369 667863918
513 851 673000112
831 120 979222900
739 703 714111265
623 598 950489614