1000
116 233 287322100
399 116 994362152
581 116 55978347
647 233 554223609
693 399 55822895
557 581 997527126
48 581 141751060
892 581 571246097
803 557 992649233
604 803 615716500
390 116 864436028
284 233 80570044
180 399 680374709
750 803 491597289
170 693 972218793
906 581 794303842
900 604 163924058
385 180 517871744
575 693 845392094
152 693 836873505
153 390 613699737
870 390 496628809
44 48 238361267
185 233 625949662
68 390 609510046
198 604 326337591
664 750 456343576
820 180 291582514
917 906 174792166
551 917 478528357
78 892 628584043
653 198 233805866
752 551 434379840
138 180 506119255
67 68 555355457
949 906 264344052
939 153 375939439
969 906 873559157
524 949 575679242
387 198 613067629
131 575 364670182
371 198 927992483
333 917 241340906
70 198 644997688
434 198 869773924
445 664 886551747
474 900 562899244
745 198 287641398
910 653 175346708
206 750 535286850
554 198 529140584
129 551 231195989
834 284 324452531
482 664 95449302
57 892 551163390
191 138 281679403
874 647 843220198
461 48 996889473
437 554 448868111
801 917 5645507
99 233 604971752
125 906 302551842
204 138 902893633
768 575 853036221
578 581 164612581
369 198 846261497
954 371 664751710
273 125 333911020
638 801 876067386
739 969 405196821
187 820 96519776
320 801 309363985
330 152 260270540
100 557 774440817
595 284 547781195
912 385 238600965
365 739 240054671
887 99 27090647
866 57 360151488
727 647 132327555
264 604 940280959
56 834 128401613
742 745 575055015
72 284 290496653
833 866 429861871
882 100 437033056
847 954 378610293
297 900 178118362
879 390 850708068
738 68 344078547
248 264 913203621
451 68 755770134
353 575 199778639
450 874 316499734
644 129 725086033
252 581 13850131
628 874 663050251
890 879 70880529
497 57 312845309
426 870 230261835
493 100 429799373
540 900 324583000
119 70 306158996
166 330 745528300
928 264 452283024
491 461 953599178
192 595 864002232
592 738 855354574
452 882 578757161
203 874 715367560
886 452 945682109
506 886 87989126
931 647 929633615
766 551 457543892
24 72 341325360
468 233 40321503
880 887 836884471
995 320 899314151
311 874 236961326
351 248 766294889
457 939 966558302
266 333 206394999
877 311 182309816
967 264 809520402
151 820 461929332
216 192 818560696
45 311 676677976
921 166 590416582
627 451 59168891
564 70 464332883
973 482 678711580
463 24 583864498
84 627 210239211
708 434 810692671
935 461 325968600
588 437 653479536
113 153 721799518
144 592 813353694
783 877 259863407
47 766 451925471
245 198 538319334
934 144 948610289
130 192 871801577
229 638 363318524
14 595 322134033
488 491 212069935
722 311 202885604
757 452 954580285
925 880 424678215
570 969 14411136
476 803 605532780
182 506 547758775
362 783 455047009
343 890 409789829
439 206 104497256
316 738 905120555
299 248 849147760
600 24 39838203
42 967 335083822
918 752 175228865
379 877 307219786
357 116 318373568
462 887 769662246
596 206 134126096
656 445 823764058
927 437 463206986
932 931 648241839
118 371 614789839
994 745 906438801
558 229 671638472
573 595 668073523
648 245 464343888
86 316 122576203
286 72 825383968
584 138 632801887
363 70 90968410
458 540 569451921
416 462 387433149
835 949 192438260
800 57 383019381
54 575 432738126
828 351 74331710
657 558 64316753
853 592 232959098
510 928 91228335
968 72 917321005
899 152 502877395
454 68 677280393
466 803 464146169
195 320 939886384
230 595 585651204
662 151 104457379
455 954 542221479
326 506 924808045
308 892 559809680
507 379 232739827
224 78 375036555
112 931 928779536
344 918 420615396
577 540 600542290
863 86 990092189
179 462 482727751
697 351 755058276
819 116 83482586
984 273 237225013
812 507 564545634
394 118 460509168
290 638 442423982
136 330 936190530
174 153 458807958
64 863 394944026
327 437 26225197
441 932 649007407
546 969 551838358
971 136 742206122
296 627 860669006
325 151 448092807
165 918 751473625
629 286 418059232
331 828 626282700
691 493 18810099
34 954 561589095
650 325 908953772
620 129 133198043
294 595 391503593
30 932 983633379
872 179 883184671
71 877 786287987
186 351 31714715
667 185 629002235
59 835 165109057
220 739 657854784
22 648 199164119
377 203 959566113
974 890 560909407
92 882 622379364
4 648 467428947
615 750 89259707
883 230 652838781
715 833 103962123
278 874 730130469
247 186 928745884
502 667 931926290
322 68 963027891
911 507 640874996
140 363 788216328
269 44 601129999
808 72 785251654
743 863 812681649
114 187 670850512
736 206 198435528
402 299 288893691
50 819 570647755
525 697 416479521
862 939 280123650
599 874 802218289
960 742 552406587
478 92 728632526
774 70 327395156
175 47 417379842
916 745 69846985
626 722 586479441
238 363 279068889
603 252 442482848
375 476 251333071
487 502 697268817
87 264 431676359
427 491 621763649
473 551 748158526
256 322 93241504
393 42 343768978
873 766 321999814
762 968 129392737
17 393 979281062
951 44 899678648
717 693 76419215
756 581 829724102
675 916 498724450
784 86 342796820
428 984 36651695
702 757 723355097
167 451 880481876
593 717 570795904
729 768 678006770
391 783 333969361
859 322 509107857
210 697 652245297
235 833 294649539
741 144 461783315
226 995 983360954
244 86 185191758
354 266 581530322
301 697 369823754
597 886 240798383
970 393 150116484
633 473 961380592
688 934 862047126
520 308 679993006
62 138 837900446
486 588 393792648
440 756 415309412
423 187 402196915
9 64 710643873
276 387 11289390
329 273 39440667
306 629 840802022
826 129 309342044
625 557 978555738
513 320 62562429
790 445 891020982
514 140 533174151
442 311 595433402
598 116 777124299
275 482 720732815
289 880 318628621
895 34 569224425
948 688 779882982
576 476 814099215
162 984 282334684
287 620 476499269
479 488 124396202
793 45 415165
141 644 188184271
996 357 187521632
997 141 250384329
8 463 606097834
613 301 274518893
930 344 659573745
477 613 93415963
591 59 977596958
572 198 836876279
852 9 21987208
763 656 725760215
259 870 661092961
894 375 150159376
184 994 447565236
868 247 124685060
217 230 624103212
583 513 109156949
75 591 95586926
761 289 612119182
304 752 609621491
12 667 431087769
915 627 475209646
794 354 313673688
27 437 994010984
658 297 564914181
767 599 896150344
614 162 27381712
415 62 911634396
258 68 920247786
950 248 738693462
323 572 50010013
865 9 508828546
601 329 785134929
568 229 673622341
707 4 376893996
436 136 868700134
274 790 774776717
79 47 57066122
896 371 539828192
211 34 398977686
260 573 563705675
480 510 377984688
992 59 75315110
532 564 204128595
893 906 896010116
566 911 717083080
97 930 78016032
41 30 286651376
534 664 570698937
565 656 248626090
902 391 310674425
298 325 180879250
460 507 372521945
380 399 75757418
732 439 316685833
676 54 274373598
810 162 869724950
346 479 615960011
392 790 716799395
976 457 869998062
829 951 51244016
188 862 982285966
668 833 514033265
196 118 818254212
261 71 354424627
405 890 40668858
663 738 446535503
313 819 303822319
215 487 854640176
93 451 173094219
857 664 763474771
472 316 146843893
232 165 135603377
407 434 111845131
149 708 411239752
587 34 581500795
103 948 737982630
35 931 832707704
651 899 600495653
409 399 374928910
937 393 200930114
11 675 971463410
530 119 449529359
773 451 956910470
944 455 581739183
839 766 78505532
240 233 801052153
85 12 750857974
494 331 465381577
147 540 434092056
227 534 132351369
827 626 739690332
838 48 497814538
765 625 54843447
795 371 376498766
993 918 914132067
523 195 6214954
806 12 214276691
176 911 18634840
145 482 739387190
849 752 599145828
908 849 659492255
645 592 260872993
673 967 459212175
913 14 518264579
249 11 48483926
158 85 213030733
208 967 832598492
926 343 211877337
541 264 612825964
813 633 495336675
943 247 289969891
438 64 186606866
446 742 255192076
796 882 202112941
511 880 489287132
953 174 782188972
315 45 651068979
95 868 124280579
10 541 298740802
342 673 804546607
120 192 991406453
531 184 390444172
701 100 761628253
955 595 329685073
723 558 17226500
422 260 234505104
160 921 479542979
115 233 814336474
400 390 451311640
143 656 466758666
142 227 118096308
512 912 57574017
661 138 698971519
26 176 864219028
425 230 519493352
384 852 381592418
631 379 512473717
535 645 751701638
43 887 74701338
431 486 47290648
82 628 95210923
61 301 788242247
876 17 487786168
533 287 167026989
685 119 185295212
798 140 126545431
836 306 871095674
714 329 267324626
96 752 107757924
293 925 503626878
799 661 4814497
317 235 106173988
548 647 478729924
746 331 167893609
590 631 812142975
372 573 307182465
6 385 205706599
802 95 487557428
459 577 503608752
23 799 505284711
547 278 625820616
495 394 671424844
88 158 284898594
690 458 633596856
348 120 212922788
163 568 902957938
816 880 343546464
705 944 251377131
411 600 981536982
754 451 917732534
181 195 577820854
13 925 389463921
7 600 110994203
169 44 377398113
126 331 353824830
881 186 850889982
725 834 392770371
528 85 488561880
161 570 340086044
74 474 980810868
94 992 547068614
709 799 465918095
978 138 470062818
980 583 84585513
90 702 205262090
418 664 257198198
194 48 939111380
447 570 522153044
239 61 268775421
888 363 458472805
666 296 610269750
724 275 414895861
156 363 572065998
177 457 546158586
728 93 111531164
632 304 662590876
282 717 301762621
265 715 411685890
637 575 239964633
340 184 238889314
611 427 89395559
563 819 241059285
850 129 942624765
991 226 698115735
844 325 514257434
771 967 424445724
640 152 353974763
579 249 921802307
956 450 24480371
500 906 462711862
102 17 159484287
444 357 665172163
448 766 913064427
612 715 61185656
111 688 575217935
190 64 707595824
759 906 185520903
347 486 180384990
302 705 468175736
737 599 308182358
171 628 323211365
509 838 247859626
350 239 251141421
536 745 116986810
898 728 379144614
319 915 611687505
128 454 337693724
201 849 559144212
55 808 114146010
936 30 297051546
561 286 594542697
314 138 412105814
3 232 773762198
654 894 137897784
679 915 489631486
360 547 321765732
309 520 716513271
695 244 476662440
988 56 329378178
370 274 334764874
619 174 619024321
207 459 865331506
37 910 645637543
310 369 661472246
758 326 587037800
665 668 505747820
337 795 116830117
920 314 496876627
312 407 830570247
396 794 115704802
555 276 889090202
225 354 237609006
221 226 940074788
197 534 281172674
321 727 201377494
689 442 884275067
719 265 937767673
914 287 346252120
135 298 728842624
660 819 466269764
373 204 113331510
25 927 31209462
861 167 225153328
80 196 173463698
345 259 908705877
378 23 773129250
518 868 366378283
199 500 709365756
929 784 135663753
376 930 129661925
778 816 722362368
840 259 915753777
560 225 322669036
721 451 450583585
986 407 313500364
467 658 739746797
139 570 5642889
680 416 480409756
781 555 637207795
659 215 309592338
20 708 870165348
107 911 915039245
924 627 81763017
2 812 539842044
336 115 468153841
823 588 521036755
356 90 236146477
586 474 8454765
787 934 340056931
341 613 645518280
830 926 594602056
421 175 521856819
901 62 26216516
279 578 323968761
257 143 539680858
81 175 874545703
433 396 983627094
381 997 86299649
268 217 655202567
867 612 390339515
277 84 346912396
32 701 32028065
395 680 288602268
809 599 762895261
634 216 803578390
962 103 924967204
361 301 465897522
807 64 892778003
683 656 69885472
358 745 834206960
504 6 601087196
713 177 16343792
36 293 997119295
940 660 976344054
760 411 885980688
580 746 944461643
465 198 536672661
885 437 240256462
98 301 870256934
283 723 260837007
749 433 395578648
228 181 900026342
250 931 97609793
726 955 33830634
989 883 513134173
699 142 425531446
15 299 51267398
832 9 910134774
856 548 112360439
527 834 304525136
542 836 845883192
982 859 624172917
1 427 189809940
241 90 583101929
550 826 14457147
537 970 567171887
65 358 436738246
858 310 127654991
173 651 163928302
789 259 523553124
403 586 84590477
419 161 199225599
521 2 177210612
696 3 718392552
255 986 686825332
782 541 361207135
770 64 544386167
236 930 68515165
21 810 721212909
38 448 638010942
522 778 197127770
464 50 342866385
734 829 269663659
671 717 926274250
178 375 971304530
751 176 962643345
420 619 728272108
706 511 414667218
324 883 632394457
305 656 394509078
843 612 190455305
941 550 293248836
602 350 744980943
515 472 578554272
58 928 294355688
137 376 891360278
562 323 512067311
805 344 75853298
382 226 587305773
979 810 700124854
285 758 125528265
435 723 24859339
352 357 209491979
489 830 104342060
569 371 191372062
159 427 635351274
338 166 296132359
251 298 164137020
386 294 390660529
271 375 208357993
769 497 823322775
905 227 447314130
777 928 80212050
730 345 205161434
209 379 230900254
212 675 747246582
710 988 743067534
213 836 582512323
922 58 571301198
884 165 909711934
91 454 852225773
977 460 64245382
919 311 298118414
469 758 707065107
623 919 294477605
237 620 683443740
205 603 106459824
359 640 181860273
952 320 448675113
646 611 667854219
202 795 505059163
869 308 727326065
490 474 247949751
698 114 877501448
18 766 621924522
670 510 54731397
772 301 882515851
957 581 846708347
485 634 722766070
46 532 21953270
516 829 124013920
804 373 246664330
963 953 510163953
855 729 571704469
764 601 887028969
716 506 169746842
959 37 531373309
222 285 123211364
845 321 619856353
364 563 811717588
104 932 258726047
19 351 222143187
108 679 484770633
270 378 642606756
492 462 385748166
649 17 618199183
254 32 590202751
983 596 349961264
608 812 318368904
132 490 13070017
718 597 136934143
127 156 429431604
780 439 920911027
775 527 408296479
53 273 762371763
146 370 608467999
200 963 637886414
990 251 218634531
253 327 648978069
295 25 599752551
246 829 122431860
837 705 913697953
617 625 148179596
618 575 545347582
280 603 626736622
63 435 285980751
677 491 9744370
148 493 157971120
150 488 649553133
842 487 859680900
669 914 525009472
529 554 126348776
106 973 498167034
594 6 597596094
607 369 606283544
401 135 480875721
878 129 71264498
582 252 545457098
397 865 799754
73 959 470885304
652 663 925709857
281 167 671215227
817 887 936408029
875 925 69120549
456 239 565557728
553 598 518710905
811 244 132375874
349 844 715614555
703 495 791361598
242 594 274516585
223 253 564201752
947 457 948708753
635 489 873787180
871 258 45392605
307 162 683387663
946 939 102278958
822 595 197459041
904 202 658810938
639 587 934074760
712 264 85825576
164 54 265286343
609 577 339434093
821 858 919745709
655 97 757481739
720 325 258378703
797 565 293319775
891 974 112531738
413 264 840219483
958 870 427960740
77 482 885829250
60 73 695824463
681 804 842350301
193 534 437624343
471 392 333688796
355 96 457246317
154 314 809952512
748 363 818594291
243 249 216700439
39 321 234531474
83 382 555603204
818 983 537053444
121 675 702011358
133 106 447769105
262 233 780460861
49 121 481935596
559 588 294832769
292 103 417594484
328 511 554313332
731 250 359241921
52 680 930649732
755 302 38894157
735 691 946216970
412 86 226109525
965 805 588802858
498 273 560793243
155 73 165767877
526 349 187483795
157 133 258880584
854 115 961509384
776 199 306745799
545 804 598132940
51 119 235913139
76 113 47220858
733 880 416398983
122 314 704412577
998 512 593508775
740 63 299630131
692 439 845734573
449 301 179277226
567 790 798065540
16 991 768112661
923 476 450967332
788 900 855913482
964 789 41824566
622 728 103141188
496 983 468655546
848 844 771387213
961 705 787368305
621 918 245065476
234 242 335838450
424 321 63274858
571 37 778554694
398 60 999182169
889 252 301010901
263 821 118577522
694 489 876852719
475 614 415772105
404 60 14105309
31 607 654505578
443 754 441524568
753 534 798472675
101 550 157828570
846 604 308952208
624 167 428294547
841 930 820112248
189 331 48309862
605 818 160891042
981 534 532005893
987 764 370975762
543 234 19619007
123 11 739650267
786 677 599598692
272 379 381959404
218 265 815802423
539 759 62110915
388 596 750258013
368 434 430539916
470 85 516055044
711 311 486580709
864 551 459375301
389 411 820683282
69 886 40050256
499 833 249480371
606 329 637331070
40 513 794061937
408 492 882134070
453 727 424623501
610 487 260962238
519 733 86897947
335 78 295873908
430 603 140288657
556 706 899763888
288 799 659407231
538 480 164321369
183 364 44386865
700 637 359221709
616 464 723220847
1000 626 725497936
124 788 584140301
747 47 510163049
501 884 222277902
483 919 746678302
945 194 130890253
744 645 64016406
831 465 798169853
549 140 669052329
517 50 912407788
105 661 480638263
942 894 366196186
674 384 380135688
630 179 442310187
503 37 922692589
860 581 394022385
432 520 32263770
815 936 678317922
410 433 355720222
109 352 56093799
704 733 606782725
508 628 809103000
641 705 93266443
267 62 515508518
366 805 926296216
636 977 830109264
214 602 144074855
417 724 683037762
544 494 979117454
339 268 359673447
383 225 506950281
134 506 133227717
33 509 370875674
672 421 56706037
117 121 97853689
684 529 451463032
5 550 282103170
332 286 517682427
907 327 61953375
481 781 84470760
219 246 384489302
505 742 809902280
484 979 533006477
414 866 182309603
28 515 993055829
686 3 11905059
825 124 26303286
909 694 720720861
643 591 136105797
851 641 625497839
66 488 845329661
110 971 450841256
975 147 290948361
406 952 9801629
938 330 810389577
367 811 886119171
933 726 582290131
897 500 580918287
585 333 782166304
687 780 290585193
374 495 584111085
429 593 177132027
589 489 455665198
682 443 616036087
791 368 155984303
785 841 230421604
972 899 300272612
678 988 226001402
291 582 196360842
303 623 766229366
814 390 836947877
334 107 447640943
231 269 972055813
999 98 955666928
552 84 58434709
966 193 238528009
574 723 211972639
824 840 895494083
985 76 205255700
168 558 589166460
29 679 914359402
779 468 184640451
89 144 798794015
642 892 729990540
792 315 607127646
172 695 569309751
300 754 812103428
903 975 746162645
318 101 968759920