1000 10 1000000000 1000000000
432981576 898317285
731200368 956255721
524345726 203849067
181527015 104657892
577187401 48028141
723952963 787140436
804226082 265865428
774717971 82023829
144294362 886592529
886787790 164658520
603736389 96467917
707579273 449559379
334076525 712626600
690529655 382227990
48116032 543777508
811130103 898818116
177095513 521719999
816947649 837565822
450617386 754424190
226862854 536547374
980257411 111369285
255417229 617727946
104433897 742655123
582583541 495430242
128999052 145915191
816857715 494417081
113645841 323209467
150362229 983003727
212686913 960933203
9311682 562377004
999786547 869538252
33010724 875106829
175163465 539847234
931446743 852324663
71608423 215392966
278043822 386970091
208977328 405106468
83424328 254754375
577854692 30501856
701869484 188066040
409685178 132085793
768994064 2081130
476319329 169998261
121992342 566097685
785714922 815940522
68336513 773972885
247204194 822460569
641304046 891010095
79631182 99966432
198090981 214354486
554758999 762868768
606072988 681667882
998245732 308586457
443169270 278448702
718416234 654477793
868035010 35849219
871867076 818905689
744370244 364352684
893109794 137553257
21025788 48464835
467084907 51846650
456474167 626030915
578192577 393110425
353884601 113418262
662836773 367197101
753409837 213238608
575344906 976242611
363898315 681281394
966105828 706472993
650251590 438772239
798092179 976320491
808843417 127967246
391450100 43319441
636217323 34576797
399026729 980289141
440723035 878839603
57665277 573242948
468502727 725622070
525555398 890484922
760584933 828207090
965234582 102788406
763701019 324093158
640970967 379839636
361345525 395906962
809820872 282844689
641721484 426323169
754872047 655034711
684334011 270691758
359907618 171583024
826534228 581028915
95432704 242113450
305309833 4389770
880797059 109602570
288732600 489793190
725749550 709254736
186995657 141318081
322525320 43178003
726818791 399370051
357470699 597856858
687707205 494184747
505855868 241074182
927282200 350272341
147137442 345775462
499450286 510724509
338364269 816213298
317954205 357233480
574146158 655504927
103894449 414570224
171728719 585550235
834787039 914518392
593964466 585287793
780921747 949370039
771692429 579832133
559118556 442691218
136212222 622582160
681988171 106918120
13765505 949488531
450648688 423330309
674444522 137012319
989324340 178074566
340585466 103718720
900767521 4313781
32950431 903873155
722041150 829507976
220957216 666913258
761538912 800681739
815607710 839454204
321495097 679801906
335944727 239866954
967557685 464714082
842810412 695894539
750807080 25224295
983988344 12810874
861062487 353745622
764712722 225974976
477217557 948466757
244873142 993111297
855100424 285373058
582509040 247199418
370999948 32918419
771475327 982553820
125203715 937091153
154196830 109712447
250943309 300546823
688565269 467451133
606952601 921028290
887245316 304045596
533954290 793216218
969547268 269383319
694962868 944334368
727819722 332380048
205117523 425281370
834867760 145199814
688250340 751906858
244687224 510958820
114592577 349552833
169925206 521982497
207588841 740523586
75657444 71476793
429014749 99237459
695666484 205989682
522392102 232083690
255386807 785722283
917605972 195215700
641656157 214171101
967814228 398540965
975602671 350439138
636991207 741025097
969256558 842664282
407177337 742246637
142279716 938323659
493754733 767177151
771658198 708753032
499103 852801427
689027596 646265995
110059843 731942579
337851546 781089044
376806948 885149557
981925486 53390899
395194471 637497796
509232835 347547980
676089733 833530194
808265653 739148131
234694379 678333235
380388056 460911663
826151822 212034613
380144781 405648045
748734562 203081967
99700906 649638365
850298492 194900180
503568344 198633217
642768625 41434873
510782006 584303438
963695684 618305077
564709855 927922326
275934917 924566450
642318262 949862891
709411208 500310503
267193412 150857763
206537288 810503129
601792801 989712824
409558504 896729868
117744502 501233763
138947395 415123791
257627502 59587905
762628203 978087366
502280609 221377213
392564539 144990017
204651664 57662437
505006730 186461072
820489710 586498537
241008087 929961372
899401967 781787849
672845282 210888539
554171320 798125416
728506583 161558873
524610379 105620758
149856591 306145707
333091307 967377398
860486732 57297567
96338296 362466054
867280899 172092706
31828272 9034762
386654484 291717007
562566700 478979812
234176701 209412976
682065809 623800324
747399515 661596176
158653742 210447092
119355782 472454939
517011600 58848186
138143489 885847255
82922659 295170037
980696249 51018255
778100758 5698706
61291485 379840426
634744547 467571986
543231229 930309518
8867513 819654346
181735115 989419724
317832048 47943621
764324991 601925069
436845775 226476305
779394858 221627763
53061581 261327485
692412368 828601377
701585794 819677177
601078229 467164955
567993297 528857536
225191313 1606314
625350582 945750225
453969453 73866699
234359529 721940674
703822592 472027401
942782415 24851091
454355391 900989760
110144025 772987542
741604608 85845954
906806256 960893161
447731499 160856958
709475864 95970173
678755437 907568850
470263487 57713074
750220698 937416993
71413490 985904386
579348228 778322467
306245950 776908154
26277073 760534174
27795846 538425157
742110162 921696136
274826809 748142932
813935377 10330488
180689207 658943465
283709243 284255281
69861335 674167134
936406416 727660392
991559808 415443475
471317256 677527220
686757273 160482930
797607389 614806426
557153974 329799194
130651269 74395432
40591018 43544465
349255390 624741611
101168992 199560076
636360150 605220864
533672361 491568062
338441287 557812383
946149555 695475329
703536612 897641731
622637184 8476769
297140291 511453641
746646144 289597042
442299359 408886007
467373983 484198239
618904566 861555293
62523281 34622502
911803984 310563659
557566705 603480271
983022309 693357497
930407171 337206439
715705323 303288493
807362927 250583602
332716786 245259599
951613796 146294208
18008028 462112245
984652976 28656907
591497867 980685605
556500064 912097251
726406188 843636425
498672146 650294237
310567684 361156816
528032237 262152501
489626909 121800194
508114727 749720454
480221072 257980056
571467363 587977655
585956774 961725369
31675146 617245537
809470541 210467786
702395045 639154649
742044233 189632495
243908045 463073934
880664566 415364150
491988409 781243861
414234989 71724681
421525720 80250456
719657067 415158844
756164715 789751993
89111517 176068773
68727883 195469527
487124994 942228510
104457629 924446805
715571933 358886192
594885282 371669900
192920017 271253167
874754683 556632264
467697482 390298621
543875284 57782269
562879349 734112983
371655105 806567907
655821947 614456508
781594052 268692532
446309833 759478551
999054638 489036607
752630420 825111181
236646581 422428753
442398455 913565592
831665681 162135170
181778844 230074178
758942327 61775198
745091524 939032857
405532488 227682564
728439866 976640205
411900816 543962113
558523821 715759797
24202857 841210855
174344589 214932962
46198111 294775265
818868063 400248388
675069231 855324258
34303838 87265856
316461632 892374517
373514130 739651300
729493704 142282001
76856673 348992480
397047339 71306096
214776522 701936437
960683004 419981046
648607899 549954501
529009894 718638440
842867600 115455651
54881088 140085003
689980416 835517458
187602947 71846921
341663229 969193270
714298520 87865863
729522285 462317738
98123273 622017945
290826482 389227909
654299406 90395550
74572481 66226851
547639042 676138351
209144163 77448775
282718179 633044536
878003343 568671912
441119062 138681245
826469926 175325601
615780124 243815125
753921805 362334066
332706418 835394792
115456865 98539037
32951087 220857300
139625541 78379375
226356457 621145771
679301491 877536230
802143342 650585345
656774243 804759560
284785671 588864993
788010094 934584097
917056230 692133771
311650292 98752723
711654564 928087030
83237520 29650592
680031641 788461381
492547143 516797047
979134160 369272001
730537493 315452134
636656069 805232625
371737846 670803279
261482382 694042458
587902648 56263126
922442476 95675712
500140112 12514562
404983069 491663752
780761505 585591315
817276780 142937241
94708497 646115069
15577001 198541560
926138696 504580589
319915346 741023459
761748227 474171649
277740810 470205559
132473797 956010577
852671417 641238534
173759359 893125525
931646277 104193566
816633184 48020261
785529997 213100553
523083938 71933907
430359030 57445746
325938429 147190592
329282229 947036273
412542953 571094180
674812236 583263847
330573728 812378961
488871921 560725980
211413903 689166145
881517466 150585673
960524041 598706137
190998389 61790075
804513866 460040608
76451435 602270370
701234563 825354116
404121379 366579370
92817033 666585411
428283895 959285407
133471285 671341168
54365383 978151375
565949723 584932842
135088560 384131400
705401451 640198120
807422214 786085148
760069956 428555124
860905425 79536297
858701754 517477792
334402306 266607607
439052729 622407543
781999491 317395736
995541210 434287253
508686701 233574541
892566193 104801573
147387401 368131669
969574685 545540434
91183329 819169819
831538021 828303139
884180092 832086713
11622132 133386400
852992676 547756647
979675259 510834032
185516138 762266947
259497644 654276423
757339555 207135023
609115096 474287224
207336967 11691229
351491510 362390815
776729207 718529847
948947966 100349735
969981771 438800393
864297479 662654251
156637565 359954479
607268542 31859425
311556444 960825020
728716573 273326194
453647049 507164797
890574161 752904964
272257439 957705754
140257774 611160764
473790841 522239202
178744353 592011022
602308039 198105491
896795028 551388291
315970126 541890245
319499163 510133505
180891069 284248052
541729052 860278523
85660377 695933919
343148041 258822550
9438625 593763277
168641484 149803341
485724309 720912947
666605129 623793708
99866013 834413767
252217990 161924596
414000684 24690731
355060831 505280640
16813587 621523856
410256012 554290528
901439726 4902894
940363629 528925420
52686783 938126663
572861877 129632020
209907462 827473734
757080163 729595347
15261198 944290412
637481079 627907759
675382853 930975135
750365644 605398026
389846119 364780515
322194589 783255194
930123177 238425858
234190762 500299220
201476464 603159224
594753115 337061986
466474643 430199430
134135267 841130858
247329681 805619969
751110308 93980449
115356808 660029137
835872525 228409355
495540693 329298822
944754950 909465328
904050939 780668979
878633341 760267208
353814558 457500812
726931248 705423030
930773987 486589716
382351478 254933692
199713040 748224171
947875392 224818251
347621431 778159492
277857294 229583215
34217904 102560869
190485637 256591779
278813821 805078792
121400044 592002795
371150264 495997110
760382174 489001031
517783379 456409833
517943404 6412855
507251895 328332810
140102196 982502713
144488604 30360778
952092876 805908377
131210976 516884327
730214532 492554793
783446388 939055499
131177768 141370306
824641307 782830096
646427383 518222809
83322702 681839908
781924518 780329806
384000591 62004086
319301670 4233329
140524469 255246185
210322204 599150917
49659929 609137313
651971633 82125190
12086843 758556570
833695115 348029849
666813265 158492991
531313341 100406978
167251615 200978673
324661350 710692044
522642066 454036160
559290851 464136997
712484070 419764574
968570456 29300916
105127049 568724004
973748817 481099803
491277188 578176310
329177197 319974996
311125414 695198326
861709413 494761191
707943600 928020641
341722573 365443026
694808513 509106999
933270484 73441324
553697326 393546315
508257324 738749350
192281508 781476517
320490923 920653522
423678847 61817347
956957159 585554775
384183105 648003066
93188315 473314039
705178636 849246166
745343063 872460874
765290031 830824867
442362962 862535931
790165851 454790768
936734054 594918532
678627467 152283850
772001470 25978014
919330425 207390330
659923864 130664320
541313219 880380008
261302110 281227620
700198376 568534090
573987047 523261133
740339984 802067154
811903287 596453758
658481718 860428551
903284099 985202315
108726609 433234022
678485451 127575054
979675904 256048421
482149242 321171301
205945805 443160065
496155884 330444656
677019307 189427003
54408555 289431640
721262386 196430542
864314850 102062140
782280804 122862061
409790243 142955067
194592578 296740837
124240655 956580204
797443089 42283495
807452866 721778095
906721589 154715250
476420223 199881826
568200901 142849480
536271405 504210423
229193167 895810813
123690881 430761290
944294932 913908026
392185151 966901253
943911392 374572017
697548060 467250380
77053709 235781250
314825401 452402461
43471593 667947602
827512738 973388779
971117340 160399917
418805072 497750304
305463757 183075940
347241465 644745591
955168571 763636190
179466353 238720256
497468436 433890780
296100915 800256650
65598135 829252770
588546603 71792279
414191663 616094515
571217930 623450153
947382970 152706965
682136785 229496732
74161973 341491361
812555122 97890928
768057440 937618522
961470725 304693878
310639202 280368221
862351132 889681464
813509231 98530385
876497637 45472774
679861275 4556286
930303728 44115673
888433189 280661814
722854324 934738169
79481759 24001728
417162973 384089111
379627904 60673675
14767602 167186814
721027544 866119183
201940768 924627268
856921424 102035956
639581520 641257395
132432546 59897016
81732124 450901276
384364039 4407939
874018015 494771173
680179906 55668652
968182589 646358258
293427626 208511716
647943701 530363139
695311728 436659634
390925327 803101316
30302636 596300091
278329580 600436379
663541934 259865301
835850371 198411984
830985332 360790198
264254482 651255116
96934409 1509348
454857701 679315774
400699493 310754486
633217143 661924725
643085147 376278825
723784777 861349277
478298293 22531042
759685868 156389819
707473695 249726439
696488300 618195062
151643726 154535511
538728798 315214322
365625723 969676341
605598978 215608452
56562402 799627218
290731858 968790274
623955132 705164897
694257170 526068069
139828187 966302382
797625542 914754879
151630693 800393243
328176318 249839838
495723673 151757641
426705725 69778177
450538712 726363752
633670172 963651949
896084050 498187403
385047767 939516485
56389853 944317831
134818843 119936131
25328501 208248876
765677262 770409616
771244750 882787809
121737797 827598330
104835811 736448918
196074798 533132617
116209650 274020956
771952971 359539783
545122448 770277169
580256198 579895686
162779848 295729019
368174241 852657204
499632928 168230243
637583761 416418641
652285288 320561936
308298538 592808696
710553826 831442068
684628068 534289193
845119207 588399749
987262985 610239737
834914401 951455779
380814015 660547054
854907316 785501992
45407467 50221465
518338310 198742866
964248765 98718738
317501542 339749201
924295124 929161255
844162490 194895607
841043394 59160714
120658924 222656455
148478323 438203423
427240835 45989134
259604048 6451403
577492833 186534212
260486703 914345668
344601847 805429764
200782525 87705298
865260221 659116982
876352991 963354741
299231030 481676579
545440219 648065309
770775192 968175712
900281304 989272551
898600317 609543503
42893453 688262265
784715739 175075063
539601744 562061822
696168438 463359497
596872268 874013280
369317059 558932073
394944149 637948161
691927638 706084740
910038839 368163545
787421401 711978021
565602923 636273246
317173769 640551039
583775686 323858878
225581007 281920596
406353932 772181633
539028310 257314966
356867975 350669220
69887213 628548808
299523509 846221523
611842440 958182577
284868233 645466038
100425391 49518402
564898684 899947596
175464867 175284865
311345857 765989441
58731937 774200796
420106820 760871891
854456646 102653389
862887892 217423589
512356096 624673959
725381871 520616463
247687817 410565888
811631582 120931842
191605975 99378858
99173587 416879413
214352226 122501933
392273272 237985858
5784631 647660513
874845002 422833654
660288483 800369039
434912315 535455679
759698735 72357950
283742655 86835631
607596549 805729952
580752685 293810669
185948821 322802653
196212998 810828988
190891014 683082112
984599057 484413968
284486718 422030483
729677573 807586015
365133702 645810662
376248189 771775930
118152347 909707276
41668552 434937506
532839794 736256632
252290499 32764856
151378567 976213697
665765302 469399470
2553201 478412265
400500797 727156098
938979384 413530204
819661752 152112967
175838527 745075766
920911174 802533481
472913355 615008315
217133307 516771131
626638488 120868056
400823149 71439749
777140590 118809674
49461212 592215267
784697216 258334431
925430193 159805575
404168340 608739705
966911275 561639724
763851473 596424349
161385863 193069517
331606683 861397997
87152937 855853042
986343314 338962856
837566781 360034044
383032430 860012830
285043722 459800718
645909350 775297496
565443826 374385646
704685874 183022601
276993217 419562689
725253279 866124863
90888891 639939799
18001643 819412199
303159711 651296528
237609953 514571235
749908690 618054400
337701399 763007708
532021760 674105063
597460789 95922096
112711128 494288071
596152769 94378099
664405966 815565028
542061897 628965610
543673792 746262590
146925388 771687928
597841330 771661109
823297874 437735457
679198243 625821457
433951522 20790341
427149606 142127599
968475754 274508742
631097776 885959468
207425344 40044981
503470143 707707655
769025197 653235003
60080445 306630965
543551398 716790777
751456759 767597993
797672516 577142663
132053159 703427224
582479466 190098811
953173264 813354646
177507759 935089551
769386769 139246292
337239519 388375843
247253306 179793241
30465586 588294498
539946074 1461357
146217061 120584364
663179262 83925044
518092247 572407233
988602776 455726588
342685693 906290354
113074004 639727858
154072562 899444215
209113474 542442152
497140317 492445237
897188360 19558652
115842310 159938265
978658809 843032967
151650948 923753841
444306237 922272608
611713058 497720221
833004010 210578529
310183664 108675490
704578351 903621126
970287981 558071166
47155063 532963995
74811791 54550641
339834649 926259064
10548800 694554023
604548862 876605488
724966986 333040839
615214507 694699401
423845522 60653700
887229730 644935423
225356434 881015012
685992898 954811217
353122260 209425240
128754 578216443
617898936 942210505
794769749 957964796
90063911 477669748
354476460 519885409
4009251 811442520
746728799 716685389
827450088 740728182
378543416 879511641
855786583 55830951
914461317 511685047
701854260 89803415
998317379 633586475
208139696 56458942
938889091 349399700
940927561 605791271
836389733 522743970
878607676 39072759
239110198 714666513
789858382 681921574
914237933 827645453
237611958 243877937
421530079 14934327
33200329 282080535
11254840 735643360
209101745 522181914
687429551 570407812
351112766 112506131
733289792 846472672
120031576 441578744
378160413 868783819
453159686 931618444
774130402 807601058
736836294 931566723
868448393 73746127
918164216 126067233
815268076 418501627
328045283 607935143
120822239 453142720
935217644 240649319
2454345 797995019
874404361 176951633
347976789 475777440
688793404 365568697
961969144 369940396
611350325 739326934
394916986 815005725
960018020 156582578
875186262 489937649
933409654 389129187
649018784 392831946
626502574 791896887
216935199 509336034
316069493 234265193
513682022 899963654
134739826 354245065
381322786 952727168
317895548 852841382
740039358 935285887
691923667 967404303
568091959 271233216
914148138 243662542
201224450 22476468
878149180 513473705
983259124 326283842
382874174 529321675
14991618 281991065
615303093 910559119
619685651 357208361
715429404 26779688
273018273 463404584
945556019 740079750
626403060 690852313
55611860 813028865
19010503 376103277