1000 6 1000000000 1000000000
27042640 597060673
867313155 865682571
669707162 697986438
322196156 746866639
716795108 226236797
944995506 612132978
615514445 508196681
63769471 51554189
301011813 392520419
408423762 2034485
324636207 606248452
64286269 62051561
870816613 227436319
175619687 30305051
702211433 337600068
587192185 873926919
873267409 425449571
890930193 597675259
331382330 380154402
30380677 436174605
924100546 372336456
576376916 556665823
507409908 711804551
531720927 997894641
727104603 983559230
450281215 917832917
60807245 691746158
306695783 743148387
66706787 32094197
857531061 449099946
706093203 717134781
764566941 720344114
575706784 398482882
967770328 999627154
903745960 773111982
302023698 599264066
996694410 985446382
140955059 884553328
255162244 206919135
557060621 621852388
953539028 5223296
634135358 578076602
263904764 225763244
820868562 352141128
828440211 969861938
628985624 779724246
891246855 943294415
251812499 476199319
200380732 993017891
396519857 642294091
709999935 280999901
513108759 954747956
442424502 946378186
783592913 579833066
617835935 668514942
464603233 289091519
498153645 604653812
105202571 610151149
9793425 280796013
579091250 525274463
561640458 160152483
957271364 628751827
29382712 500297281
824908857 891878973
370701581 391263951
426501226 359692984
18681764 398736512
859064292 643638015
89783241 328760451
667057984 983774942
570041357 295731877
508967528 766045593
306678022 479635184
838256885 605585208
645494436 870536496
685854784 685403912
496375156 540272034
953084331 788312258
74691193 878292824
69294030 24254934
415697894 59060068
274305110 358873553
368157987 253674301
129696488 743901670
283983103 693136635
513068434 565785733
189904749 272477038
314548282 723732343
277909748 544763233
234340200 458337817
21882090 485669572
514115383 941318348
822684551 559908589
554152902 48010974
522515911 340604064
243664098 937764792
397144599 124933744
425578741 411721308
832523843 760537628
331778400 179550179
86938311 806844217
553495482 401344883
613444432 466307783
288144455 261099617
917797682 648394662
252628728 35117013
917786543 492951329
939211780 631593754
80016327 551401712
369018300 963880683
84433018 179251270
366429509 675023450
515599361 59941064
721970492 628791772
728909169 889641720
659295315 524258004
981152772 289675104
391722046 856971538
555353285 865596030
504243617 947902572
622431454 840377768
577455708 677729677
155502853 897568692
170438716 12978234
300566664 275793561
680971358 84364045
179736797 958756897
24827621 996965940
395345213 158288028
733230704 315175964
266190562 548392916
311346359 199513455
577514270 685317272
274157633 982222842
896187460 254973815
562962619 887112135
89937218 690564408
320490354 37462645
907706258 968780290
680276666 593308273
406527555 144661161
112145544 133327575
743331513 248231766
406691508 392521499
748239429 318733147
914468766 408397124
635109784 576070163
657702358 567300571
826994901 458577677
271909484 108723477
835961358 629060099
920644517 296854685
361279653 158103205
758073061 741495056
695773713 228838572
731277836 608956248
361240375 617729929
447766219 650106816
850029505 341742494
54875004 857818888
916468658 626771278
48566447 998338692
39798429 351887756
252019952 417312256
236257768 418386395
872609964 156226452
114148846 844468826
193111748 111883008
989970217 511514018
603706867 391341961
579511671 305193179
608392 146809185
574255685 276268457
120556164 586582755
655255535 466960176
844334002 944922969
794210293 237598708
473747472 429203541
170708818 516339335
192711953 348694659
587169911 66582032
482400207 145705145
796090724 10098229
931575550 104578494
840681648 799543649
315705147 393329170
38290118 145975563
802246945 410778770
60299309 72264525
855297339 361289485
152157380 982090319
681864008 580102522
628200103 59859498
596303360 483504447
618951168 305823131
331473962 546322819
660221510 372478367
338070009 419476596
125808458 115701382
371201642 25484582
16768715 372802813
939995578 121099362
43582851 98764853
406839297 632842609
852144637 253382385
973548909 870553126
245122678 61084024
428493932 151629319
197206107 740173064
188475497 148085825
732036997 548456
829467224 451607538
461851312 473212255
329353966 68356046
945224137 398738015
652332141 263371460
416695218 956184342
988080337 910149431
822914020 352634980
959209417 128616738
167391199 463701286
858521505 956661988
639702029 367130410
544536142 367108449
870408702 448443025
971493465 462176706
411028780 985723447
561157743 827833523
455678329 799872781
231383874 65842726
179786705 949507565
14363741 524832010
419367247 772062656
850152563 384399100
815210906 243483042
493526684 997459382
829149470 520235244
80107743 833067987
48938335 214430306
957292762 380339887
44687045 963947278
983769631 947474962
349095860 926024067
865811642 720028772
297639772 129411654
847297362 609336904
890504419 54563484
462282134 33409007
198372678 214274472
243369053 614790763
317562953 922638922
546129369 967105966
440631947 365234076
680068993 966619312
216102396 718251178
651418222 687711319
460811667 562209349
234249968 120262790
211476603 553344341
146646776 809365201
575035243 62334861
561002795 168388171
392383586 778408794
405852684 748253562
165126924 572880764
195279225 609920597
323387052 888756161
866004373 882835373
813650447 694265665
117378398 916824340
253834759 433263309
481938053 294122210
898543365 202650969
140921139 585553434
256846810 567827853
817640589 662090537
49477174 426175565
800100410 739974981
939273518 283472900
771467351 102314829
40924942 309709984
62410321 638700913
51999077 882984075
722923215 341167456
151019688 760079494
373720136 632146805
799693811 980157232
709923938 648439130
750638320 517025921
254473825 213269170
900094374 152180493
97994232 372991448
903747516 104748263
908959709 810815449
475117764 388369634
86647870 760060937
57899482 384682517
84008859 885053756
669591666 647421123
313234266 968091793
482867092 852251417
719144943 703332208
488110129 160542414
760825012 848482327
975759476 98635122
767122310 896450528
716500186 599264445
154252919 103387930
492560681 793184173
931953103 526709384
951611572 864436577
37205163 894731204
788885588 132916397
970938342 934635764
701618254 46849530
763311235 841827705
856848853 952609686
637881882 73765492
238747067 60127184
705455411 615543545
930294166 592322965
306580306 391496779
387325297 552973439
90082540 13658938
97232727 178747900
806845806 568911585
712265619 970555604
997055023 485119572
106191355 192614273
29733213 593594269
636583357 53751150
230657909 560115509
782272255 66442227
414306351 706859945
861267609 640179916
963638066 538435101
579077992 85254905
515193033 740437654
86804320 362389238
283702521 90299277
184256799 47435320
468341974 237536379
442875971 726254697
30690039 131889312
769274920 983731613
321809054 539354650
221239106 96604592
602669134 452039028
428124230 729485161
879064361 710477382
476507467 317271464
730504759 87070203
585024948 298476296
914225554 775236331
810545097 49219387
572974941 367507733
667784822 816352745
361787100 241993416
188400315 423090999
868307757 893418962
141327730 237426181
357829050 303438936
947188026 271463585
293048057 434379355
75006178 190692587
815353050 418379547
254054416 31298835
625452416 895574524
777663800 79252479
553307351 204123655
145334600 388516203
788149884 43306457
676015437 991877314
867026655 698454704
936240419 874315118
353595121 641179538
534764027 76288733
827226688 86315662
228892077 916816598
635879607 12499859
320975028 770787598
525357447 928710788
966233899 301790131
63755661 814929028
500580712 694190123
945033154 779963625
980351090 602677024
132267060 990191600
321488190 53598650
132420985 834352908
265930863 902816692
864169132 434642968
685616613 145354993
862884714 904280969
773087927 51727709
377360234 925762446
541290552 896594566
56843495 599511969
858500871 772490723
850835606 235144036
337768122 423139811
784720026 50650117
659782532 168725699
909213656 160315202
975283973 264041752
819016445 899910882
565233999 567351187
204673783 415721795
856838847 293898861
340970337 568370965
639608494 177258724
765183897 937475070
102068936 311152663
589907315 1265636
336237894 744230688
499184913 176964551
718879869 953879874
955320688 191534864
76851244 238875333
99438460 385198320
545131713 904171153
254872802 786702469
312641182 627047957
472533222 722740126
70512895 308006876
715926687 995305317
493610727 941172547
735584297 269370492
827842583 959610632
483880726 826472432
967959477 196073487
767949080 653106830
903392574 77581486
317493102 419886685
209244809 174372284
283322209 69975418
257421313 434676319
499546868 853244534
926280232 744199552
396361187 923935827
968964234 193933929
890620516 350462114
549209636 165917800
698033364 180616285
223026191 50902821
484393010 256258771
304922685 794745894
925163999 799026209
843673261 185054996
784826301 491381964
595953235 692621403
412204210 282170000
443122837 83038296
818732400 457620260
679229162 925332273
647026673 470493970
804782405 512240224
621646156 522883966
704518577 739894687
417595997 191356104
947289053 795206450
590588932 284015742
17143971 392349188
232649750 273216171
426953237 63777520
184222467 778626375
255512363 127592531
927065197 735001494
827611954 356377613
69056240 697133688
181236143 700557978
621375856 669111528
59748015 262709498
959785723 432315359
368095787 872002120
494941043 450782187
44833636 317180146
82503006 496069282
845822276 512351574
153560650 427038671
596208217 495701776
401435264 431707868
545653521 303508242
724866445 165223389
824401628 980083432
493030701 854995506
926845726 541207140
198610271 674093330
192665983 820048474
225625574 668271257
476797166 209466086
944008541 749739116
427580383 244983706
208590013 809381594
872168383 323861868
782591552 744085706
849944706 155846173
311764415 120780887
464359436 521812836
472545127 605492615
332780051 762223949
424162223 54040096
409931318 15743155
969321228 998979251
16105052 420367580
20329007 961136960
205035308 318949262
367333205 677858832
112258786 475079135
33411770 666283806
602640501 604184432
998840399 49072141
620892620 311666150
995906534 860681858
892326392 161422589
768665929 51270186
539354841 883738043
402216255 617473813
304633894 183957892
437180498 47702661
202043533 698442912
771565220 985299201
865444786 30941889
229024160 425226890
711404695 612812913
945480143 186239894
370586116 189655351
841327015 986259776
33604167 823206760
740962208 417575913
276832638 392257237
652728911 22253076
223503473 114408177
198638401 636654541
212706975 729448511
693287224 165280123
416421310 775759443
314594520 994308504
500953690 147433889
725400925 728579967
678263887 588779523
325256323 774641842
554290085 414759868
607168159 267412675
540958969 944036515
326599323 797634868
257013044 502052729
962133618 518337358
66729977 454614547
252131812 245902474
477267843 330375509
63171103 708032340
582598093 399335492
8509768 788072787
668261399 12868236
753285661 462034630
805601876 950966227
873306333 688636063
111428987 39531062
172408821 189283730
939575447 422962466
96372644 317746455
730540012 336455218
36799440 870112589
465927870 702870487
14390829 104342159
562955018 768502030
226451805 633336353
773717916 631328428
887634092 512082213
912722626 448375571
475951642 372347336
478419981 332679091
98612806 59981064
929931710 165229784
35509772 920632491
264128442 406526545
314199649 758254795
861710632 352396303
271442223 983887446
350549350 449139115
705990876 584775787
502491972 276514428
309154654 108908989
233979894 589421644
348074841 788665296
434637693 549290077
986728001 458705698
180577639 596250259
467042991 874936356
495246305 638305835
583491362 58774235
60573090 642283154
305992608 97732135
530940094 784749527
15507134 481246606
503680733 993931232
982434603 169587739
909657105 623624060
448682541 641621553
28815222 737992759
869433786 680276255
446949068 845946592
570260717 497050994
755320967 152526481
709973035 411182632
374013075 442640401
80733575 955660285
538274954 482858000
886446910 329781816
725661340 426268120
320757769 233138884
887024144 693184480
10354278 553680367
58659964 439450357
331444109 225845783
823970424 230063090
271673581 984813614
724344147 327758986
61429844 208931924
919717583 956138885
793068487 631773171
14143926 580069731
880432315 313489590
101046402 190788184
570985648 861872508
372630979 520803990
36521516 788496619
469785458 228923734
453870424 954441046
529923710 276185122
203138168 11331042
293496864 800028356
7140462 362970061
843764289 830579768
801923003 574889621
532997665 676554007
45221075 36116511
361307959 939190070
358711968 549851540
757089227 44143539
72860442 996203690
111641438 269807972
752591163 197386306
61468484 305702755
871106723 128740456
922273845 909038089
851694374 990612763
656646488 707170653
987743206 797613545
616320096 287340970
694465119 792373914
118801265 544906062
947641714 467990362
791823317 652443844
71394192 432400042
907843530 742929218
585408527 992602374
510639378 452111318
89782766 728690482
648575409 272827094
20861152 596962128
131533181 374963730
62870154 205952159
843673832 229951652
447288338 885199635
210612948 341976253
854704403 378190834
141331877 376610472
83109789 380586773
861955283 441487086
633422970 483058840
15742846 616269533
349466078 213451087
222250346 656988445
838149752 982320862
735213487 172358237
579433370 574063236
695523054 249669312
48503871 975807152
790544273 211087073
338971579 459215122
467462788 826624284
360754593 915481373
535416249 269758639
745378653 58588551
373620623 450838121
820945908 651758090
650875516 130373040
5937791 850647093
581709687 630500924
442853289 895962720
187607978 712899010
767608375 107666632
705470806 662904199
347424259 640834584
362548528 153402395
768025557 45652869
906042151 602113354
600393435 945231498
990470449 479293973
708737412 297276919
256498179 69807497
396051784 759702181
416552324 197278880
233522715 734592882
146199700 235122731
337688889 146350530
82521336 669160226
387796382 923184142
783823497 552030419
699016090 329423659
406823410 366469817
959523760 650517919
921416452 261727244
715917425 502313408
488372180 966969167
657728932 38670443
766545720 242709167
154164346 212168808
253780362 784384363
171596330 725217891
675593045 522646734
626269275 445074842
59578651 207308589
771328974 475971109
628467879 653874459
389442101 242760642
433778826 664026472
261340744 379364849
673490515 198252347
646652791 796058043
595239339 127084721
777024109 464695185
500923038 767352918
694092360 480839289
624643166 324753812
128248877 185031485
54602408 420372442
610863490 228920426
677499334 636095838
135911493 710512177
623356615 734860330
570521163 959424801
427431034 112173892
682268581 388866369
167361359 534306036
269122731 535358846
7114839 188008717
1452391 47386135
729321288 81818061
410735913 855660146
74587090 428208645
73479939 34207182
656336399 530574998
668892261 244735650
274235065 83769156
853231679 26638339
15540755 559423867
51262713 259515616
284642140 328358716
465289572 670413176
25077230 415946284
134870901 398306770
849557669 789477847
426188536 56119859
541698588 39508349
210448956 966235922
673613929 393198714
417549273 887698136
647261719 543255422
977079604 528833120
831013972 600762812
126724569 952775220
158608446 96708293
62057420 968311211
383265851 831134658
196005199 165745066
448802882 169562532
305941148 146356542
231140211 235679687
377095641 21878432
312421865 172488170
449058108 572753255
836379805 19454897
574483885 774383869
733571564 762172105
583260695 280921559
340291078 188171070
579493634 26222630
322529916 465541018
491524111 319458066
779199481 940705717
946221325 714613274
875391116 822047809
788013498 883024168
550851799 924116220
641224402 658544590
980814947 943099974
592537702 126436196
21200287 221422930
810741364 938248236
848960282 244153558
325845971 132568946
177604988 252002328
252388174 380465342
569908684 117691703
96012950 337691951
532342197 730250641
952689660 334474089
822360560 484252102
61196394 957115696
59408543 450248617
357468635 741228156
648112915 483862959
100341084 599532788
807961764 942478499
879029463 221588670
283804287 51692396
100941499 310196901
977340826 983214531
512236960 539515141
198639037 759411560
181764855 741090134
661459526 528028639
331005458 332213701
425279699 97716972
208475179 10487225
174469382 887923256
67377039 441623702
990822690 325652992
31388161 84832884
854939087 869923579
937281925 530256645
755749209 118820594
977125582 192606317
512399430 163531815
370238128 919284115
250969746 511253914
259727172 862854821
227954103 470266344
324661471 747904306
166557163 44691425
141816833 670336163
49758409 745579003
426121218 620399464
990489887 614163804
872709204 664717220
234519429 450764017
252790566 880929417
921703310 230265971
657881627 763034245
77772787 897042404
710505319 535989190
588974042 806176006
173025607 92627861
48542675 604826027
589258159 630591464
295638258 121429034
425930963 386023741
898093427 98235733
73619952 576617508
479871908 314649413
90744894 49737738
647832423 708268371
191493604 530412998
831237137 613889942
791687248 455742033
878025721 767577767
928770073 421587929
36425832 525922052
197092388 337336681
536839353 45655060
11870146 646112693
440607750 374766302
199687035 910428766
568320771 395264107
165819702 754185151
5517283 904947807
905302615 486729157
18286534 359308003
992420238 686976381
821389432 646406508
629759635 897134704
918683841 921873016
481240473 246245566
87082172 875687546
612450700 1571498
173845115 678016625
565568917 516947332
911198897 301982288
695187862 925832639
876156366 443936599
66131393 905337621
506751272 56785879
786169017 436451798
964011687 732478411
827291485 303717023
352879292 172382501
531457158 41411599
901527721 578508555
843616033 647833301
679371986 497064823
250155351 987493752
107343554 914501684
699101782 794097640
193208735 913939469
854499341 314335609
188933046 68759770
697023418 211151975
311067710 805365604
172378801 520765652
649208148 987001820
645277249 453957573
287724572 936519074
817337236 200748252
623793342 462632982
380258848 768457842
537491042 319269859
509889698 214275818
380202883 1822186
761727076 461001148
134319606 161505868
544036438 572804282
764254113 946587791
51770918 859092264
945927098 707231475
914139773 239335705
514401642 132411019
302909658 788673848
108266549 629214456
469870444 470009534
381278784 666467238
623520979 498022190
578903165 648650331
350718825 157071938
287584189 378385530
963205616 869474268
321326947 225258411
866605424 872350387
342553160 117517225
366361288 577585955
266960955 486419180
937414146 955868511
385604737 349014448
479152644 575954064
577600828 45407935
181810871 45994032
875357165 435590009
463228099 924817688
888247711 996474925
754498958 905520429
363055929 582650282
368948407 507687140
148773321 168467560
71102365 262340780
493560126 671563042
451555951 627631588
402582407 668885540
631156085 653880012
462384472 109142538
875627770 822489315
341414498 856705106
252222738 941209684
123895829 381004376
746319387 493147307
757653292 145003889
161943149 241777130
493614688 212263136
430320591 100169741
78988696 453363170
559867852 518938704
216673618 111115908
685108376 751437699
15003039 705219683
457205505 961994613
684836226 599175296
201996315 977095297
971229545 496784369
830163258 592180669
876081783 616985713
786643668 367980186
293457738 951840841
381343191 238080091
663612177 433977123
550101660 539849233
593536987 820681617
493697993 138176304
295239472 889180697
164138345 578092981
377655986 81635483
282838123 948775500
979463855 942351147
446497598 716265292
949052504 660084666
6021745 862285536
31153395 324710842
284911808 506637428
89334326 392565828
469947799 873845528