900000000 1000
11934038 257096283
405355767 570001955
876668629 249890139
453495728 12239373
657165788 462212374
822553808 432021485
431563805 561217651
513669276 596309475
157329680 583456292
753259864 817005401
432371535 764906373
878606404 665378586
22850648 457512559
378828995 310391949
517676786 358387154
57778895 234935851
286932955 70661223
313685585 726407939
137284026 322786144
345885308 196175637
76174299 472691652
241344888 570145879
422662267 551503624
370936582 723241644
130682547 30850808
357167624 377618616
294693516 409051491
612403153 820510690
708799212 302881898
343264306 157396472
464367498 122202911
290066783 714340663
860127216 68456346
685303703 514620658
73755466 696612187
648158321 148189045
854241674 737596750
34368502 35368042
489033375 848441307
243106722 611963689
627027155 280522489
41781762 194145632
479342947 401801721
202048698 509720171
673295877 268952783
231195725 162102917
575680564 775958558
107789503 474618094
785075390 588933550
672841926 536587289
402372406 791994681
639681959 490327554
710798528 662237544
548231586 714360017
505617061 472759929
9526547 14394691
72903212 27825976
466880371 291171310
463312759 840989668
199591082 568766757
125896335 643263963
800645085 774086752
328990048 801797003
434216324 532117512
883455897 126184681
630426411 840357157
758615295 34967187
548233513 114695036
891271921 255982706
773822128 344004994
218409577 505987787
320549356 502625062
510890676 874736248
530003798 259416205
652487273 670844328
879325384 566595004
566639153 648711565
284892719 776727026
464364394 191938887
544388825 665425097
428805671 603747188
308681547 819699460
866129910 442215824
320646371 225675425
148589448 682253313
447778340 8921056
150015577 846734834
107084034 539101490
319795715 243823817
362245741 414787566
872756181 253547346
727962317 705290853
834928493 746563922
785515710 102680176
414644850 537521718
174776607 496455355
278394142 798751
162110508 772369497
592721499 233228698
473171039 650019144
868116467 506755801
602200108 385590263
695891714 568323447
425601652 606474195
684901119 895016431
133504232 67445293
463927908 651081206
531739847 540750069
448590805 172119411
378403653 156170892
729817656 684876409
350144953 211036017
35289397 495254238
459585023 160299948
773196665 511645578
627534228 394675862
461255785 258396241
50630450 51788475
588737679 188083900
135860279 597833065
621368390 569174954
182971379 584353445
56318486 321105441
506259426 242887078
872176986 500041964
148084161 806764725
93165636 841352606
457601961 395240981
744734805 190388490
549468516 271517637
513524772 254574588
366558027 420794655
7737822 301604251
760104459 576674645
454256470 589398813
571044162 794652011
828661254 599297229
350036668 769586546
290526110 409522167
511341536 519760757
654570420 739914081
201058618 30059796
376387938 219036406
868410119 263179024
328362300 468506374
794106747 677455115
438672230 323651140
752252989 138792246
666505938 362803485
457277928 182247928
416580269 708379853
768207589 693083368
70975105 29023522
832274696 741421999
67915544 678845107
415119288 755219017
224303948 734694576
377824425 63567451
788435342 333885487
183449833 798498997
401631779 44638487
541134769 848784218
238486466 636689683
311192747 832547991
197616032 111256297
472512282 36469785
195957328 525463893
279871844 685124893
18475761 780877670
264440725 620365458
415013978 533830134
336579186 325925188
76497342 14002731
130925505 253505145
464924891 235043669
757755538 4472345
555680129 279206096
410475158 295270951
463757803 615706603
357736001 558782322
586869614 858166411
835741050 898371776
789779330 564476737
213641968 150631976
876565204 331525567
203098040 633105971
748929698 479011248
638503725 484224027
192621515 695394284
675977305 268453458
690215587 748799630
451230010 132748639
785228086 711641206
367369267 761971031
780367853 721537739
293534832 534884909
5072065 441738503
817984952 431306239
504388819 640817138
341258525 306455953
50613127 707728118
137663754 811284790
19625315 541029562
783259145 437499833
686860514 878684905
539215677 202177444
383553086 579769962
783533410 805912234
765010646 57044997
292656852 459707366
710330705 653984373
571719858 786280576
428602957 717284416
584570756 722050598
406459014 602479721
365159910 210653497
350279812 181647833
881140748 83070901
223898193 39047654
568409990 735586411
44054829 389761677
505912731 183092298
127358153 442023040
626153564 427959736
548224073 361424880
168480060 105867278
351602179 679412903
398335506 686878542
360462406 682790417
336604959 645317785
264372120 154090101
307820466 453082865
179135299 535697360
759693611 242469107
519580096 235628285
704021692 66661439
78114170 433210211
728229254 553478060
155292870 675809528
596435569 770255399
833861733 510814113
209282397 715327115
374457269 415179683
239093779 651685642
501360569 212264602
879533442 677766434
469746345 118685535
252707514 368049433
755648820 388696160
407067911 557223934
240335908 373093100
222826175 142720776
158986879 198032537
320953582 440905668
52164041 878076940
298284179 541343762
89238271 31296162
834592091 348608762
350466345 40545281
739277427 770323313
300342086 352842190
472746321 128718377
879698143 122384547
851978986 490241386
564817971 151008643
379923724 349185685
798080409 120210834
651578870 411041796
43765467 330780269
680940392 732908653
436001148 610852202
349739056 390010620
335977657 566899235
754922005 441067977
158393859 511549854
774278373 332626369
174968590 299963057
378343642 484494660
355584943 331366581
628821670 344259123
202829411 831985568
37750594 831149962
401644015 603346782
743786828 135628970
384240538 825050800
395804980 475162993
148884068 812299180
502857526 115765613
517088509 119221933
201707201 443084842
58435357 791692712
737158617 518641554
703018967 888361429
29824324 576099162
894026922 80011369
297760375 404585520
354788096 90245919
779428182 792547928
517241243 853258853
90175383 489859598
356939158 185664857
873212129 776995993
303095401 867788797
10644061 120619046
651711744 86805327
349420072 191249335
854688991 719638294
745359882 7081591
601045225 452879811
747781995 420040567
4884537 828744356
347999928 65791358
153163844 128380530
532177575 79968643
235836550 509624040
10636690 361367099
737109785 203029186
625602489 373940861
729836174 496422309
451718197 714939794
69011161 580094363
563648468 16363103
403181551 567906160
431060318 19010748
96600301 411878838
700913427 369165899
734679896 493404221
749889695 336368100
264718514 695028413
437844112 811208444
512368078 463479268
303242725 420695008
61649577 536204827
448475892 268092660
432132289 446925380
207338381 342337926
534515770 407958597
695800839 679358627
679799597 437762907
20282435 871669886
215984757 638231535
628544993 597263813
2601378 715548178
483849254 699108451
869664776 153428382
452087726 335979695
158191041 996213
529478769 396592573
97227686 249996339
609440442 278980262
608729287 653756720
371827165 5180526
779320921 697690907
769098909 614358260
543317987 126981826
724951337 822682867
856722547 459698173
823510641 283967845
75618782 218218420
660786650 78507817
413676287 92421727
351928950 332507030
290799532 187863974
389813599 111072910
33365053 718775473
373517282 489107780
215250275 27926583
875938306 286327914
108574200 753044740
33818206 596455923
543595869 650646258
381579271 517069925
458170882 150611702
514448833 572589670
291378688 864705026
272598782 654157218
845750666 266452943
498958796 350111101
606307961 188466162
775870595 189689315
660387235 668085015
19678190 149250884
824380488 783152204
75598322 405488702
691917453 753669981
479543311 695996318
187419448 868208871
467769166 316769455
442975736 626752150
19538585 614252371
1265361 806495366
559005357 826787118
43865074 740683108
200155203 347355007
729213743 754978662
34179870 885600301
814155246 28529358
734692682 635734519
244086569 38679622
422568628 663699698
809347238 24456113
718012281 620449419
422854341 511681620
766419674 317932775
166564457 493207029
385716568 882397859
566487436 399195726
165559544 673702965
733456177 783159277
646719640 586991810
2336515 535125181
124114950 217263586
76459562 816794072
696938817 702247367
853756496 663656200
589360536 717552114
838973285 402061353
407553035 384580630
53483412 470529402
472013214 573507222
668109179 549421718
348067151 518965288
193687635 207457640
146239930 456860760
834986681 95206924
124467838 99734102
733578925 658596131
849031690 803256060
265356922 856507881
199637512 18471703
727900333 247638973
61878549 506164606
712100219 234997933
670363380 194763913
377160620 352069411
534092218 110860527
12710785 685573619
588367929 683586633
707942232 246010993
564621579 445680489
707596690 374076999
267817257 896017936
87856317 536203611
53576239 767741683
283829675 117387671
363523333 518230956
827433650 306337109
4735865 587856325
332303187 144467837
17125442 805635495
63375666 258278955
151488472 874967787
549193188 721136754
714750541 707212566
280035731 819420023
847638012 777947744
860612691 856268415
502513880 98005921
820562231 765418166
226028146 366137852
329295651 710323418
75797476 556626417
759358256 745093568
141172440 209409980
269858634 832732177
84250512 839344080
711866434 526612599
274698858 497315420
96940640 517829800
250692246 300702377
652228478 882361540
714303225 9380469
452042374 263477415
432473662 644989343
403493102 665773863
518030276 507120721
300901295 539960229
83569414 807219976
618888480 884977317
341965101 338150897
587293128 624965890
461606709 810607919
200396531 341280896
306494310 73505852
338474026 358694628
6553369 56354080
25739799 601760846
829329718 834552341
432381613 291691728
77176924 507678457
662016904 66061196
794558396 410064544
381203286 56395857
117705646 814765565
896007877 347444111
667152384 468282841
66333963 394237177
438389340 343516731
769301751 76251600
810999525 114483117
838682107 383840135
688265094 788750738
872350790 11444615
661369733 460150718
411194001 842749720
132091043 179650476
561009920 704195289
739342972 128314559
217021550 599065260
93642013 637587961
234907241 466376163
509148116 317592021
339800870 749117813
749280190 500368870
40358204 585084816
251689302 215263117
476852183 794535063
737274229 619349761
377792826 304162808
516795647 87146675
710036627 783864887
363558999 84743625
50471318 838474272
813325203 418476762
378065677 174999561
410423652 748054655
816815640 618467037
571555913 392103727
875211757 176595182
453224416 402660164
446941959 553831775
805557156 182143027
607940837 38637402
398085296 66835335
284560072 330025273
77145141 308895420
37097467 99236535
509353788 154889849
149004928 657165664
280254617 838723939
206160717 12579194
483079722 867704382
408597447 513846784
155597219 691573381
611393215 594959072
69874309 18122633
485539101 709755380
689961723 648307124
713199833 647820663
755214468 385444406
472806402 330737544
376079345 884049322
225723683 602167198
607944408 372632477
729967499 723439235
112863079 751772789
723915044 445769180
722679878 273223592
546820358 566188236
57268953 606600550
191416954 845486204
362155647 660192160
503497172 474655451
119899366 173006406
644108208 548215388
262872341 721386013
67220769 674898836
743302824 849527265
306791948 870704619
734547638 377806002
680442894 758227093
3354466 61001219
250310187 654618764
281986045 37771576
412750451 799276714
524844878 556401284
375547955 556755726
632278768 133031206
300470352 419430038
384298453 599602045
161993653 602284913
479494373 523179888
741166727 388688922
733173763 445153326
531794355 48601348
522650769 202292882
482183992 412930645
3812346 899677709
686570247 735803913
554662583 339884978
219001004 399029480
685490991 275523442
343652690 662127978
61493137 708452747
213057984 312689625
424439352 487181749
347192688 495315052
407390886 856400385
470614648 363434415
771805979 8257342
828047744 269916347
135826581 596811447
201640577 801419882
781404466 641162999
275040885 760784116
629664079 862605474
236095373 178191526
823115044 874849874
652614514 295592185
566512192 727514141
797689836 580675602
548404104 600573593
800566029 35930095
118460263 356924224
191368857 570045609
697580689 215299866
707628026 66487557
167798197 448789785
158709307 644669075
5930077 172281939
857736231 449712157
672911355 264319284
302988838 272572508
490251299 867900366
787759564 258061677
875682173 736724761
505516103 138855164
670549581 536428175
633878655 775021161
577392875 839109682
190150805 136403860
348337953 506386641
431146018 842142048
374616620 405948345
337471763 473565230
177490295 361333137
611824313 256643708
546529488 706065172
117470944 734629567
75668549 339828282
817684843 160908421
65405606 830229152
575118636 59066581
168195295 496297507
382051146 765857354
64392323 775368971
596846489 24401515
37856714 141979373
166989173 842649868
538403700 610569250
503332661 252503060
761377235 436439991
624070022 792915326
38447351 548163329
605992493 606681815
108183277 72699095
68624827 700435530
633114895 502288303
721964182 839994724
76282843 798387899
167641526 827445216
757225205 875530838
626645404 733558378
25069424 408182560
33737605 7793162
701642263 141349985
625649267 281539075
671874363 404459083
623316228 265114205
336540697 62291841
574050376 126237218
49972799 623106338
785861418 691324906
817960530 245077662
434810958 164348551
508782152 214813759
661137380 189016729
390507526 476830031
850471497 887502486
499425130 271865905
753331303 400272362
705884607 455200497
88729332 416572171
566050248 466415931
282738080 750577572
603186479 1936071
629040371 68302779
742012063 291574017
677250318 708492931
684647041 43328581
503959333 88639575
408349229 837843483
771616213 285162270
894753121 709128660
237433161 375591296
32068201 322259855
391124293 587708643
605897267 302114610
680498601 898717516
553479967 423649202
399833021 30783768
109267608 18731271
801460560 181842144
83683569 682638414
396987589 458088158
511549295 701268362
460513599 829498649
850226531 475468568
822059092 62876803
672645370 147426918
324184751 336084092
799713416 689971904
525262065 377052042
656716006 773451220
336655319 658150843
634324610 233230514
559941345 644534806
843866434 423975934
709616345 143839850
133817749 88079363
846278283 827705494
193944811 179574780
251418936 94779939
354200279 402746704
86559857 799952904
492474042 793374310
163078049 599565608
215851881 528748569
658607606 571847395
390171963 97765866
295988085 665039968
403115316 158055714
183413902 555087497
547874582 179284152
128433332 583182799
474342025 479346867
149070549 474368911
675545859 249415642
533977314 53569702
448239829 69903734
618449472 147489617
557576768 506407266
784091999 571224079
75758287 636144517
499640987 895090093
46085070 545295217
444172295 486872403
644915103 165582540
307795586 278977854
225827003 3439159
16424254 397745625
188538443 510217136
457740957 761780358
158175334 481325579
899959234 272419511
487695042 533789048
630317927 134694255
781232935 345621019
761991137 332342588
719381653 177275034
488255662 253050193
620786108 709863734
807506164 624934371
657679271 636677279
733619521 326275757
349557250 712026273
248279211 165404787
373691690 404033360
769815056 532657463
349610421 694337436
455046331 18169347
346701838 899026179
67714428 55841622
462059621 127558344
261232219 6094605
122667082 599608409
816991897 883739276
458763912 483393379
599840670 268424224
610032490 241743427
10804454 643727481
17355918 172016833
860653387 782575129
810080344 181734899
64232646 79476261
501510190 413222605
378966439 10175763
859725791 30130659
167641530 205288862
169706073 795678699
880461529 660843678
148147271 631010565
330366418 522038537
119311752 46862691
885497950 673335762
865917641 895128032
356012251 225320223
320175305 142676278
446482705 545289071
194687887 222838344
886311895 69590738
875180979 796821259
80209310 377714177
352549458 243269943
658873022 421736708
670383775 158321616
618704876 98286892
577206108 350308489
850185400 371941817
79233632 44972956
239555587 888768266
43921831 574873355
555019269 827575032
891883099 153460630
852296761 742415639
318037757 596037535
608662212 355514072
788391435 705145109
209115112 570795278
280620159 310005635
162322656 174790140
491521874 526511371
396116072 187416208
255869335 70057882
272006996 846614489
517452778 437839098
484521355 389047416
195761844 710044432
405482118 102861125
130666767 735832925
640788232 281479001
730094193 460697179
113456122 865278956
56253754 696806665
625025568 209856041
74221949 289984751
65741136 266496306
333828120 560996452
842263228 418886574
295854703 218350692
105733046 703380098
644348018 782601586
289488208 136563856
771009566 493163364
571434959 625382345
859950241 304714564
119604564 493504369
493067251 391805237
477161755 469706913
494356170 72849165
188366647 677989593
301816437 512654400
861883285 382303861
56157303 737068902
445583741 149113351
859639062 768997954
411487857 351956841
363838119 347858486
669702668 744038456
645114122 184956814
577846262 617128408
225118329 99449202
403148591 609720947
730077955 468299997
533856855 101190806
254738403 432297115
847095780 695833510
748194188 340308037
123314179 449076115
695060892 155790960
673509100 792213358
143220008 477779516
726043746 769064009
212775860 190827173
657237802 370044979
2108251 310326051
477184825 515925363
163607885 740785378
116306875 473748030
611231007 145574219
369838857 815804427
253674487 889077228
880520114 193849547
238427787 562635265
47006422 167551223
566289245 625120673
208834044 332360918
409607306 700502610
839528481 161713114
742827795 38677032
892109458 455678438
304366949 494123744
360863753 102879671
181375621 860272711
746941319 19404287
8785443 244331682
500737992 545841429
768714454 753960937
584251557 603877783
628814577 601349450
519718195 693068448
570127236 103435931
196663722 284166543
53771244 599979598
605674622 553011
594031954 391203336
338418475 374369894
186250712 19005474
49961116 256312304
27090449 323217678
296380143 858878964
270505473 523818195
564276854 151691813
307884594 893032647
724467163 288335462
722659338 637198405
58915078 553069188
293245502 322098981
587884802 806647181
341616443 200002227
884185435 218263701
636538263 808857424
836632588 138335978
242927736 825075739
580119824 529646078
409191454 162480135
600224425 237555658
563998340 107752653
784443992 244331779
445088575 131997475
676181041 852934631
266501878 697039428
397626172 751802810
602562832 390172085
208680787 386748276
420542101 480761497
813869694 437383262
684414918 253693988
430422818 155143286
373050427 399232773
860374047 492693519
176716045 400748353
459218075 643650953
627574140 511075049
768985843 116797764
200970517 561333198
876394947 844154761
208799499 644569790
826574581 560444562
303913058 410510576
596717393 569784287
206105526 231170928
174467694 581618059
297864628 176317211
514416753 663299371
182873889 250958223
508528631 894202112
320663223 361693262
125467599 725891058
397494052 220698660
162593874 48024202
834774230 1539614
560646190 560295444
140428720 626097424
535122808 407114207
861750754 733661552
24487317 374173258
431145057 575060804
487188605 451313880
102967897 893089653
389434805 53378029
139095675 765291947
549439244 93783853
765028298 693488177
841742364 374233818
592952336 871847340
22323174 141259211
749936804 230292874
247592705 219050751
23995363 637858877
597747238 335998566
658496942 783100165
449874453 358306188
291837880 870586960
730331484 48667504
318267854 554075214
485774048 563494671
848989663 287025984
768389629 122327101
15352037 637137175
828078350 242171429
696436318 738263560
303278694 522457620
9146922 742535984
655983909 82103179
701787983 591368583
478441894 863688039
48723691 797083974
369880584 294730451
698424445 244762267