1000 4 1000000000 1000000000
754488399 48062307
812997425 783083763
705396092 367084403
79679490 359739312
290740341 545580264
999274938 98020056
744811784 129680459
475163233 210118500
233748427 917582314
829233881 165031907
945713380 664299447
256437727 109749475
210311566 231048559
794901143 967471112
936903195 492577662
249723264 668513143
461951768 823907206
787480328 235322408
174600829 254728770
604164522 393661903
688908554 839655487
29951322 147430969
507808746 583339470
178608469 292749145
762738 471984415
176945297 193997745
532695542 90931821
660492296 664734912
940272826 698856866
526261604 432161227
472599660 932870608
463258608 185621471
282358867 938808751
998307055 466117063
571232919 263639439
301254173 821730368
326770100 371813366
782902194 488109750
18889754 917204534
224857592 936740370
700824373 632869314
327313194 627763448
244944640 811130570
813620310 197863458
267708809 208542739
645032075 674601767
4646742 899308129
171494467 532043906
596182791 145014852
761742029 962239185
64197372 979597753
345760107 434823269
589125906 610756133
483068665 832609596
445322414 300390790
800053406 392521891
291225013 447768834
568132073 634730254
129028457 704032626
611936540 42645415
600196208 92409738
823578668 654882232
837957888 995249159
136738962 967932515
591288991 150125482
594685820 723721315
17734818 329162697
981938881 696217966
431421516 468003001
623296359 500716040
419920228 676178762
270142804 561292892
407147351 764858002
266754096 597442435
752671329 839970643
333760046 569201928
419755777 750654694
627675561 768647819
709926645 79983771
180758233 309924779
411159158 195370277
231307229 373628799
315914927 121327378
298424810 256147517
575822531 591988049
505381567 190351481
929012559 222616178
620848684 498836730
886842102 899123266
466799284 450874657
437450673 16270125
775875171 83587495
418380890 345856230
700129253 659019585
149099750 35975607
48576488 632223915
182021342 434667363
924831613 349862770
628536060 202456781
850819074 860888799
711196300 87939385
191273632 455510989
266820856 51401018
870298134 938866875
425711250 349311955
20021976 352750579
682899771 156327784
487448777 371643724
887472351 173244534
604559093 985545866
150256477 24385563
494932296 237210449
418886333 614463448
534485469 678994377
118431179 724506758
631935085 156381904
196999856 163539536
364433595 391229335
556241119 645045825
954306846 335904117
859297549 65662991
753333533 185892710
282016805 71971173
601603726 387384345
861179469 206752388
829334040 650184945
665894237 728876718
93391143 395585038
310490291 554355160
897597263 832130264
90180006 26524275
889700092 886380764
771074104 200367107
601349091 25579288
336032629 532323262
584319799 927684999
575180278 768418852
170981297 392603507
628180137 89099543
764648621 585911468
513647362 320847444
451665686 980318962
414120420 87700519
268114227 356042545
383143614 928491633
986854510 162809296
80227431 629428901
292713049 985135044
761344268 751119677
553205485 918701154
714412908 701992913
578008171 317101531
553777243 817118790
191883788 641077738
713469849 36605968
662963792 400863094
310170527 688145744
961857517 368799086
502950490 14064206
48283506 124477356
43486076 847758349
352717103 426930537
888408167 844075558
943458716 64603273
301426574 962617948
537713266 468863569
589058949 254809349
162522526 73672121
538053025 130673289
422122167 823846076
318395518 98580716
647543527 366391874
412252653 852806502
747710440 871021928
371012332 604779500
45183000 512719957
500148194 742742221
350986894 884712485
50877666 492598512
739178036 796197225
50141190 924591151
41091695 425555536
433514680 793811424
750402226 854543785
832133486 658219774
462587936 888249957
893030253 29795863
956194567 383675120
836572686 979708127
739084540 259037208
544656850 337192536
151936338 956804753
564318863 47477934
655533525 484683543
254449268 243036616
580394731 687057563
914931417 444243690
630208690 109609718
150004689 52892843
688141116 545025589
228826522 900759586
751786895 998947685
629550981 234471163
33390837 631956061
867857145 779405494
712617106 32686669
711474806 754395034
465900556 604769143
829219227 183975531
556176506 629703750
192337615 57239809
927098173 750860715
279189132 746603045
774876976 840356981
488654191 263653957
477409437 918653343
566049058 983576182
443799348 532451782
226184974 208321173
447784430 624116361
225658681 608868477
756596893 887774245
610219926 138716743
933716147 173983839
728482810 347529252
541723548 25017761
361308307 252056854
202582490 573157015
233486468 600648925
80306470 69812184
533115254 760534828
968932008 316785557
412160309 779434608
821396556 403697591
842562637 843883613
907372850 906779868
485040898 248001719
395994644 141267480
237138236 673499116
219013362 78014443
973441888 592807623
668165139 108339075
300233813 673804335
544941929 271240082
310713761 371223664
429712929 723891217
752599262 324229535
29022648 847730626
380201274 582562203
744313444 224643134
746476539 99128996
872322493 904947632
251169413 851945657
877649853 613530185
868703660 593150242
292774751 323014262
869320125 720724792
212025379 561965511
770055624 486016906
406222471 848547459
225123740 496723875
537082842 250659297
120315646 763381723
178774843 605405292
571040493 833410570
632677555 794900212
152046699 529351483
265448388 411164162
587809172 579158804
115613788 467586365
400759874 821481030
246353974 673648390
10331438 466093117
108869055 406925940
375152666 70478775
499229687 443592498
115281962 892573347
410094570 875610503
798316842 234561422
705908680 407524328
645426048 394198783
485594254 424396761
749292113 182341017
780350175 219214934
199728016 395281266
796648752 505415377
504068387 598322640
827150837 588549021
853685133 486057006
676964974 179158263
126115956 541536455
591992850 973427492
790923502 780477199
223195741 563978575
888749524 800523091
749274017 553321494
24943814 875237852
434888186 588070452
425108546 356836683
287204352 402355154
869006492 552779522
145883609 421278348
96262900 594425162
196942603 425302027
672497280 649308000
126105545 687718636
443929510 373692758
649885300 671638061
483715897 443457278
100836891 190078948
751512068 726744935
856009904 100801729
721881959 512036439
334000978 412593547
675652557 724261328
836212753 736069766
645253922 246372450
852625541 512075843
630209892 14637550
412871529 414964778
387608338 126081119
351582603 855021952
105557505 642482037
825401052 20868788
601928329 406668809
310861358 413682043
388318272 16249454
511360258 163524602
298001703 93187814
882045197 495129003
210131787 313737436
758707289 765364711
289730712 944238598
656328076 344736781
698775477 189368804
131088674 906115215
778307032 778932439
513319496 139113571
630937679 378626681
795587658 579880099
989007071 543998297
368051424 763417815
393167330 682705254
141145791 726919005
452214309 439038074
783014552 554117823
246001492 860384236
365910933 16589440
473376919 895004716
92715349 880638596
455998485 154330400
33053944 378432172
571960482 354297942
900159410 37972291
611380998 535474858
947135321 205136408
186057172 610442678
547830706 427211538
969220052 261810104
86892177 484129108
737164347 931135603
440150352 412097664
995567322 16896086
745354954 853790668
228747069 310515525
900062620 557058661
354669821 718559974
474492389 725806948
912550579 974833594
579309953 175844586
479377559 69719514
909122250 166925489
198230395 700269716
310122803 249750846
512081333 60955237
53614482 191391547
904719187 592461787
685464209 810552683
843994361 928402076
154952409 479597392
155851216 724384746
585633047 825656947
700318052 520726251
857006758 308986130
708116613 432536690
330943979 471610079
219808751 635398608
933416279 660009119
265019414 130959657
133366182 436984027
259488876 647170915
530257834 42943875
380364755 218442973
44416994 556794650
718722404 670606912
514727871 580637141
881902256 26327375
652270696 647989943
521601257 573715228
222346292 277745663
357104145 782648434
367956677 889178270
522565660 391176615
622732724 208804963
134458245 252928128
258685325 467649562
507408159 73353231
682794348 565464262
366507534 58743686
35754041 502875293
150287495 51213025
496203425 117483494
274969501 672273205
985149813 448055821
257105122 797497605
569331772 662596177
353620141 738337786
340878892 269916519
876573729 420907267
506348493 467099703
341228941 685030285
844218124 711836917
892533661 342772162
219976303 532042439
74682815 549841089
6496605 856529906
524549704 274623942
709440896 759134836
911538480 570261608
898680342 21870850
758547284 40277470
393436826 736019555
271594346 366166542
127946712 747109268
105223671 267477545
963472450 912293428
988674527 475846221
29599517 256578583
241196330 611860884
731745557 395681897
586669200 598380699
2089563 324152204
26327168 969928910
487740341 462024369
297977013 142117557
343569691 904077065
110387930 87922222
949025468 143236757
627846907 582335679
910327293 242448527
843208613 79932926
994272028 934175267
534718197 690747604
410601384 438473368
484677300 631286323
299232 742333332
844509356 915313346
171705372 585800421
774436368 82168762
769994780 693561369
345907522 60908897
774040749 691581183
765846638 161673764
734245903 302506889
124062259 949712935
32500946 544555595
454767525 873883874
338556086 818230273
81688742 924745590
423928690 583340938
140927869 925300961
783811627 263459345
269437014 900813390
208704273 602234668
648138667 126883031
580701190 800203699
601485594 164184877
175206156 824224767
499325480 404140925
698580575 574957533
767669241 275641656
147799456 469534045
893334857 405193591
442114021 123477559
670052249 241119968
142171880 452907607
862695714 209375899
572812403 748130388
509710219 579978180
326250747 253985536
304993089 307938329
607627733 20061571
728584801 42995923
750598816 322485643
675238356 853573149
673052461 703946311
371627484 510530873
149100673 603553950
2596465 156947002
770711134 954839682
76050040 35829555
978915512 898523378
552057365 546115153
819220998 594651960
817350838 89308770
268086219 812453946
890115352 998637958
377137247 640032545
745887759 806694662
769858672 982210564
333246604 406415421
523087629 23953713
933120026 447226652
384679336 127467358
758951754 939701003
971740236 630043279
613242853 327703855
804003164 221910238
541356923 739451222
138037304 341723058
553790308 213971879
854458011 743042259
936843157 86112787
527166981 797467803
517883443 523518201
76575718 526379131
589900833 268144451
524034028 939007163
391152203 721164671
659214156 223455026
955382100 605015961
383529511 241050950
437961292 974415958
968958563 742941690
340551033 467121888
981688590 719125868
324421639 475843106
563204555 340316624
958807715 678993361
677864583 426369649
999770753 836951647
756289265 213898954
856689028 392386106
459336541 170636350
263056762 611304066
519951144 563704397
826725497 372268448
392306629 610024393
858662508 314236688
742562987 74453555
450960105 651428273
287032679 717946720
242057662 272331395
645996837 695200582
233411535 678363278
399880335 848120271
736268331 257872887
464643464 405432071
374490891 408314093
941368283 275359793
659905247 141842513
328023191 381118826
116357474 268745240
136819104 139818792
149193147 733569998
656588901 604086004
745425780 568274149
595017365 180328280
819295540 565984740
279736111 494199923
276712450 711993806
780315638 506741756
114330620 632478612
915699070 586252612
564438436 536329886
454918153 931702665
180825625 984712570
614925900 622058060
84278245 183018563
60610910 59008444
365958530 660269634
261689854 683156857
914874657 194486490
142996098 408752998
989787510 624877158
253107849 150658786
509713909 931859751
86327752 348687338
869770180 285991592
30401464 346135717
695182837 992023911
623334625 496745868
186226156 662859263
224149665 681109970
956606122 31602586
811955335 561443654
668998097 482737023
793446619 22566115
481288262 293417283
429699893 294857806
758417894 313776896
688291949 768047012
616061506 174936580
26390776 347163921
347786257 342149200
245204910 816277700
366567524 378417980
197325804 332206352
949925530 554298925
737968001 217893523
316477176 538891160
991444104 340338863
646967101 894800429
248569591 795731757
877079264 738826581
752865518 467780065
980386342 436095892
297829188 435278755
91145761 987278781
109212892 670985830
17399592 718473191
480853086 63247467
309707527 566488966
266415724 400048689
190189240 196959281
689382124 555893015
936351138 130376823
247232728 16892034
146024540 166375355
371257419 948556783
90873953 577046813
219519910 962034763
769197340 626620494
676643928 354062323
482611157 11379496
600309846 997959825
739793485 297320726
271315843 939969179
3475074 563973740
193056893 627627895
479672201 394300789
59221783 163323549
551723564 439151031
217942120 963435285
102627347 839906184
49711909 216427499
379700953 327428338
728920847 904922963
33555962 295023419
129223073 298281294
822271422 236811375
576234688 472801358
290561117 772716643
552882225 893736173
607391430 872455351
769399094 542363500
34267643 621719229
558402334 716027760
76244237 925685663
823216460 21116783
880230836 352589095
622809160 348243060
547586201 21066253
428153882 723471496
643169866 120156965
531951268 905406859
749431062 614148708
576463754 809582085
635859106 672966990
613409736 231256125
710925005 832730459
96714438 675944876
380862222 233729535
195338079 242403802
758241829 110895761
401937303 612113862
609895385 84376198
596926962 37476263
290554160 477808448
140385505 370903913
723457555 595127478
730602363 299941435
825613144 532170787
352938906 38708624
462467325 59053796
701729860 340727462
399195688 458458013
687478652 238067804
403997408 971930890
628511838 850364564
778654811 922483520
198093939 746377426
34799380 331760943
272928434 60265588
108035296 321544917
265772573 72642681
579162872 123151061
972987110 548893511
540693329 658346526
217266016 398432566
461754967 398811093
797209824 370947035
135085448 258089187
290108642 559702295
271437106 273753059
804200786 536328162
790368606 654563541
694310006 422907570
358658398 707344770
783301916 120538486
280679793 233778308
655027983 91842627
746875754 164190537
876757124 449283755
510440155 642600332
485569703 870891735
867552857 116882200
39470621 867449034
957755179 545078557
936356279 805891669
738641536 881983978
379358527 576239655
898959001 40569319
293026353 925560472
598050655 465185005
39457118 902165923
414577528 945475734
955642596 14455642
676459235 932373665
432365082 147682367
365461573 184359224
521004323 862682697
747932022 320458242
318261271 865675148
497567797 736376538
711358456 458082873
332147358 255078595
429653428 998624034
584841805 939440986
845340147 513386526
938648689 251924015
89177504 828148169
51884292 467201833
930763411 53826621
541382695 144192603
541181184 91777683
831557724 962881198
873921198 529964518
550888498 200797926
523489346 941175989
307417582 139203063
746343383 65988052
911854049 278248951
942663197 639670445
66828754 135094311
527500239 5499725
595357302 783699605
384228941 26831842
847854255 57533064
250727989 874820664
677961367 317484613
588765855 813976027
501479982 930864854
19692109 248093779
403934399 610528570
955407732 716843751
10465778 726102511
933993137 768977373
112216535 775335525
596225715 280347666
607089672 749170937
565058773 760478298
676357749 948836672
458124592 5158194
814278695 429753273
257255122 437481526
153502084 121194036
553298701 47032817
798096226 471340257
194189026 725790829
667595230 316728374
394957649 327176131
764282435 398279897
866462462 87003099
162344057 321459819
321946114 365550839
257520883 767069883
304679047 550296597
551058177 836320102
514046051 528942655
129330961 696830498
200291765 360221307
963355281 275915494
149163713 671714914
628962382 917841061
826920103 263837302
242813454 429789946
334267919 339571493
541394509 237218295
496053817 481054906
585005308 856458195
153860108 805279450
547519858 177260283
133599624 828788223
221950316 190048922
422920744 210185628
13817697 554675024
447516204 302541406
356873254 505218361
505690723 996494232
232300201 937857877
71821907 658304868
132258302 508065082
867310479 632655283
726240203 244577524
18548671 183146464
274539810 599096965
862253573 357846554
613166136 223875378
746754696 894640422
200372415 788871699
631655567 301414521
173836316 203678689
166497483 867284712
792274653 37752471
881053109 869272587
714381293 279572893
935707903 248315253
755541839 838290786
740712159 731637698
528529565 70374082
479195057 795833249
453675530 762068726
872638379 95119251
267808474 272587767
261550693 448919712
386178437 252403195
481526781 197057046
309838714 508535440
979511075 522419061
20415239 160135082
911321752 121137801
778317415 381875740
504373202 608331490
518341285 391796548
64722687 100702600
713011335 229442322
601351371 161261623
9252773 567769951
969884466 449790422
514058257 789765895
680299143 47128770
451313494 772622257
436726151 141845756
192101247 896343145
91010808 42351922
797464882 320619090
894675236 842151054
144256998 347660613
766355531 384980433
135427568 956492867
184338963 892427679
145646038 306176886
337786418 999749152
706854291 64859825
287508179 344681704
997189157 934911802
200305789 945794566
227295538 271250983
723063343 646253836
802600946 492986645
387757038 968776349
726490821 283542491
610766307 989165494
160987931 780404643
534352483 778406516
207600145 944641031
210585578 654235878
656185331 647556389
644635709 817896182
784341679 245600332
82116841 904077713
899943043 266380113
871615942 843587751
596603298 482915106
876824565 108962149
43297994 997802060
11601073 591048184
727947156 834559094
175244579 825676084
108946598 984027513
964294996 168156766
552528068 376404139
711951579 491878049
717157599 44448348
978014017 586228656
424297986 963977596
793009592 247091535
778742134 60378285
102416102 16973290
387970474 464085658
703787457 146357518
510824439 796522347
904925845 946094494
639070607 536650486
429435484 693700706
694633160 26032327
172077092 383597053
789497295 539179375
65983488 189946874
439259801 901195363
13284170 686372192
605376599 154604469
886934462 863061440
841307412 743248098
512091808 350392341
775586174 27801860
148392236 129062275
837579173 812504110
828742839 337853275
442182513 36919238
365175483 617692518
236433085 163927728
447941860 118859612
678064255 822711537
971034564 789422031
383155563 393482554
86982098 627757401
832556372 852404361
988001705 68978874
165683280 937028403
631941762 760975401
682201603 604175278
573069090 425495047
99229147 596235650
353445261 876244397
621897083 424163377
84803519 240483556
41844934 134931272
568523699 992321793
710615664 229987811
618170334 122246610
687679529 114486232
861398138 33856463
246302999 513076341
792753378 48947674
360668465 618299115
953548178 517786682
686143003 26675225
947721817 852462803
788616842 153126278
322217465 535671803
151235902 137232093
796308718 591259584
476114393 808954043
706546798 750616081
458834587 63913796
23230344 802934776
14447951 709303842
711814581 397950942
610636639 134341464
270389170 975674560
167653184 890306454
824803404 955599747
932230842 744195403
449367722 832784136
856073994 9576866
287100625 233056953
606648677 924162703
343634353 185566207
222274560 704866523
438179874 117171343
174072757 289770777
19046187 177210691
808875537 997665139
336399468 108430870
680105801 677970361
648148481 713990855
503862545 868369444
693592776 83204401
546605256 958901816
971933752 759943814
316141561 17331658
417714662 425403524
911940245 352098868
772138038 957346209
232592471 870045712
348047161 785285347
141629131 73454258
407815768 727678672
377598550 84924621
88756639 243625058
445667464 292592084
681848758 606405465
447006211 178567654
199133731 586244815
55457733 189861909
46208901 69778563
920695940 396111325
382636413 726893358