1000 1 1000000000 1000000000
430280759 911178843
8620526 767952331
984318926 867990979
461767630 23812300
92744374 845014155
736506641 306138209
98158439 528229558
384231088 529015417
124191954 260287182
445218084 127799371
861972052 140763173
513531172 508623099
276452927 649179438
833111089 378061297
772268380 354089687
113174552 658606341
159243881 779703363
29945170 961377714
36762384 768292154
67443845 538127942
615412981 136573229
310732681 400008107
170990953 215084470
549425520 828722006
202813745 72079901
976863830 852763042
383946169 151623703
421147834 781649599
749391448 446418922
348873563 526835945
489329024 629667462
412246019 959784326
683416968 190241682
527130849 814172705
330002947 158099987
976111030 807139387
857404437 531769766
819894954 488713378
735453046 789545948
606267223 412155509
882100658 596632883
512597332 211972992
845533535 930736279
310763357 70126947
566035771 710661092
957871851 411811337
228512379 701485638
888650445 895650565
916476240 14182333
802770112 322874389
597398746 148586448
630158977 787740817
299222795 930946627
537762693 607072845
85765450 258619755
70977127 508261264
777547498 625618578
451541217 508596079
982755061 507628457
471070634 498581069
354665715 830850136
506300195 940342597
546685018 635793773
759774080 329872748
829490275 328265919
610091655 247280928
17643542 441701143
791422365 359225223
242016724 927263647
256009649 647137663
231694788 653477041
889580245 246754083
432540086 1352638
522375769 509942203
302788205 353023514
822966852 478148737
68005159 513823510
983760891 705340546
683193613 4772564
552461188 932603980
599143886 992862696
169592402 220223294
539260125 871827807
316113637 837841282
3654950 100795535
825260235 129095860
786523551 490056159
877877607 161932946
843532258 282962134
380049135 785751654
316663508 914637578
55814481 605900073
118750599 478800460
706888569 797191865
918538024 653776279
966814099 881563105
634868250 31031419
470825836 939368245
146499984 560722051
777412096 885881500
118707946 738411016
106291923 679208126
921426312 467945713
134074423 716026951
114129126 463335019
737643779 378513716
963367379 16257992
861358504 208692312
769005968 827651801
163130701 572710519
249450655 956856440
962649511 832646273
984877281 308359419
359346580 941052558
566649205 185730351
435709279 315301593
42335870 479433250
831393877 714774862
886252197 907548872
924064509 342072509
738076566 236850843
533399190 305816522
725351124 620102926
765299912 31554806
273623697 590950939
14684370 881120411
880382037 60566751
568611034 660069768
621110264 13583949
908811222 456148498
918740634 861290295
56510562 285871118
858082752 387081463
875881857 836134460
596713611 425528924
539370969 506321792
11156986 317892709
632890830 394728157
935446232 452462262
56525431 570605291
277452030 949806150
762589293 247069310
31392687 616049281
913937989 466044076
103080724 439994768
578235405 847960556
803672288 133712081
75993020 397855364
489576943 945693858
439769353 425692851
787981201 348536078
627743107 290182431
71991313 310140492
566365348 948209010
775185907 992619696
313993514 550497393
966488589 633474103
570977083 510674008
562451193 499401899
982890461 359979209
120631557 567617984
654407146 132153425
335732005 589241254
614219543 179228485
916137792 483731766
639594980 953984295
234685085 365215529
496409612 991688462
71747256 626645301
801232027 743555383
464532853 325056123
31276578 46399389
472940189 992754636
751476769 424596741
914138566 20326951
591830594 507221277
415596406 946181133
479456422 78711222
615528359 575402705
836009195 467417882
892288593 522565039
10406123 492763420
537322317 916496757
887987971 246502526
972753800 960685188
49710497 862874335
143013305 354934242
838759485 750504214
34188900 249166783
407776564 708152854
864758834 119061192
88960143 947320310
582367292 378859528
963580999 395927977
144327818 535625913
159463826 185579842
671175772 551038707
417898824 935128516
975070607 824164091
729050154 168449312
476021968 807402117
111634680 855589795
942257311 886864434
823494288 883070725
405664365 419906045
740341879 58449716
603855887 51586972
276714267 681829333
247368484 906803833
882928514 496429356
679798147 457151441
812150929 13406418
231894330 725820877
880713934 422676074
925008300 657708508
351344527 9580257
577671809 536220172
752413007 732979909
749945271 66951880
446711205 247996208
27622362 418582918
511289598 618556885
622136572 63124662
56811587 531634682
127436629 594448918
462634802 345225637
33158074 932218676
234942761 452463567
510719525 997531880
802889496 479686575
347740585 339460696
685674033 839769492
254265662 514045021
116144864 294745647
165160716 688124924
558985863 932920137
445829618 831742672
169418585 402707530
917800041 549906341
297960474 263817585
467107131 615603931
745018475 889795944
307733188 332534832
833511693 786060535
136244820 162654679
116469392 354341538
839431973 488005356
928430616 745841043
777047651 779244631
173893300 287610655
145149337 858744704
13062786 153859189
486154877 871166371
135396462 178531089
19273347 209230725
426221610 488046974
354806775 140323645
242931759 572203723
78918110 597025182
577481831 433650491
168426067 341226508
834268233 66971801
750245017 999876760
180785890 50227273
155089444 766411228
707113982 895952359
843484279 534496009
374335122 744373495
683066209 1953151
747102618 306317190
324353284 677799345
238026774 822503566
417952606 522561043
378267566 423243469
15544889 132864562
947236868 199762411
341531948 380311782
512792509 665337071
869185283 369535564
560538064 49158581
207342245 581904513
326240403 64464321
139637666 413559404
228980643 789264157
462034581 746383741
365127487 35310814
255754491 158333987
435853901 829335183
396957056 288601157
205622829 238618707
442657666 329790110
728384207 917464211
311000665 683256246
125317971 186936711
175352567 247626850
286615122 770384351
763595053 330176120
24425331 152849835
359958383 695064600
589753968 902802007
575843663 163565250
138428053 757038715
733063792 534475366
386558375 219643320
98139318 426276156
921118079 337151218
345693584 187695262
153875310 986357139
404202877 964722372
845123279 828351781
155598369 737519447
236234237 250425150
494339165 990875334
766438518 422546790
690056117 200825070
899435057 651487613
294805904 504857175
930139624 715667083
461100795 473963061
602360581 828000973
225542975 474961682
656373279 401021521
316069943 557504996
893782317 305101401
375110894 431506009
238879899 821618330
188589613 930126483
474717454 831356168
869538922 346736053
612720657 855483766
778591634 360353920
131933948 621342542
850884832 545078695
903543855 675390460
534684733 20096699
444489703 856501707
591659879 916354439
57639902 898040600
938177607 495332326
392730907 98473051
662874111 889134288
370198235 517631936
495278619 177007189
257963609 977121926
746308716 462244998
878593581 804867394
32473314 559161008
491051735 629731868
635723633 89497181
268193004 44851909
859807564 171478378
549483771 888339981
207060275 366031032
150089257 585952880
117780668 229916048
54989406 138952123
654300704 274244770
313330031 176583496
155779321 601749955
7576501 109382217
85496239 213091178
828626724 978000952
103459934 350331313
206897815 581717933
652579956 156597979
686190457 958594422
891213317 950036359
478145961 170922721
748929177 65788053
987257076 598770458
851822346 243339727
777214147 862842019
450245562 112745843
577027008 965426271
692649739 349636645
758649319 962889299
297171987 366396603
406159825 251134226
66169700 29384554
929963367 470945357
722166979 336635436
838627496 815543601
186383687 457329995
87157146 668512135
908509001 176763419
585644343 615138582
939637156 965031952
328851093 880920142
635904481 403758379
938555761 662374175
720580700 75588141
580205320 960396356
715025010 711728246
497981877 816344607
787495533 72416059
222851094 25057297
942400726 825965173
652176313 774521556
275929874 419135906
123344692 384399798
117448436 373338962
644474367 608732379
135569310 579047823
80193680 383619781
555014605 429338628
187868899 568431313
162490811 170391162
468294742 107097180
699664917 742891256
234166341 160449452
987426602 937518883
649661202 495642955
902053630 637157610
685839279 706792086
350390691 718315418
540607505 452611961
153057569 237824267
550606120 680684831
242997375 444631694
578096944 940743241
587961110 989982375
281932434 125952775
532027672 225206312
211747987 904597125
870830124 390503424
823062595 375949678
491276105 729487182
963033641 92716341
148314349 484892742
177854463 105637084
263436900 415963241
39497339 499146134
122469270 955921754
168603816 474046008
649765186 630061172
469347875 195706240
933790147 565910333
409209430 744236678
782475356 234357390
730585040 784415311
968502359 305350889
421443644 304004624
173315300 227800826
888846595 563726281
408253825 847636164
252757397 452964211
351481812 760837402
329456332 772738901
325706814 812973025
915962735 670273542
805019002 59772360
271692029 954313528
396128033 904134800
464299894 332147456
222068125 36401947
387081148 561018056
842927413 192525107
539810069 9438151
91813796 777891271
8571209 417097679
64197606 705096351
788599095 542945808
569698132 687070428
613710814 545164995
497657758 990986444
623491311 67754361
137450912 774766347
492516389 168065786
673006687 531307554
432736917 37770398
995710398 493483092
769488736 404383588
73542140 696341061
482850235 87775994
315486077 545688679
239282582 290304021
383004405 451463176
444320323 262689064
444441054 300161775
796821353 281067621
928954068 166445981
680849457 742357659
914948493 806296958
595188480 311997750
650595320 692349008
185939065 695097443
633102982 908962547
448415589 832097981
716807713 336036729
325056748 304314369
941344295 635450284
411327004 962471142
999250917 484427688
347282111 329937428
342077607 851251508
914889055 77320026
965758499 408901293
967243147 790019135
545650726 162839745
313051727 657047602
200838377 214858607
186319025 477744222
163275528 183334959
205859268 220982363
682949123 992253786
921499157 65219823
803957293 570870016
443645436 511512232
152322885 969983140
940952525 487803280
554222250 699675239
288418109 871918324
388457217 880339069
67275246 151356465
820410142 430342230
811077064 936957606
982999723 799306478
602548496 259698343
295525263 208423448
236897792 338251353
241600932 444299579
453752914 220660340
376115898 639469365
616753254 115794095
177412407 283007265
492749684 656531845
699378719 763800305
897834589 922405568
169258678 835335614
271952588 18316027
596661240 485755402
195170803 909705985
749113087 235006338
334979334 183098937
166761958 999856420
824036555 392202763
156359273 458190331
10984570 699967695
360904443 600269503
443376231 334659
750421510 623625793
762041024 542296359
940988124 960143196
481661506 53827069
108698756 421990689
864849308 322850891
423695140 823846458
869138736 313470064
653338746 41869632
451220938 933047447
155259146 67825626
984211505 102438549
948240105 925475609
706193238 478831055
475178562 254744653
636742772 27531740
386771960 309357238
328298824 203024485
521883292 130768244
857350099 176216971
851052121 783642593
193426427 807630036
609340495 997292802
239306505 717120648
65226468 37940943
531873901 219449674
260811595 526125459
588448562 289617000
788043715 552844036
827608298 378521833
924449216 381056708
676532404 432423046
694121324 243038915
79411961 71255977
115149361 958967546
964767389 571616072
778649863 961364511
25507669 178778836
228050646 670057284
266796207 765247664
386884701 332714638
426419897 965889057
551299029 439473521
454179298 484736192
517625466 602510252
525243346 197149795
69172978 531571100
472480511 202477440
878985290 56534218
360153939 934031599
491390631 373222159
132339979 450620901
285103371 97242094
690911553 840650784
570397030 784044696
367459257 317717040
374056010 246232771
919267823 705531226
175656097 909112421
910212855 57948682
300072803 183383127
532606406 672950406
782448565 193653918
625639319 601917448
7266227 430221147
280807152 369813293
2403657 939444513
65854097 278464030
927434456 438432298
508239721 712630475
533968841 339039518
159465501 983758841
461098772 653964231
805956198 684059785
443248595 396692840
334364127 366907456
398788501 593015227
423566379 779603445
999119624 813750279
787295135 340573023
518687999 88262082
685943400 142435588
381256594 741502110
59911902 370625658
957111736 642003475
996821512 627967828
455678937 285924908
558548578 550586655
589875110 257465144
879511798 169643357
469655935 786437830
163738174 424643128
585480172 210333524
904375753 853582845
956283763 184743946
615541829 887266546
495137035 969654805
283360661 52088271
358774793 250022446
932044026 257976426
729993255 880556707
373814801 814643571
885475996 33182951
720907526 806548228
42545084 280820522
326964554 469933873
888859870 685588376
877670900 586972384
677056014 439151358
640849555 53537810
625207836 696598197
829510575 427729098
182909639 75064785
433176102 743330302
596432648 679479194
179478381 321451488
495175364 248628400
836463069 958265966
801462928 66676149
333764651 258807348
778267130 92867165
36018689 156096115
131839461 463130200
453325983 759437681
701426813 202461656
120700559 651705155
834649470 950277946
861255835 967047957
268865553 489438691
97075353 970134982
435651690 333559639
858565197 196255842
62747846 969874112
129508743 346998790
766421532 182710168
753579629 245556977
773804754 255197810
311880118 993868503
771572294 526801817
793948036 623778195
192214195 487511386
51030736 657352921
585584861 234953110
605297596 76645369
410487777 80399177
447718022 817966367
963504935 438813355
686858333 445600892
850455293 905033651
897762768 598520558
525743401 834377831
491919879 942763641
868039465 495946532
504240083 81655144
434441962 338383845
629772044 383932018
112365127 441657276
790978964 272255224
57342793 368483227
765819855 785788546
519848627 372420902
638299461 382886931
894827477 966582140
867852813 3972278
809264740 860677408
323830444 469015009
546767084 91184363
548987163 765443063
610389966 109355394
44415054 695649112
778051772 667269557
391589029 531569603
906672671 519002776
319524984 678198356
805144928 401183331
301525358 117630942
301482056 96787810
232268789 407696487
770733336 943211198
138378639 889928941
727839528 198733944
550993500 244192831
999521492 711953881
94800454 663467044
613137598 281122350
392642861 341987000
35444730 582316694
556967975 131158464
183202988 177816270
238449597 656518142
649052345 682871064
468146582 769784742
544162213 917331648
793203151 375102351
973538550 748541568
538650825 688433454
415919444 246798829
391248428 212344637
678875561 831017146
998035043 811901604
907658022 839530389
395535097 515934701
625729746 681980514
969134007 124559122
523628581 628730537
310451128 539668543
754318309 793195049
958612976 439424643
666588260 831951752
134838244 557920758
58090527 902683805
404975707 302713588
266607091 9224733
818501060 719425197
368094151 757680550
702517910 195876362
804559168 932357944
553685752 668104458
331114121 62728105
628502809 155152304
922467809 133723469
32418129 994821508
403147317 835244509
640874446 292922847
16975436 749916063
731255078 526309529
899503633 841072916
85113489 475655135
697560514 678992757
746917404 306168917
143800212 388976363
951379320 589985170
757725414 129570537
699436113 877703149
540342253 525733937
456871301 411497385
355230629 355880028
743858327 139498081
957860375 592440136
393381089 80015330
426552371 744943405
787222999 612031986
157301047 177804541
876297036 580725981
971092086 450365031
594430715 427236563
122343190 735694226
858860698 432218005
732268032 451793675
584795901 732811831
58540619 521856673
534264562 990522094
975470604 259935464
770483842 489230747
515466534 48706208
538219181 392499349
516964653 484067013
468698954 829752116
555962846 957252376
685906934 182431431
893173623 132318540
131404834 252393245
147573684 61693900
829778732 92424095
576381878 824567013
879520666 917696528
983468987 334897222
308439004 280243454
440743152 63599774
102952630 237257045
753640668 771923960
371903414 567462201
261584638 332279307
793483005 755360993
481880361 393966870
914802778 866300775
891347770 62760221
114453761 49717643
920024356 136499250
826645738 35306309
897108327 458379744
79345430 7150276
148177896 3138047
277041793 862019980
867470048 739663418
110766193 366244416
468107516 660666206
293825381 735041236
300727518 632957916
682030106 861334437
396716763 600855142
63310727 838405118
971545622 823523295
205417490 650842483
67497091 101173500
484446271 377946790
940004464 654487251
824374576 967866409
630072365 479163721
642426529 432335131
914710179 568884279
791323536 92046306
301431956 554213202
32358314 510715112
510773634 664072954
668418109 809121934
567173917 805642170
559867299 794406445
53810606 256144863
675494087 498226272
657056394 447475722
573069986 341863841
972718529 536509012
127627998 866843109
826381877 527962738
439125165 244112002
496836542 243655878
54131371 139489523
163215545 205849769
468618068 832126309
327197042 770175547
771472043 198566803
611165474 555613224
312319425 558137949
186928602 278424732
394528021 774456268
648429068 610298578
307400748 99600058
672471596 207807744
13743485 286819184
596036588 863310561
633976182 567559273
625119496 22456837
540170567 350192837
841699297 119443662
557880360 440434886
321500323 170167608
26044622 274357608
360396217 410637542
481880743 989715597
141964326 1765513
605454742 113582718
788810101 673387320
5061997 515841715
17445522 834649809
67835370 948741120
967949803 22433938
698909012 670548409
878216271 435081588
476418863 122416837
306772724 749305187
848654252 506203492
532055654 940852858
174453017 89510827
539347653 624473266
979744148 663180962
884703954 649293955
983901514 394484327
449074842 688340029
591818352 283069402
182077130 155146861
394509417 41261369
915706699 478956449
156384715 818522104
1566709 38652343
65529817 182945030
204389108 563328075
99411893 899813625
48852119 676269109
18071874 625884767
760669868 314353622
186350593 813675283
427004001 774763533
482944493 116264994
901397396 106889112
454633483 951739904
936258653 913978748
487033970 757267884
698659292 494125324
597492897 793933977
135695274 724412298
910668014 190996200
42387043 469411595
492974497 606413145
352149270 322801783
929082581 371724733
336979615 618854351
393314136 54144799
557046442 282238285
463022056 855681786
538275290 826464042
142384214 354999342
48444423 722897662
506667341 537444920
269427656 206319489
672704891 435219525
173419302 75300108
975500522 674168006
567718215 105163928
948554585 785395028
905036948 690078691
22378787 856239437
409064659 344042395
468003237 361577310
948500096 746557902
607004385 306604171
532960378 349035361
414230885 927927551
192663805 847013537
472141454 520865070
247807399 458838878
555283175 695298314
745963500 274305585
579344594 796411840
835081437 490886780
31454475 974407379
499901347 137646057
487628162 641208671
890494378 597905820
240778312 832770011
148588252 534584065
120419295 401504490
441296000 553239913
135643968 421313723
859440392 416860706
859301736 702612551
961083380 865974990
377347050 719607430
337980704 63606673
927471624 458038928
466962930 545841261
960421005 937894695
858797319 937425791
581490427 269622221
728636608 913065008
114885527 709628556
945062537 227228032
716834312 14979691
244960391 579787348
522086923 509963284
770617445 566245793
110903265 298437758
50749683 617362695
138594560 443666176
31478875 254487654
676567355 227757684
605082855 967794994
212656537 660170367
987726951 811954022
779991611 671350030
982080732 357765080
399006848 173997383
612083060 842259476
888395006 749304305
336116338 330147858
230355316 795536032
298089579 995876868
556563152 816443038
145635832 520613288
587680668 210172017