1000
689073468 881081127
613328959 683799585
688380485 930935455
629559449 915788743
932949684 950947027
877829810 910303134
985669643 992204938
312798447 833411463
249441286 451905164
290340189 833433404
210412113 821807585
895850253 964636315
595166437 951075692
757114981 862133312
90271041 744841968
291746986 923609341
868745115 928061437
807205408 942618853
270829300 820457440
172053211 959956407
789768010 912413580
225964555 927334140
523524204 967512162
707005734 859237157
105894508 347443806
994465920 995622575
922919963 935455060
659528975 755794746
13587136 876902935
40155521 818337824
675977509 905225985
688817178 787860212
172825711 741247133
347591056 520291270
600832797 989005254
587126408 960652425
492751282 661670775
307214810 418692637
470125766 507189185
408286468 756924301
562598570 701980972
644964745 652646689
307569535 987599995
236487885 958457715
167262206 499552495
802305182 888931011
360542714 585690272
863692215 963149392
612059728 834794991
3877056 877108127
712603397 986978307
482559096 885080858
274586420 917622105
997173000 998297330
928988394 983252099
940735974 963510677
331452215 557178868
465220826 999455890
499947678 977869322
551044685 570082409
604674551 906976606
732342171 783227683
313613723 719953186
675403866 871538274
787962042 810930772
552453086 681880404
46607284 332792281
414742546 736323471
605456742 785227485
364907556 554476003
489489040 907467750
365255527 862854738
949120934 982820256
396359427 863377841
510568611 999955878
921369976 965930773
382953737 815170349
832848460 861880117
364894491 881903201
109294983 641220128
828499377 861062225
461214223 539097593
214644191 638347518
370215003 568130565
808320092 956536241
822776253 983119960
196192987 505335129
866079454 870282421
372003318 541117817
890547297 922503886
731650535 957151937
309879088 925340971
224090794 948684975
383853852 653183066
979567977 986707444
664467977 668892345
173266661 702773960
623997701 789315361
825552607 916100330
99812538 928537738
171588257 195554062
421703138 953243537
313093775 501118528
277718179 915487720
495064506 872187089
787207893 957299543
463486499 911434213
324896955 437129976
785715244 805361355
893368949 947964323
673289825 960992343
888988900 958415479
203279815 956761496
435855190 733475411
59743833 832569858
318954785 333294945
879716534 970290049
232356787 601284606
906694873 922816726
140089510 735166795
236963386 438790159
486207078 891622253
689484241 780757203
292494913 912509198
850121737 960806907
455683425 877925440
505057941 831601465
561611853 970842807
286178999 906847788
16224281 678055283
824834888 983010705
831075241 963353145
665671761 842420389
183950993 192247574
816185882 989904496
472860708 483185823
514434142 917186255
936556438 954034540
698210787 735531876
55731522 295695485
113226549 289843671
238746747 854800889
992750008 997357632
988733436 990559363
986371959 996674655
264939878 393414783
446945404 727471639
777461713 999129456
789543094 885323443
40318400 472737563
125687287 738008785
55291234 77663217
553004995 758672619
803253150 933138507
673152408 861256519
63076703 529054007
352974672 489639125
34950765 465815030
60641712 608320431
740887684 796048593
613823492 867736744
135429319 678258074
845404807 961974486
922000838 946356287
479910334 496494134
558095648 908537427
712741227 890855817
623628802 756012431
661341704 782352713
928154314 937082262
676002340 707455615
842633207 893015149
310988209 651417234
787313822 976153109
795149056 950075837
5357428 352832763
546663054 599237409
273147521 657868050
255443270 646836568
353362083 932071503
915251234 968136494
880224543 901992829
866133489 964697849
314634829 981050744
385228587 567698976
769183706 977736381
85941148 225854908
601017098 804943853
612366763 672487802
629287512 866704325
27259584 894689297
646884535 707662135
601198070 775945243
193251875 732012286
275498082 890172385
383657351 949318425
201770159 395355121
827595197 840940662
608829137 892697281
931756229 937963008
266218916 953680484
333530824 869184052
557957443 984380925
737853445 835963801
398270748 600905638
536826590 948250312
661394567 930625347
34508003 936009834
571774498 943489397
607967011 813182837
698274585 951917449
893910304 909007075
650553807 982212423
593393516 933161737
109958908 557543191
650792064 954580271
890049218 985784906
800172378 831886813
101936411 247960265
103219615 572787079
195931281 541007189
839160428 912613478
167422198 812939595
509242791 560919197
919011160 928231637
667874483 672188051
449395257 567933110
165161630 900859137
824585849 987406843
953434683 957639745
215618594 727017073
948712874 963781424
193511865 542541644
307471169 432461208
598466397 638505970
974703388 987494378
244552246 757105623
445278283 851358023
387111325 696303249
605894927 925615934
172272249 269891586
795550689 991925669
617239707 767525234
520550319 945849071
507190932 577356080
227075375 327217606
796896839 858375289
646171589 975533910
256821205 715058441
667066891 848031076
81166590 200900913
558484519 587266356
390919767 931984260
887091386 892860498
744756770 976975455
498792356 511586524
386932167 812703579
632408716 921632612
376088213 783916330
492122427 510017373
944388164 996682084
17614267 263296325
184570661 726903186
97240049 660485431
987824380 996518749
552630584 738758727
538629712 772195724
574884516 679111169
17924334 588373476
121820869 257431982
148229328 229938835
270844436 326865254
964237261 964530672
120253910 228207868
143269663 451743518
670676254 707271650
982560092 994171114
957680620 983387162
856284551 998676463
249852545 855132794
62247964 188126621
229073535 665891832
86060440 707328007
804381171 944387708
368941195 489457999
12161936 631653351
643226865 781330959
60555592 445553288
369763040 557165768
122137544 198682719
642276728 980598046
147332682 620035652
457897435 473367634
304201610 371935776
512949281 847652558
783780477 918593742
593232554 906534428
212800187 269655041
599799453 881511907
623090717 730609385
789866353 929515958
650763200 728815729
308119179 568519214
125721011 942016558
17499913 437216993
731735241 795545522
159385279 176871397
972993028 982984304
295503724 563514081
826846042 893196081
579445386 818809251
190942783 811425604
277795974 736904627
248134426 720444146
526470691 761018795
243384443 791380157
795954077 942453255
724702640 821077935
89455050 998382468
639359524 723426821
866719216 955029459
502873977 597544285
719081505 879628874
384764924 484129871
251999240 745571848
932617500 961799224
995425233 998114823
379377267 843721105
411972111 873437162
955047455 957797954
331533516 663234828
742561533 925984457
317279284 585006058
918136579 941310130
225128098 684087095
530320812 869901484
816277209 870548922
471922437 692601452
598578381 933940602
976580287 978117488
821526498 951578049
883617037 951598799
473750436 680713777
102097313 273228627
701499720 763240814
468288063 579244444
71426507 513036221
107177147 874622582
789721360 795779097
117023411 841604124
824307066 959085709
833482885 955212050
839003313 847194281
989856996 994145710
781947440 835804314
167986351 958661683
694148822 790033197
769649155 892147608
729025911 938698784
606567267 795660540
91464099 884982269
662582828 680806721
358935029 754213663
142382416 541590994
806499943 908157105
697976767 705264030
897139252 982125605
332395559 387074289
110981423 472354851
35263040 451307576
821234900 852011849
658429999 698566595
911305497 918087668
665436536 814809653
155082715 962414886
910986021 983738548
578491135 903593207
997922047 998866573
349507599 350006273
753734425 829375364
388326700 553538821
208428158 574890357
639062836 768478521
487087856 826185235
619422116 745831999
819933136 910378577
737134798 924575715
400823948 654596410
720973748 976089343
304804451 489046962
315621396 951153587
168007039 259722363
523622592 735730805
348987230 965089722
661177784 712054770
293942208 796640180
995268080 996802117
244004532 284345121
214778791 762641994
869932195 969094447
115405385 386978227
290727175 834115730
45333450 299233044
424703996 648200115
460480822 573067950
483304168 916026803
920829396 937352278
973307760 975240788
392723253 844143952
637097142 643391326
36980592 39248274
705080120 714386665
445628726 478306368
929640850 934700164
813410230 930446102
9057322 311820637
186308520 843676041
761997535 826065974
878536433 967971786
129495095 496378552
344448414 464571242
526484190 749554646
893064901 923197381
265815279 623074212
396576572 442132416
6752386 769080615
184713798 968082823
370631085 848696079
667544093 876476577
2064270 793270112
23851674 818475783
975235240 992269371
174362357 511477432
715655711 958974176
50645530 133014572
907737828 971489225
573012240 732461930
121353297 311487205
301734287 442120709
387169659 648578923
913955582 973762507
753606881 939735087
55104946 507418862
366359538 792340742
668619005 860024374
554061614 602839669
555808480 969179286
645602205 691059247
631998045 778369651
691459821 969619325
510846517 779595100
912056137 930584810
300673867 795237275
231849642 858839639
850930918 946828279
40258024 507722907
503473549 504332070
917501873 992661861
969865257 981760350
163658605 476738077
893548175 986986799
182906761 251948486
111293999 549470327
805281487 849110990
915542734 931615458
2599436 862773062
228095450 432647678
636700805 837211315
138120148 534099082
736494915 785779688
659977881 798157162
748521500 855482963
435038060 913925012
441454327 846863949
278373676 421068506
779043079 782177686
519538223 859671108
382544949 567078890
622586235 987554346
993460613 997572908
845079019 952827379
332843652 474003098
582870572 933739414
181769241 283036773
460440399 755112803
585375185 951800183
215153596 960911898
181634191 529842723
658270738 760182647
996253805 996468450
576064075 950321283
652351374 767416680
444328214 914773544
741174083 856184124
923394089 923719623
12098754 219555715
909217192 915470944
968963124 998369159
163662830 943852373
903600428 941091259
209885406 836776343
658998910 696379248
582792441 848056632
547257005 675885123
754685518 965951286
367303987 715054134
955061447 980034256
931394688 975413426
504025529 578215138
937653480 956234536
942990816 986097050
318765873 735285723
323833606 576313514
428498002 680698695
784683459 934221832
706065876 972229782
304426034 566672465
453215504 630118598
286472021 937530967
834809743 877495859
68526907 590761222
555130753 841594732
75538381 729384685
178025166 191259452
739524434 890257111
226960072 414958692
303579567 825257270
768655009 849195910
774177942 794423592
385063909 683085774
396930822 603507289
554013049 664874206
841636328 852618021
857775422 927896563
325164609 946808364
16275624 909565070
196185912 938535318
74793342 708721242
910531145 949181660
246398231 612320935
609237794 889578604
323169443 969407526
268816196 571029716
13712594 957638493
348230182 744473353
178607065 447697590
438308668 970767036
623027259 714933013
888818142 933187652
440741502 624301238
560459139 610580498
144064875 166861334
346692480 617980187
947664090 963784896
659519910 706303526
225114700 780708371
867631354 896971950
16929010 295085756
92539472 921728865
180504117 882006327
681404947 846890312
910821811 986570489
749787115 791805715
176102476 904188636
191093850 303185974
882955095 997600638
205485856 352978991
501857796 649552404
803426285 944057093
647665306 648270613
62664849 594521553
229839762 315157005
550805567 686434565
391192662 548487358
63608277 371534449
250231376 547806291
826637716 995942772
125335945 817698051
744832705 866890211
657545161 773581879
442760521 643152620
720075530 805583057
414286193 672502626
249623286 909836361
788813560 797869831
940877927 999143061
521626776 710751792
545340234 637149376
945451557 997887093
580297291 974882792
267127347 290501873
515013584 754999878
58717864 779240777
175983997 628913047
68192827 271112594
395304781 701958768
411379163 511804051
359299191 701417864
157580072 961579157
810363974 924196044
699334209 780726550
841739627 948975655
281128269 549231505
696131873 837127861
840933394 862927439
1923042 814108948
569649855 702660295
607331099 792015923
208377089 750227526
368446018 969093902
151351753 890669928
656687405 821140269
574955394 697151091
212781419 969958046
139137467 848101817
404208136 484103846
558272207 841894863
105613516 129682488
41976728 628558159
946002406 994619794
486177113 515623579
109468119 405605688
249865244 497074004
677747670 711881766
453190448 963040815
602951496 876310445
706354500 738956383
928134228 984988200
368687818 374525538
867286204 878419762
986910342 988078662
834218753 912070106
108485585 489101689
852723322 861434457
753835454 936785358
237215091 379279249
63448540 325381785
778889812 835215359
875238968 914827875
111254470 932059245
248667190 728882165
791413502 854575342
60390281 600940521
377918129 626842628
905854519 924975415
610486121 925009790
650397724 969396751
317840560 653053294
266714904 282674018
55244106 899378383
408283574 569694791
343716895 888196922
814337629 995776577
410321001 454363149
840711951 973366142
664168130 849222968
287924915 593362903
756219824 781578030
284638441 459116121
333464764 726808212
329790138 814967691
452534705 699082942
899042319 972655136
15426907 665274339
581234124 825087606
150492234 528625952
45367405 421219736
631718212 795341270
737067712 826246722
844607349 879147152
331612728 466288481
709130747 988316453
937134250 953364208
45519003 504470092
49066593 318165954
947232513 982942831
436775193 518397728
40041124 88078580
410351237 745625101
234024744 409093513
436379406 755296697
296159956 491340821
152275562 840663773
240926831 770416684
978947649 994773691
457492977 799023923
273551221 520326599
92934789 680770290
965870090 987294847
421635774 458517450
998606120 998722424
847883183 936134671
334005475 537925519
87063649 407553484
102562223 490392051
329091789 527985343
611348470 766327076
128284807 715216050
610939779 706296582
546347517 976860096
707726887 867386818
161155730 825739996
381042927 991596149
623782524 744314041
110762195 129249963
867178385 970167918
235668444 689965946
498540899 744573958
280031140 594651995
551924666 800306812
516329319 894559262
318549845 730005825
957895646 992190731
646386612 668427276
288390375 636044513
711329031 869846655
697133666 764258955
46808327 679823333
46971119 515519549
32864397 945297826
913671917 927464778
335210740 485318042
992149593 992359966
369141662 409235486
355630960 365340295
324644397 489875147
637049264 966515370
87188206 724288917
625903776 971148064
696765015 919552875
110705614 526803777
262589202 426744789
875754743 880779953
850919310 981483249
338201684 757611685
884081463 965688999
813957927 868282495
361193979 517906399
883227629 985149910
342522632 491705795
287038156 425312496
264152400 328329963
848687379 936564304
516667298 937917926
663484883 781703512
354880875 988749364
616784945 950581820
405956482 825049685
638998977 961789781
482681509 871673065
180917194 336423947
607740726 826700716
33058042 657231110
336896011 585379927
136462144 425391169
676644853 889704630
894767115 941968414
933626151 967688688
331602418 780647038
825555590 935927110
955028884 971922287
148516253 899807242
280111963 467266527
215920684 527172729
490501195 693594228
559865488 963938983
773529252 904328035
180430932 796115151
836308835 948845694
422017073 597576004
526891962 576994535
716158670 840413875
136031429 309936579
613962845 676076816
986954777 999631405
369322050 694119687
740215009 863159002
293748358 506645972
225126263 907638465
305286132 425101806
262639700 267774443
347647728 934368955
417436242 536499349
524636643 664238240
781474992 831460414
306064174 636910634
135976055 822057036
338914808 779367525
109088927 345467040
660903847 935353501
596537470 935429732
812713860 952113751
493708564 621900840
693062994 780673698
846394803 989386839
622282839 737838778
561110929 926888671
545695266 587527028
368469528 935993446
79922843 106376173
498735951 622649384
358397791 637777201
940937028 971002621
738973530 852615239
47022698 510876428
940274840 975799005
573654592 882163090
734887258 921090027
380652928 707311406
274482451 794303713
784934703 984331759
255742797 271515824
315633238 577832291
736502100 935202897
68729218 376875196
371919424 793587524
253765101 923534403
573896949 608127810
519805353 577299787
320176359 724047964
190109087 254758250
56129950 94183995
311917075 322197221
849621454 989465113
224020543 370107559
653709265 821797170
666192550 738798294
104172551 842704425
250794525 968936900
370037809 679563139
14586349 48131267
657414212 701898343
377467005 761533546
260518011 684664517
614720226 640583302
483517878 885954187
568606735 720402147
431323765 530582847
661462905 765321574
84757947 156689901
615752558 709352194
683777670 848128707
748656682 965024091
276730758 988277895
642799833 803352177
428342639 768889648
260599371 263144869
154539207 981372265
11907945 735255270
39017447 406033463
199710611 775449119
179140377 617003166
687211440 759376178
919579758 928597033
401223734 788808695
70901859 583594467
592862868 907953847
643665595 892774253
120115904 294237488
793379016 960909255
138072243 406597376
495671468 532292266
214403574 235498377
404181225 413010290
166977474 542722973
54379407 426345227
100284873 376445572
780298032 893512504
630314127 977479159
877753526 943338309
786887016 952270824
447438476 515254835
173199604 715418201
890563484 989331662
485511645 711265225
910313722 960857296
577886678 624065378
807558234 988965331
19963846 168041696
31464571 328921776
319981569 907161165
541736175 998711351
780447464 820427539
906187946 918897417
722584470 784292727
122560807 992346999
818549599 848408428
738853686 961391316
590375764 710180941
209780429 967971281
989514101 999335760
256812107 946982406
155196827 746055540
1281806 575383090
170040625 324922113
848918244 959194068
105591352 793751239
343497197 442407472
777968553 972013431
891261350 943522779
16230217 618015258
931506302 989635076
209010316 363240966
104188092 306103290
402580372 808482680
12545734 913872033
946781198 989488719
886230693 889119750
667961656 910054227
800630217 972423724
308008664 914614300
62102229 861922774
956639875 985527587
236722530 955647053
355647092 431922471
217238223 418812408
524417981 570421632
34011803 802864910
157553217 669781811
49215831 699108372
502808021 514697589
25843052 49336580
621028982 997440940
243327878 861098958
83986313 153067439
325668248 821330900
741304602 938491660
916050 447647594
506975303 800402266
518704596 869190416
997839114 998281081
689192780 999521744
675943627 950173324
428148731 878313396
111759874 228804227
692953414 887997675
333201210 854530655
367717153 654377889
205420871 917002651
916736090 987332840
691016806 790731766
147653583 594800445
999322160 999603067
620062163 912940078
37215759 478633688
117911855 188194407
174736772 815880375
577282377 890185064
755972994 825009747
292535757 608726928
807526264 821419119
85048401 468546454
909029503 950986795
418687022 602879286
67586396 787048054
115856351 708132887
423788652 687861845
987749906 991840344
583529181 889272163
946427818 989469713
166774915 990586209
973291204 995470199
923035166 944156205
983282649 984720808
458683932 472909429
421893032 885193867
466530189 727463273
75861161 162563649
107861212 482277418
739009345 910498585
396113183 696504321
19040215 846310911
65360816 534320041
204954658 384649761
144664821 886413428
563035012 872722664
148719275 380414693
678841773 717066941
578181505 897505744
769740233 956991899
615025803 877168779
337673756 470140092
641980714 910877773
376763254 971279162
539546590 868800623
249013084 505511551
853902332 993098217
15509456 292134427
566987740 940183682
689551557 750833386
793175403 959230997
2158706 774628468
367659859 963731840
207738522 462494524
21353607 467838300
269685077 432036061
927047751 930669541
991763002 998350437
812345120 929703802
796271344 956057526