1000
618 578 432974836
746 618 355784989
912 746 180876850
398 746 159901051
990 578 927042793
943 912 523410215
73 746 36023080
669 578 823223455
557 398 986607668
894 746 452054608
135 73 930248190
864 398 659659385
711 578 569061734
119 864 797479444
163 746 715660871
363 119 518859854
919 912 980005727
935 746 977523858
373 398 156757953
459 618 707042976
351 557 902000644
567 119 118086133
312 557 27288156
641 363 599880968
845 119 462313651
106 894 817741714
30 119 389029083
321 711 674155117
532 669 960445259
429 532 408476250
803 864 646248935
360 119 505968902
201 163 951715778
847 943 891460996
817 641 586261290
909 847 681026478
566 919 584018995
875 363 438134191
534 847 73272384
295 566 305868522
203 429 16220681
593 746 242739534
86 106 438505382
770 201 585410670
330 295 999067677
560 711 39546697
531 909 694232968
328 86 538472863
112 330 690999639
249 534 550151804
614 363 431011768
544 73 38553941
425 328 990923309
973 864 386205717
174 614 277205956
283 973 935027042
584 373 44173741
303 321 927462196
34 532 544651503
931 328 704098838
153 86 434893987
835 711 961375299
844 584 434119976
871 459 778612943
601 283 383318730
942 112 169692927
262 871 764736623
219 871 751906433
609 912 181407547
298 557 576655492
655 398 313174028
989 174 671281461
751 614 901659378
123 746 447972914
608 669 69695685
678 174 563479354
394 112 974214977
780 669 222364806
296 135 424205169
732 943 202951679
699 732 768118656
183 73 117513168
640 593 303786120
310 803 288001287
247 935 418629720
307 618 618867048
851 249 661066994
111 614 6495840
402 711 967138595
621 111 17292710
352 328 916703206
499 73 343446049
16 566 134540168
245 219 144715747
208 30 406997105
294 352 356733145
731 909 373015037
796 247 932140256
749 817 80292392
582 618 101099268
146 294 329010394
533 803 212149486
755 283 443699811
64 534 211305440
638 245 450918131
998 678 874164358
406 532 881496528
963 112 426474961
687 123 254512634
332 655 669635481
650 618 110058800
756 247 624564114
205 174 414835575
186 963 958389040
712 755 94873172
863 532 564324010
451 593 791494970
260 678 980453435
214 201 343080997
753 352 901864328
660 989 716003005
822 106 652756137
895 669 206668882
215 871 311363809
668 203 351887766
967 989 831479249
962 86 931733953
546 963 874773230
924 895 155873239
389 64 354201945
436 64 862340196
299 731 653426361
475 638 686345748
414 962 232104703
768 363 856655581
56 608 743329745
304 414 224134832
441 360 823121764
867 111 958396565
318 328 402136998
991 146 841576500
452 822 223966572
187 919 24931027
606 123 226418885
78 566 886043617
155 398 358562968
380 201 454485019
543 601 219590299
960 296 504460375
76 380 628710269
985 924 294026894
107 78 264469278
103 909 833587110
133 655 434758871
685 606 745127671
226 749 759538670
764 732 263242896
824 429 996177403
624 296 7767540
766 641 656280217
688 640 702319782
743 688 158729979
773 214 824491342
964 155 619481212
648 655 309505818
393 894 365183316
227 394 616183051
21 187 532432957
213 310 37968052
586 871 909691795
920 962 336387134
366 796 110756488
850 678 620937397
179 389 251499506
150 912 545125906
454 895 20840751
978 912 62902340
905 318 164599097
615 655 465835611
322 208 997564161
820 624 346441526
797 699 856661851
359 963 127581014
484 459 306157352
141 919 745063847
883 328 585877994
511 624 549517018
327 875 942999483
703 360 667088716
598 318 506450754
627 624 86456126
665 703 615066496
1000 650 37207315
498 78 976695147
68 201 519209931
167 606 481403876
301 425 45213420
828 380 987340826
787 163 318908074
837 245 166862569
657 598 796075036
176 609 777949639
758 429 523600510
591 665 752406511
171 205 948159465
391 174 507128317
37 640 498866121
982 533 911145017
361 330 970467721
287 155 352232946
539 703 645556977
509 402 27995005
138 112 638930534
24 394 12272626
992 894 896335174
416 586 43347895
378 967 324463721
910 820 997027574
375 567 857102877
719 780 199908984
922 787 970797383
424 910 847767169
403 609 147443637
530 699 564348838
653 332 202382440
696 414 546781567
829 665 762042683
270 586 581825343
195 451 407678690
626 822 834313667
589 68 136371222
54 205 764241857
368 155 318864051
170 608 761530174
317 425 51921539
887 990 646454599
988 829 52912094
932 964 663717716
417 133 570444187
757 119 99294555
956 731 541235014
348 378 92301072
386 368 812915385
716 638 445435054
377 985 87858246
555 824 846873240
906 867 123381448
542 757 189998292
772 307 74663283
730 378 784943454
882 773 910363320
120 386 180951251
946 924 139689293
784 321 680166598
430 963 697725138
62 186 691603345
671 678 548191539
568 924 500866932
987 436 533692930
84 803 861998354
290 912 538182848
647 956 704349260
886 755 906649656
670 441 261563114
679 203 99805611
281 584 595795273
879 360 767116759
122 962 214652869
160 920 130719281
585 864 889909206
289 64 221163541
623 429 268304607
189 366 611065799
739 120 439738081
975 30 224176170
741 294 504520602
721 586 633164683
297 509 641781260
223 532 181797947
2 174 845443258
300 317 413426646
156 459 442774692
714 784 245962507
729 920 491079539
868 623 366172939
66 283 692765894
38 498 154694145
713 133 4600852
878 451 31437096
733 106 355142962
884 378 596972375
629 699 440759134
364 615 986693351
81 38 198517628
329 935 566963575
149 922 993576918
945 322 350005496
908 660 635583186
212 624 396772807
432 962 641827277
747 366 443500960
661 160 769879239
422 716 871120076
504 424 5126984
692 366 446885197
993 879 861858186
583 991 142845864
384 484 661098732
137 533 658814430
792 498 517996521
965 985 61722618
619 629 55663622
198 753 133130449
637 844 50353216
937 648 765519338
745 935 492116069
376 86 807629220
710 205 761235330
181 380 433517965
869 710 4007450
720 475 604316202
488 713 589126581
930 796 777105472
23 511 71812701
450 910 755721795
958 991 744917553
19 459 960563308
899 351 94288817
358 543 770205235
489 119 456573418
813 133 109440142
467 300 384646275
234 205 128148865
825 618 919090543
413 787 250947779
420 747 168725973
951 930 826580304
89 988 332447478
832 714 31287483
325 21 353573937
736 391 232038767
607 638 641720367
461 884 263305592
580 710 997672747
830 363 707396964
538 965 206986051
925 626 840133596
347 373 428564203
551 886 948542903
707 749 855805584
362 657 417788995
842 825 176953806
917 393 783378321
565 772 430356200
552 198 711088147
370 919 536680109
893 312 892875786
570 452 344277788
57 943 234093441
767 894 100674099
191 946 75064370
907 935 617962378
693 122 164814245
612 289 41065005
490 317 103172835
677 149 684692541
537 608 820704272
957 394 57824816
145 351 733897331
771 307 731285334
814 533 174831301
548 37 84947616
903 403 498624875
997 16 585696277
506 978 553853920
625 967 707364783
382 625 169184134
914 963 667419764
169 566 454486700
231 539 394387368
116 894 350803775
861 89 487636777
319 566 413831326
698 23 110227738
885 327 376228507
349 384 841851922
166 893 159980307
595 825 109572422
357 914 274583198
853 670 404046953
610 985 271040841
969 205 456105376
576 116 11518800
374 619 418966137
897 208 136709944
152 170 249872576
418 19 474272815
395 882 996004645
439 116 605313365
620 935 226614069
385 719 967061406
900 24 316511908
128 122 214221217
246 330 270565672
462 283 398332798
550 260 465769492
90 593 351385956
644 598 969181933
291 498 78240965
29 879 474276139
934 703 916953549
98 422 261292558
426 511 551868248
528 534 807974527
113 170 17364584
323 958 570753652
88 719 132776816
185 29 403439108
694 934 422242915
667 720 888350516
855 797 99766725
118 780 649790279
229 610 608535646
108 156 930667564
52 612 471309587
49 290 674704597
590 875 552839655
651 608 590745690
734 648 38373479
902 576 52018597
151 283 851249757
659 566 375639594
702 150 509294373
750 668 379037318
443 246 773474614
577 62 919968693
517 978 692660058
41 462 48533000
10 668 548325126
695 552 575714056
572 374 23810763
431 997 470473110
101 767 785295824
821 475 484207661
846 882 101159685
622 544 172273721
476 212 407880393
25 205 201060405
446 879 408156336
735 832 424540668
399 450 746616998
404 171 545931483
343 817 992017482
125 659 764129555
918 391 213600030
172 76 941397126
396 304 293839672
196 531 537777144
889 467 851922720
519 532 842235963
263 156 299989445
79 462 431735887
873 281 283456955
816 452 859629322
579 98 680307133
642 565 177711407
438 146 850191136
13 593 484206638
233 869 231734861
442 593 7733851
33 89 754125091
507 568 211758221
981 736 583115423
540 461 624276944
649 68 915666794
628 443 474083639
168 741 988744384
496 719 264687120
856 176 687142652
162 511 868567293
61 729 302655867
46 767 405078241
521 146 947284468
379 301 837694789
316 730 906669685
20 912 565546764
672 924 158854388
689 626 405584051
512 21 91592685
274 557 123114017
866 153 290256352
502 699 387599460
939 163 633933219
646 385 487328761
284 925 681847193
599 932 887993273
255 462 166185743
243 670 74365745
40 614 726563498
69 579 398763160
96 912 173018466
915 24 147745028
645 10 552927473
904 534 469296622
235 172 99633684
976 274 286536902
726 425 412049636
575 300 183950458
723 578 749997077
892 205 721395963
421 234 360766443
469 846 970796207
434 1000 275878139
592 851 583020477
862 626 609644969
455 599 449390221
267 343 990783661
833 773 121098435
663 310 237814927
3 714 5279544
664 855 607504522
232 450 189455651
236 135 512187722
952 568 152560308
744 659 679079713
175 734 428197513
338 821 547561383
242 734 643093580
309 76 493776178
387 317 688785096
480 736 246279341
559 924 99480000
59 797 670659834
877 862 979527275
335 40 318074613
285 138 859241340
633 750 229366351
7 659 817899936
632 601 100929710
190 155 970663207
673 714 628617428
681 650 150622923
45 163 577060401
177 489 637954337
197 712 359229923
486 234 614312765
144 167 460585744
684 243 798973697
763 442 284919647
826 651 5040879
841 719 330310539
865 358 65621436
857 424 658039321
594 291 529830634
51 25 852957576
972 382 13594384
302 236 950148742
725 719 278033321
445 46 538881889
22 169 483030186
478 615 462119522
501 144 852890424
785 116 208601974
92 321 594491964
979 504 843762901
218 431 168066573
515 170 373397326
843 628 913493519
392 590 288972183
275 462 194153252
701 176 35747170
400 489 65479365
549 614 933321028
959 560 425003248
682 835 68746140
306 988 356746187
705 732 813473054
573 54 282013074
503 298 335194006
458 267 850639548
955 900 595561043
390 758 458166341
872 62 894176644
115 90 118820292
929 699 248416215
911 886 969063531
207 364 735924427
786 862 1032232
754 79 370588509
769 952 179736041
690 865 166379679
759 638 786165295
407 54 705818657
154 176 553418006
240 310 334936105
527 480 145250122
799 542 718319278
369 865 247313639
134 152 747907278
31 399 687414132
336 281 266324794
5 829 282461664
704 234 703285948
353 665 837809205
356 895 424168343
367 593 632766639
87 559 847694390
341 982 369470404
556 61 898624665
913 847 813894461
823 442 261685342
928 909 742012911
807 592 967555895
70 618 59762437
722 532 10174220
372 897 834787145
481 152 470639966
778 689 116693073
265 275 860504407
463 548 553762557
412 969 612465836
43 198 584498026
936 918 989059242
662 370 587130125
473 49 164400031
109 454 178307536
411 900 257108084
36 699 891369545
204 150 938520301
691 942 342970774
795 420 347438287
180 978 256927373
523 969 281255332
147 231 467304876
269 990 316357497
15 128 581119604
818 627 325394773
656 615 64045619
355 208 690986596
654 23 799153512
206 879 302976249
365 379 538954087
58 608 6204064
465 653 422486601
558 772 353330136
553 573 226601010
75 826 59987881
999 865 89892604
194 664 671503734
18 991 959495609
320 893 575508342
881 169 166877470
85 698 18310405
35 242 285353072
460 905 363478412
898 426 476514890
740 138 727650604
117 116 743858200
802 920 101891051
839 504 183787940
308 49 197544684
724 965 717339432
880 385 336725747
165 243 895022357
858 656 561491479
944 606 875586343
485 743 11894865
6 362 323773782
977 359 673502154
970 952 780550394
474 754 926584731
345 455 249579306
617 204 45707661
761 475 473813838
948 667 358838830
482 747 594170186
831 284 102130968
587 385 371781444
809 289 292692071
158 987 876994391
561 677 958354704
130 205 567653286
11 214 976134677
44 592 259424580
510 274 978903830
401 628 894758048
256 823 559327926
272 364 586052775
494 194 295826038
200 321 119548668
980 88 557828609
132 696 814154494
140 985 513159610
495 572 878876236
80 485 903181394
888 195 541765022
891 622 144060215
547 830 656132844
676 871 627810374
148 772 627311396
737 548 467820150
782 628 838278110
541 1000 307009675
405 993 479271256
333 696 300511293
202 741 828382172
505 319 303819261
522 747 842494569
466 864 644744556
409 101 509356183
26 964 228924740
241 374 371229041
479 452 644222748
513 857 432915508
760 375 785867525
344 198 544333422
435 875 774553238
890 847 197092153
276 553 595457542
278 957 695228196
266 690 307278850
940 54 329771906
159 608 802319079
428 117 810590993
630 152 790472918
82 691 592127916
97 128 116250758
9 770 134297446
798 92 818795459
605 145 933128707
718 21 633448757
762 586 935998535
339 567 391706862
854 758 633685989
588 187 620862197
966 412 737842353
32 372 661128383
253 608 637540514
801 607 170746286
923 185 659914985
188 482 407520821
500 623 341860577
292 132 998938104
472 223 789405948
545 177 811975064
67 684 921820707
282 495 808826215
104 882 435741576
371 975 221148445
53 500 15756527
315 684 891714353
161 345 546185473
563 655 475460014
793 159 563129442
800 476 62009321
597 302 809943228
686 375 425403919
221 223 728817742
516 156 592960272
727 784 831820855
635 270 217949187
708 395 458342929
42 552 918637208
581 490 390193234
39 907 297620778
464 820 332898421
17 64 419066777
252 226 617842769
83 153 395060595
342 79 784604706
901 214 63565888
305 109 613312625
314 478 479369131
127 450 352771896
257 115 624939879
675 530 126837801
448 256 493035707
927 499 414445595
776 118 706967507
995 862 630136372
199 801 366662201
102 710 445598901
94 722 208725482
812 884 86591695
192 133 672952219
340 607 76582081
520 30 854558002
324 772 249808445
268 595 646820134
775 241 757745113
860 880 450729027
142 149 544507199
193 770 759804916
954 430 371252367
74 676 606250049
596 424 184498701
765 620 647948971
535 924 337466562
230 309 384886823
383 519 196666976
933 174 978027932
288 799 74743083
388 934 705629191
139 544 183685791
834 918 778125112
178 688 93298189
774 832 250627959
804 81 682834247
95 665 808848789
71 358 168760818
311 406 892477720
811 385 765740728
748 327 230817784
136 172 647748549
742 979 767466540
244 995 275526695
331 677 176167238
728 748 927922260
949 385 449365947
4 500 471587581
788 172 532989918
514 49 557648287
184 291 520894686
27 151 511250803
50 425 534785114
346 705 335892679
674 5 158155152
220 241 792458195
65 892 518533955
114 382 516096179
643 64 358821842
487 860 680613291
564 584 996163354
971 882 56040658
996 799 862330989
805 257 47149066
477 698 341695821
968 867 62540516
613 662 99381090
210 39 170079480
456 511 894264704
228 52 155366144
468 322 109056949
124 399 175763982
600 475 301115976
791 389 734809856
631 38 91259408
164 565 411559419
408 787 680850708
121 118 804096892
493 996 149896139
453 382 647404120
602 967 32547271
950 937 179906499
794 954 68717258
926 731 827503611
239 549 654194688
182 194 738806937
280 917 449731027
433 29 409266290
604 212 524262842
14 914 61799564
63 851 98415342
961 660 275783263
131 330 732319727
870 297 98069312
518 742 234761264
277 58 745339664
126 305 828932123
258 521 362702683
28 909 808622370
437 122 748043500
397 282 921375862
941 842 750817618
237 450 263463774
381 458 273117594
836 181 668650155
8 649 473467801
259 469 620993265
779 672 969807101
953 306 43453452
574 573 422490592
129 853 739968096
238 502 302677939
410 903 326659160
974 712 283639440
261 987 495008766
337 703 32100132
143 693 239154993
483 712 445984583
916 416 968537526
491 989 287178724
808 196 957853941
457 784 735443165
293 253 351034085
427 895 273637658
983 744 681248949
697 782 339676511
810 649 442057651
752 981 663599573
415 483 600537371
471 834 436131084
838 596 285616087
529 660 303972912
254 659 306334193
536 242 299823354
248 714 977653739
222 624 513415813
77 170 72874729
279 942 950375969
423 293 34681135
569 997 271594619
271 557 961564367
815 929 676945678
105 332 873602156
852 87 766095584
652 78 668150935
859 779 317196428
562 221 462068719
554 548 708477124
48 721 201161323
827 294 198175296
209 892 552228021
783 930 696378835
738 210 196546262
470 190 264015895
93 117 35450899
781 171 974887488
603 196 505492784
55 534 636053311
449 255 711991121
658 864 509276525
273 254 136909462
717 743 809200238
683 336 676028703
12 996 369364162
938 823 28883168
1 659 293327360
984 491 972975256
524 208 431536885
91 944 410849016
216 776 752097099
571 836 617839950
47 32 9452179
211 687 312394431
526 931 292548952
447 466 782634586
110 704 214088472
921 88 339261896
706 643 336480655
326 115 914994262
525 20 349248605
986 260 78107138
777 776 742135309
497 966 988805407
60 77 630152393
217 527 503180770
419 704 684442713
173 936 8651537
616 465 705349980
947 457 198004010
700 542 292496763
250 479 547702834
225 67 934160994
334 998 777624981
680 257 461297204
790 498 801629005
72 293 203878900
840 797 294962357
806 295 524750681
354 543 864853236
157 802 384105177
639 95 366707376
715 598 624920920
819 820 470718243
100 679 130272729
789 129 296949957
224 548 366859938
876 834 174737499
492 788 776394755
709 120 852112377
896 95 800220932
849 258 64766564
286 395 943827323
636 652 151760375
508 966 941747780
874 692 160929962
99 857 159917153
444 132 43925965
666 594 454300874
350 746 253349193
264 143 661075535
848 398 588499079
313 73 867693555
251 411 119675795
634 20 31295425
440 133 437711416
994 35 895479650
611 239 203127505