1000
750 661 562786528
259 661 810006579
571 259 57433874
808 259 181592683
853 571 72589573
77 808 26069303
466 571 788505693
988 77 84714121
29 853 656858417
753 661 204395063
735 571 576740778
904 735 356085871
346 750 682850421
697 853 369630291
64 571 964449867
729 735 270001269
604 64 409511520
797 904 562438920
215 64 524037970
819 735 870835060
956 753 486775161
198 750 321198593
516 29 848114190
575 64 629361650
292 571 976698283
984 604 796304229
701 661 382969482
907 77 436622636
67 808 174694176
961 904 148401178
674 516 332593974
822 466 434202685
884 988 696765685
279 808 421606681
221 346 321646692
474 907 431774022
695 961 178580434
534 729 593531654
90 961 565011213
266 90 99837817
421 259 480625863
226 64 216126937
375 534 758999052
208 259 701197874
615 853 209311614
915 904 368700654
966 819 859045322
817 615 716409179
358 226 401529335
419 29 330284828
703 421 747212213
33 474 264272317
200 753 114820200
603 64 686805187
654 259 704940489
977 961 984944603
361 977 773398202
947 474 855313672
340 984 126298027
134 817 635627028
32 134 15675940
374 819 908415360
220 984 377952931
147 474 999631142
857 797 756751243
422 466 133516913
41 729 545488008
899 750 331209362
423 422 964652152
217 292 645343355
903 661 160748081
755 899 329196846
59 67 935875833
620 90 916140991
376 988 47699065
491 466 672515161
746 735 986714399
75 857 361902152
157 33 47200151
370 198 479222692
359 817 504959107
897 822 362089652
964 853 911793006
866 988 116009060
469 753 680902316
602 469 786112016
140 375 582487642
598 753 115737353
379 817 781449661
781 575 5072311
497 899 857208265
686 421 148136510
835 516 856425279
777 899 766446834
773 866 114649850
39 419 866560580
928 654 339198308
84 346 910667981
612 157 579768876
377 516 303018614
18 422 222105176
649 39 874805721
451 466 810409315
25 781 992729639
826 379 92641403
460 907 162623844
634 884 837010467
997 835 691567733
987 695 299289356
558 988 558906833
313 987 987193555
481 947 695882394
193 469 689026186
461 220 327146629
670 77 371594693
394 907 23634073
298 884 341463697
486 374 653409027
653 777 17642544
36 984 591334791
149 649 156297472
204 419 729418870
700 866 570759424
180 140 697085381
48 988 387305424
715 853 332730391
765 777 373249148
295 376 220873123
838 904 816455686
78 604 831267834
790 200 455719045
676 817 223840929
351 602 953746686
269 735 211917989
430 735 302304010
19 358 245119748
363 140 779269872
336 78 387786231
619 78 154918109
673 292 645417320
197 220 339531441
994 140 220695532
145 180 301092257
9 486 187555276
273 295 148766704
206 649 883965309
867 797 621259878
699 149 733104495
264 145 405037053
37 90 581380604
681 292 270050250
443 198 495293343
406 673 18622935
257 497 868907099
635 193 472507154
360 206 381196123
810 313 979031239
732 997 572479594
249 497 768386349
135 217 838643629
55 826 616441814
689 615 693418881
464 615 842442294
49 994 138328745
671 269 459132338
804 358 223093861
173 603 834663122
651 781 167411086
624 695 841863185
921 474 474600728
21 59 835545016
825 48 70202882
345 604 96242973
245 681 157364356
923 221 528093101
945 147 163039452
839 604 707803086
763 259 349173288
307 817 936637228
981 884 994306918
601 406 164184887
658 374 563469374
119 90 831048481
950 619 403162561
267 921 756444530
799 358 204722272
428 839 460991178
294 428 11161175
116 221 53479855
321 977 233200019
609 950 561664708
663 461 397963386
390 921 499371344
932 534 482858656
470 75 654021257
965 200 821743962
890 21 122676563
124 981 428122473
457 486 915122007
683 193 705810962
925 460 250814674
445 695 954656890
334 603 937077835
284 481 730364821
529 284 192987201
109 77 790089395
985 822 792460993
643 808 263080795
162 884 457055126
341 460 600288201
780 284 639759395
896 661 195214396
895 534 405791228
584 571 688480981
733 313 459398362
488 780 945203702
734 421 878032720
754 653 442741994
594 41 312729635
137 697 938320627
57 445 566728439
3 884 496575366
122 430 463151711
911 21 720566478
807 284 777830465
79 221 751665714
614 193 954132950
998 635 233889621
712 64 846678847
739 197 391846772
951 686 256653069
143 807 27719430
339 729 966586806
252 956 676507600
468 699 493182168
427 997 478667231
260 804 58545581
830 193 924590264
848 663 397252435
412 497 723077000
831 491 771203918
433 619 14348207
105 466 319241703
543 985 958754100
696 831 407437834
787 932 989036479
774 376 476601323
438 799 66775937
383 911 484742686
274 77 744635553
919 116 492033296
237 351 863453706
542 443 955179274
515 298 149358610
883 147 989938184
889 78 822198013
801 988 146379411
722 423 968061494
251 55 859150661
868 363 116546298
241 198 206829042
728 241 942584378
860 781 857612153
760 932 512808578
905 728 175355385
235 643 986897709
597 433 724531582
465 911 185736292
941 235 59514554
522 294 289749614
100 853 659406736
325 915 130484020
97 162 114668593
500 109 463517141
841 697 537655603
608 848 545572003
877 612 858985801
586 215 128249946
448 294 680107993
172 351 923309582
541 602 363456876
168 172 173611283
823 423 973977292
455 697 744792401
519 977 602885920
548 491 184635338
242 147 754330909
574 984 798827372
287 919 379581732
885 780 539419334
759 951 265653531
51 147 52479274
99 351 500337356
687 841 618583483
176 168 281070176
708 491 642981018
659 461 252618599
827 360 967649480
898 941 844098195
85 135 360863505
721 267 388300244
648 474 798006108
906 651 840322083
512 360 84690594
153 48 584334292
343 257 928688104
139 807 172614007
53 797 950745275
640 928 157035969
618 512 125338466
301 443 448438921
23 176 545440675
539 23 750134530
296 835 978752533
768 987 432041709
856 351 429844173
999 85 552072772
791 860 711849573
738 57 265049780
188 649 677042147
523 620 313289229
6 695 58667018
189 292 21406183
706 835 25185742
436 733 216216441
399 964 233825112
532 883 192801785
227 445 669206412
132 390 138130524
766 295 746776546
106 904 66023871
560 189 91362792
480 394 218388891
782 838 190204210
694 188 663984244
248 273 261415609
255 3 250770416
506 29 272303585
148 965 340511496
880 97 718645399
243 242 802158730
458 267 698256727
811 41 288370947
736 243 549663875
392 866 312138949
414 712 127864149
582 204 222769042
194 911 588987683
789 99 287464471
261 140 80570504
990 307 22117239
309 542 544630707
349 658 660859833
398 712 62256929
719 534 146754658
675 122 773448403
567 694 366801841
347 321 947390092
322 515 19634133
682 746 270784853
246 423 286751428
521 558 647352905
142 653 286484010
332 911 927266255
484 999 98806584
505 18 272754770
937 392 30905815
493 370 737399635
462 619 462063216
587 9 256550111
44 950 333600258
275 687 7544014
76 781 842406775
203 541 57221362
514 790 909734924
662 719 327633260
356 867 785476662
794 532 916664182
230 777 429250925
752 733 392591279
441 140 911099794
668 895 804066337
280 838 550299799
796 422 770990851
312 208 253151516
282 981 98917616
133 75 35599744
367 90 891241678
45 601 613915497
551 470 704179963
847 325 960424119
113 361 564539613
747 624 554203724
933 226 96639370
726 808 309733652
31 113 3188383
555 321 618724475
281 427 69843223
991 392 25476193
953 689 794698517
93 41 844623276
434 341 863041423
244 696 786100847
829 44 635732680
449 889 176687299
66 853 589884870
935 516 273223273
396 296 738803786
723 296 161335593
595 736 578244799
894 950 355213065
16 281 916918936
854 921 801453262
439 237 957160427
489 738 469379059
442 376 662738425
117 841 38636116
485 548 787117597
152 950 286310200
254 831 238957257
232 39 802763921
957 462 749318885
199 198 65601641
639 347 603475503
288 37 454536841
836 133 311592169
892 474 808200649
389 988 393083665
277 469 705731577
416 953 89495613
368 790 84697953
320 653 514110562
565 188 352117269
372 379 974651850
411 777 911017954
178 681 155119019
720 273 469292718
446 735 814867614
767 857 135692873
656 732 265575869
283 434 56831596
159 32 813363593
14 826 80518522
842 997 164197298
72 309 654616296
329 197 967727789
568 789 546601452
850 708 625691358
238 985 549985237
918 539 881954178
711 57 867398500
120 230 761772408
324 134 117698178
169 48 509586801
536 582 665878923
879 732 624217718
26 438 35601361
871 351 114151853
467 715 381491461
305 682 998684017
65 375 625702153
289 602 728470162
327 322 641030620
129 294 44479668
369 722 580682545
785 53 162452645
184 288 354663405
102 750 852077847
803 90 249171479
2 78 670990314
621 512 812515715
326 379 539310068
525 309 925489344
665 232 421568703
429 532 292198495
666 619 100068019
762 449 813480227
975 264 181147804
583 279 428219966
814 587 301223931
679 84 106217994
815 340 798448266
364 734 251092886
268 439 950194369
209 455 282884775
378 142 305472776
52 890 483888234
710 226 581607024
43 301 305800819
632 480 357438988
914 815 469269971
517 696 310027982
385 423 640594709
107 584 630198555
302 148 781134866
704 220 711016658
4 396 589929660
5 269 104283178
482 257 20608623
544 480 806276133
219 682 758382747
293 868 427421299
179 896 24563785
971 860 111068335
553 77 374853504
873 249 49472322
667 48 215337916
366 469 314198183
58 277 640968104
684 541 692088806
855 235 968178457
940 77 434521545
954 448 44145494
415 457 969466758
832 689 719584133
304 854 27202837
154 754 178315618
410 811 986266654
528 648 442896195
672 826 269105093
240 154 380315423
547 474 160684753
749 675 19927018
693 523 516491992
492 951 997221281
908 890 823688179
381 703 384911369
862 153 924318063
813 634 735451256
771 722 760138133
858 884 445084970
311 853 890958788
403 419 715679297
872 489 145285582
404 998 845944604
798 206 988338611
996 871 339594037
730 79 84125392
809 528 316921469
800 565 901365904
524 307 414668827
185 648 782332683
526 152 831899132
337 374 1998346
751 941 39200761
233 500 805234400
54 140 603044077
407 133 278108657
338 751 215150624
744 363 565744559
335 375 83253524
211 422 963083173
972 438 443519474
982 398 750800128
291 711 513865285
131 819 119907278
979 313 870695910
707 766 312640182
195 964 927638356
660 293 543458502
290 377 215255271
144 26 973300280
828 132 84618642
980 269 858975053
812 584 870971419
130 832 654975981
916 322 488317246
741 548 120509806
557 981 906814009
42 827 311339611
352 51 432354147
80 583 322622293
944 379 754694988
647 804 905156960
520 542 876553194
579 890 686568603
319 822 674021818
373 54 789942230
564 58 685039574
786 803 861386637
190 979 986516479
623 45 351315003
11 905 758870295
769 598 946199097
968 857 47835570
297 16 475967670
111 516 770129018
61 808 847413442
174 682 283538993
28 404 931793533
943 327 960756023
910 539 623332234
27 812 349494467
175 982 467890214
993 815 172957323
108 520 292725531
472 932 844905319
508 653 346690317
502 993 581883702
8 996 872476715
930 813 840272268
348 656 387784837
498 733 534845530
637 244 224925110
92 919 777988812
236 176 568370314
851 37 774120707
239 481 255147621
511 930 159804594
62 489 17286902
63 178 681882403
952 841 170710143
187 921 988029805
716 964 435690371
605 185 878012925
158 526 668437787
110 36 2514671
882 700 973545271
20 829 786498880
922 794 493217260
409 381 39257617
840 414 714394344
863 532 583198543
164 462 608134709
569 544 917729910
657 423 21936315
166 798 489004427
788 832 684631432
40 604 312302121
150 506 828730802
87 336 797405938
742 351 915478750
731 356 401504954
578 609 312375373
865 185 484309014
224 360 199878560
471 568 54091124
413 703 95374693
931 414 758249066
141 233 690313660
432 311 322650793
155 726 673479604
992 430 139170564
901 284 886165447
123 5 653411975
580 291 84721507
7 569 374042767
978 640 250332394
286 895 19316311
160 609 955496864
538 364 452374602
276 319 631116894
633 684 116852846
86 804 457518204
705 964 947378219
196 396 63710771
46 376 795226167
875 836 829539162
876 575 100981162
177 729 516512574
371 701 6162231
362 523 627933135
473 825 437979654
91 519 188214888
677 371 625020190
709 275 916488550
678 290 747486296
599 389 284978330
989 407 777740074
628 237 28448898
917 800 292103544
713 261 1489313
845 220 701529388
869 11 475420660
501 215 593435500
229 286 930802401
912 872 962053198
402 990 435276560
151 508 131643836
231 749 950959143
563 421 999706577
333 568 843282548
900 965 411026767
10 720 477797303
490 369 696104636
645 493 206169733
418 422 981508503
938 721 196100845
960 863 559350322
365 224 141593313
745 189 818251500
50 398 27323557
870 351 15711309
191 710 557650047
556 697 142923480
114 525 148317639
417 41 385461414
792 221 311903152
317 485 610872189
849 168 366058742
88 937 485229645
214 522 117434958
494 651 336733624
527 965 649260848
590 960 426707353
566 866 759507431
549 938 99552896
561 839 314182603
384 110 267421687
315 988 814227744
391 224 8806101
234 943 265805396
630 804 294434527
213 254 103467813
495 628 499995679
948 11 853672190
354 931 408536471
272 542 492444945
783 794 230298305
258 505 175823062
878 828 390672449
115 471 43502168
641 906 594288473
210 721 419656696
784 236 234834366
669 766 868678723
690 321 438743765
962 845 597618377
118 422 682066993
247 705 735070216
388 781 163093467
581 40 365764288
479 366 23512609
265 747 4505856
308 851 575463878
691 40 485585634
926 603 701991814
589 796 539660918
218 188 518779108
833 373 881849442
186 238 920979313
821 187 840690177
357 726 86345765
859 111 245439115
299 122 162741778
165 19 903807289
256 11 605605335
476 835 569526389
740 470 780915154
572 41 729366942
101 498 170157255
452 180 812024245
820 972 173777272
400 62 810363184
171 777 878685013
225 838 521633845
504 329 612683157
775 691 913012118
983 186 769807225
924 780 538393630
818 442 78171366
540 745 717070004
483 294 463655162
969 640 123654461
743 162 318909792
401 544 259754508
74 853 135046787
936 972 306076728
974 133 954600005
499 643 713321813
535 903 835034756
577 206 688755456
13 992 418336371
30 291 48673229
94 265 130143096
805 528 603529949
444 42 720424426
593 948 646482450
83 529 696873119
163 569 705643780
958 978 331487625
181 977 737750095
453 288 688365696
617 775 657484027
22 517 761301168
487 135 270651725
397 674 74885707
902 255 521582211
874 945 987734816
573 865 867169043
600 536 443299812
770 979 990892261
531 879 42590055
314 186 494741854
342 129 91399256
717 645 810180435
34 64 571025661
81 560 709394649
893 762 410133992
300 409 84107187
727 769 791879702
437 958 995908853
250 520 529226573
393 786 402670124
913 734 513449006
303 407 635616085
450 801 714360643
946 528 2461158
136 99 285707624
646 171 70982198
995 354 793468032
685 422 985485581
426 950 193914866
852 433 950947779
128 119 449825472
253 346 956802203
644 893 788319822
353 797 373752275
1 164 631623507
642 444 251107416
405 36 208080192
631 320 227019883
350 997 966807752
285 255 899259245
629 580 408048760
588 790 61282566
955 243 500266105
757 409 532651909
843 900 747943056
330 411 650808583
456 198 13598959
942 371 2944763
636 421 318338917
82 803 140946159
156 265 966714011
68 470 72284797
73 958 103972303
550 693 869990432
909 474 268525894
718 826 714131977
89 483 178948788
626 678 544251425
56 179 592042810
530 944 3332646
834 143 278911756
692 200 796941914
967 81 806160163
431 179 852767192
613 736 682757277
698 555 833361508
459 741 185061412
537 521 57780173
939 280 905357410
503 356 55086005
161 620 670247729
408 693 540567163
533 765 445667640
761 21 54808501
24 829 394439394
355 266 890451718
216 405 462621440
934 421 975872458
310 561 67307043
509 678 198270567
776 28 21703683
96 377 708202042
844 51 892939663
69 142 245380160
167 36 738223899
652 206 39990109
546 45 938688086
702 321 637490751
104 299 154491044
212 821 954852107
507 296 760042857
420 975 973379500
202 252 616564086
724 948 415149065
146 974 20281926
778 176 906697933
126 260 51526092
98 248 305998696
35 841 373508216
477 158 849388617
611 692 491190108
95 831 851860560
846 176 484521099
125 119 16421326
664 168 258348398
562 771 234529227
596 398 239834736
15 11 577525907
271 895 176520839
714 317 254534564
425 791 829027698
182 883 313362507
306 822 155013332
625 581 560785073
861 505 603328348
592 631 267748818
183 703 801555703
316 571 107596593
758 699 582716259
837 391 375390546
622 439 202384379
737 319 356710433
616 381 764232593
395 389 291965663
881 401 628067204
518 911 252194991
127 202 356180634
793 745 761719583
17 807 404439749
610 495 20320734
205 859 900249825
71 953 104945274
386 902 133856117
891 776 652902560
270 400 408294697
223 739 162488535
278 739 958801194
559 660 181008087
170 860 268615554
103 414 3493072
627 565 859048446
585 292 475176228
380 143 748175131
949 603 906155864
513 535 475436402
38 511 904642766
47 981 283060221
886 529 428106019
976 338 98249686
927 329 400491128
331 815 473161789
802 699 900081865
454 267 524571203
496 51 427145678
440 224 906288314
959 714 544302410
138 128 737617018
824 539 362393041
638 522 445996513
986 254 102673767
545 966 454799077
552 977 868525709
680 744 463241309
112 802 886411025
323 324 384251678
795 860 9406767
756 950 586915187
570 190 194240326
222 849 687964073
806 59 791845701
888 685 230314787
764 863 566010416
192 443 983565583
772 974 350292849
318 303 36530466
688 295 878708753
1000 456 527397808
382 5 901199322
963 919 390386033
591 485 857701620
228 304 290955728
12 334 409607221
475 402 942843607
387 971 880744539
725 664 269429193
70 394 715367351
650 459 461527799
607 903 713700228
864 125 845212298
606 918 520110137
424 996 948055290
435 587 124070782
576 242 107358328
929 776 961062436
328 892 188779647
510 491 238575730
920 395 513523247
748 135 997343835
201 17 477671758
779 236 723111732
263 139 111832671
478 99 894881595
463 145 88511842
554 760 605536004
973 722 976899285
60 589 680485476
887 793 204397485
970 704 667045471
344 606 333194346
121 479 363235262
207 487 939555091
447 307 29103327
655 122 475529081
816 618 252416357
262 269 512308556