10000
624164441835165029
604652442857011127
134238702797318480
538161320538375343
10101010000000000
59693118218420857
2183621450414461
904524330055858549
42420747487351368
945006952043617081
63739650720568384
713534619820476183
971301932532493351
841059669245278722
258049476484347026
15317904962280259
533586547439203343
154473172023259867
406010932342186512
69603800792229007
51509804624978941
947109857846945942
146013460917141006
863107355100382657
13749147062157050
439979060939313616
983825326797266021
34050637408410045
890069417142054313
387468318690737101
833748657104916826
938994511225995972
121377486418279207
596167528753846703
802779774645153203
45857595838965405
588339837091226460
119088209368606455
10001010000000000
556432953056283599
700148356585997009
833747762130159591
850403570334211082
697106693869014025
215851019693614633
572995492177312077
234288976080424225
87156842032060753
13775732392844357
802746660014629937
362144794921006558
601617719776965271
826143034724813587
871006229059309757
164170008264914290
50420041393061550
101623821809822159
132634431360866147
3440078746622041
375396524420495191
550337021394407606
986093170127639840
387421026411518190
873033840089391907
82177421064400621
245157870563163830
686496741372878121
18295943296188416
85718323862406157
27829538257953916
279379509840783857
95570131789602705
27832381530008007
162820522662083002
32494452997565862
10635984081773557
76085817834796951
946962279607932407
841060009810404080
851145451716948026
878076179649935448
233025537551660157
151947659016220167
144555126099873477
963383180712631037
117364782329651845
496555398565374041
262339224557506382
376740066237610950
283395640823943297
432632325474523265
8107087069524496
543526620290571242
27869937703411806
500758841320465771
64042009525284929
714221028055778563
631389129293692859
549766529124300931
656339563974206090
259266928702115057
35973442068119080
97299661737949969
59700170908594401
774326737332848756
205728868648447693
14335414540939873
3411614785540901
218346481898901989
315868787787174343
216103938551915441
152982301304126401
403043207929642441
87848997769475857
591047811283883783
61999525181770483
984934294394121792
368386748922204999
327036523562300256
946821821929197587
398850174454011209
389480601575720899
65294742508761241
61992645273844375
171541061090149806
941507250733432661
66540574981575076
82176813338385240
11700196786839697
106868923800939690
350401132087118910
2673667727965441
101101011000101010
251495413810771177
4289078154030916
96628037351016886
182979773837106552
824357344176505163
32372442048291067
429922877542401640
669682089662785811
41482299793444721
23768136446100156
210768483222134009
789116310169434367
597945766026420901
207451133184101407
885480472130641451
8461763351780493
138249576979718401
168625151431370370
155577914113163907
180643367697680021
185249850792505321
520411736936367442
547034498952253637
50460955332860761
35965995692199369
210694858790423700
841323096821965643
869311583212945517
822178893799233673
549765873000027031
164703062288797769
471886506583981723
651778636250928983
99246114928148787
909937090863281757
110111001001011011
269625034841997371
815791121676684871
545811748454858233
658581235485422942
860339389351887121
22569707607088041
768241736762156981
244827073646401157
66409185889240805
394179461806636900
189192547547709635
331113608387078401
585877745272486145
12838498343874507
95167743008047864
369645087941406375
454491332789596453
564059979290232983
914593775012366400
288826276000631689
947910666015952949
152954572762447112
102932120860220682
713781985160740865
167988685394035985
797025403984264451
973135618347408767
669181107932325067
688922949494263147
395873060040482
841065801252323840
3038592534964900
574777935587770531
389225286762721400
384666239984282257
268890626303828807
170890988040242711
60803946348870691
429922877442560001
187334103720017713
35965995692204131
549156378699810030
447353852029597343
144257456155260816
705746493430310351
198325644449611669
61917237719837351
540505449518187221
870935095514492190
39661075792886770
296614490976041536
214858560919537925
58563431059381800
69810440250955716
692609148810952705
625293025620768961
369957826939795397
89603515131863906
74486273697881963
650695999643290000
805822220414198171
569778071568838021
116269949579991161
44099979210002450
639718055487435131
77839985838303306
97657031568752500
13781486154775817
15885971441512767
177417595789331442
59689245533301727
689517252332151781
10000000101000100
166124795893542781
710225394239145823
39076501018503059
336571802269611483
362035286354572941
967789900866212556
21035459878676100
51501516916515393
135916424397312000
248222397156039076
58029800272913551
885745909428281001
924609256973809937
489696946172466501
144922077661319300
97904145555793543
553884068884088281
350375309211882657
875508159599964900
981278188161926671
757196298791872900
40938324211047970
510041715938200260
734635941840425957
167619854416386263
292761972162404197
563759676070380847
322641714459157243
306456655212480167
260320001204665511
617617789711550502
53810951254959377
726577288873490961
27618754593968677
833834574684425356
477293558609534672
272804431976944570
146684274439885376
982885239252852011
307607459139540391
820120446815570289
919136084876085905
833911263133068981
379126526333830145
12937868380052002
751412867921478857
688439466757326199
174950904767215987
36029897638937632
526007548075321144
45848628844507585
839521227603549898
255950879574040711
111675708973230649
563751885896599887
5156280075453807
89215187656058623
429916323842624000
189192878426551860
222199621422344593
257259845175891869
903565246757377661
742707952761851129
954367403932263779
914533013438927448
669680169427841754
930862161807377077
385172077211624881
216242472262951370
547101523001042447
478655404658391713
977299915760377477
995225735045030133
435101752137972193
262630726252456091
430932270637675720
54428601874881307
244854724281346960
439978519997718765
150102271355388462
52599638858950559
83585127821688403
147388491719490113
131723342225293392
555957180320432209
624207823066629360
727234152964099553
832156979751814151
77941562744820337
652502335200208993
83837248627983877
119870803007617279
21035461039241351
577221059340599171
78621382101737162
913517256994511697
544791236097161513
573855074943579529
63015635153839105
387753545273658667
905571637825617439
944940754137438793
308818376406740537
50542150463995015
184978244195904785
61992645273437500
8454607015429970
54243496716842890
791403719371845157
4933486356365962
746310481262076431
879964014639275123
34807683228046876
34050637223975070
122556523775625
521739869714252017
53852277785135160
768069333897729318
885094137668016491
291197775514183271
23762680014087498
843389492347716562
27612602094308029
86109007582193133
73479893648062500
846313664824972291
60515844918967609
260320001204672906
936925959931475117
991430609697439396
212944325618388101
95167951429971421
389335277067020407
477639434616695831
27197368198567292
745109942892067153
725228765068717806
601406519510277119
409224441326108257
47441812395011201
95167954136755654
430932269981123841
26957629728332944
169663995320798059
76366721239601143
465471303180488261
310771744346756097
632327214671094937
220829196884382913
376038049507012044
21720071208081482
565577955601787242
769271164302211447
52075135856656969
950917188275186001
664507305239580626
131723266037863680
469164888623406221
990597799952388569
709688303215140002
12484139265678025
233276513445284083
27211728439854992
714275414761584391
86220825667368000
144555126107182389
50818840029731639
231649381141546960
61041273087898362
145767941360160
541501668509131969
110417009619302501
707754881183117777
511263626646029883
178188409086802252
21030633069950725
134217728041478400
517816322762206536
42408787643923601
775343325438008731
984930292890230464
418452567795400547
135379424476248372
894417491494263361
840306542830360549
161845717324240489
207993911927678521
630349614171468801
177921231758442728
407145630172927807
464645372833980100
630319986365369470
55826577363955225
10001000001000100
422071077063792
174888667667251676
652022603524055557
144401061250105409
166680123149830738
96011019916458951
83655525536789851
504675802397712779
929808298423411308
957535436492974267
775535842761857539
474398916460127842
396510735737001553
467634483793904099
119871046095066558
790359332751552060
842342213949451278
324274550046144673
659128522275246377
456258975856894152
213518766462266282
155468553333720064
419699265538561641
150495297200341573
644706395938995991
717774997983425676
312135544274197649
308721658554096760
520471253076361056
201575266011316236
182726208717604709
910047728270387307
35973440504092491
75098034700031251
813918182373590529
142244023540726277
75609134157235953
95402692853415097
282835690097259737
84805292972204773
76861360357572865
186130923633911527
96551409300959375
964813254095717527
101290201639999447
810154712886972757
134334940923127157
328846193309029873
655299902513545444
15891344583948253
240808362618943169
28307361911334725
839521227603546055
213611978352334082
20566460654082883
61992651611344376
34824506657205195
25590255807415662
586777214299831019
519964247389009817
121388154866516077
550329231220697207
758872852652750310
486075467232751183
997186416329813473
66553870273415425
27482765698615824
134238699520006401
316519254665822296
75098215051599450
340534293125489479
349244087706281670
439849350469738366
15885909910201086
177921231827736032
196643570982718309
996385049497527707
316519249448480409
517239565856758579
713346054405945665
728858852869274556
569619271802262565
66552726261842699
210906184946381046
573059657405160018
70188843638072879
481680962533306449
405339123626350145
231308512409230096
516485570667852331
59608459473063150
156462008885678522
31087101750363204
538682083597474963
630250152554318401
52721041291854409
600510121712794061
100487703392515189
36029931965154337
526007555107823136
609072429476786550
980967335771516352
36029896530592800
29296540985918653
134238961664512080
914274336763055845
720336709640900537
288826276000631688
939215665267632839
360091022152767409
584568443991788987
962028018946222373
922745635909049602
395704171359076446
670639546618308947
419437117440065641
672829027276573309
122446231365355453
10972047345546682
419437121536064041
27707580294195481
84605289041155728
28179239376626361
166867147057012517
46789942770938731
550329231220697207
361377048198235973
63628235466365262
8991567459663376
177295674433775041
210694507492399141
75358259194482
10001000101000100
122564899293475401
899150158307555813
736716514590650047
586460905737903381
177512437923740250
117949107596342417
374813378602041943
75098034667974451
526051991392099069
692609148726018144
883466522210065579
3117861695649856
850789970582299927
528824532166708517
864003860151563641
27212596478481817
121423271959137357
144576871538804737
998541530171709001
130131630844002021
876288020624502331
183448989482960057
890256411686931911
629101661692781973
519782279963641080
238572164639135105
423626971066406652
366583078259339569
512529047374724711
59604803476578151
549746868724110030
60210926584901
449098547954185709
31093922152735316
97695328443752551
472161969641566481
249629998700172
285582313406008081
408157262163147689
72340237531025681
446590896787562591
95151902871557532
13458723237768906
739000857346395473
261892044441885990
174315050176070522
311685320027204209
240522353495165393
3497102036826301
322975376810776133
307674209575768128
734315102424281253
394579823244187519
35145871141127042
851763895277400643
354867556016204490
243135108596393653
59678046800161995
914530477318963200
737432995885992139
144555126100011380
155568117702177796
493357137375275045
684277376772891113
164421038610878472
188974294285557169
961438431789249561
913517247483650700
27024037129905058
857205382300092899
984930354405293121
202074572277918917
650007652720504302
669883243594062961
498975192979842882
834052674373079493
307388564198408453
818455050713276659
2827473744260026
403545504737039411
768150132182207432
560440821654879362
254944558570941013
75084686279718825
240818563272898269
42441240597500439
668407548671858029
768069333896826151
15881969953124352
820945470193609744
876488343051829272
599067455844464880
12847530394220810
504079589754827424
257362214853492447
171638252826998591
253029995152536030
493500968213883061
894614889767439077
317475840933753841
640713989422162161
760231891626579652
727681251567045323
731238708823237903
466972197662986074
592057484468134807
649148819573918239
116733388271433124
8056082810307856
479977166564605583
620075415635065219
557609954754624763
518527870524285643
590733348109913820
28729637260767057
279323463199071091
196619521837164001
405915187858501261
372980422246731529
49191965399293925
437903157975660240
249296593116781447
348306911878154330
635296755121667653
528435406658760827
498816237957639121
446509650939591401
11088459921985293
427930374307936955
15088971561980626
389771689019052485
46503477495911737
904074752928159829
461361514046327693
161828243163216148
362038876763934473
10000010100010100
23762763939349182
288068150152677636
108256603740003108
713537813252939826
204712549429472391
260319596637430375
947934249246722500
18965689621062971
474646834802915329
346121791439077949
20711988257055876
206635668636529445
71909780961333
66278267122876465
128681626679852387
994064744890997467
833748648064777172
116501362470761441
23697437393678401
131621706079515685
896044953928168039
246280121448701147
14290099628947003
18295873502973953
754037907176555563
18300271532703809
870313526471897765
846687546398292121
459517423768002109
5578180756641180
639376673147472539
642986104195896403
82135041344160001
74845244085652332
857246928030685733
82124801347360400
36063981425688609
99307770905626886
968330033269059347
217185420042380790
383105314734556421
134238964981766480
106205794784105331
754520785290770482
115489530484300037
998828917059718370
293614883162384233
53582008234860762
853140692741554297
46503349395622846
651631318434073495
798082052199454927
391725167071247100
316405412438054280
692609140573175808
717368326730267436
451245767816598529
253380418492432055
182856262823551841
257984263144303025
108239263370748978
317610459956814887
973499422602032789
753243021211516469
210906160151472667
285544159227904894
477349336678064400
786198407690890000
18014398526525440
438029114877317501
899806508321385283
76085995812896250
670541835677369329
490393849209052303
100140632246302210
76803446564250757
884170257025079851
883641421791943999
23048797884891330
198912584036364083
473414920974013639
842343090843910096
819729132099072439
323085204061758180
99240468244324031
156918494414030881
217320975719813657
95151905613945334
740088798954687182
914530481897817625
538386983054507890
131621706079563601
482697351959361863
786296104302966529
260354389364958565
792954515779223951
86231041280000020
186168982285569036
169688927575253258
546407394085532513
383066018795822147
91978365954774697
96551475426044136
876551741854286425
555574292060082648
419699265641024000
59625866113925099
945901310730654869
659860044108654601
833748647973481548
81078802135099610
85494691874325762
510041690002709723
200798788725091063
93785544201386351
3092343531016336
695337953842253801
113303246136581101
217557445379677833
116117925102361499
401049444125914609
330545394317308302
87769863437456357
386474584619244151
119088192124109106
96387641905498868
685592901856896001
901450511581665530
91752853217610271
243904041060898783
27197361103419628
303200696645847012
866273956873901647
781579439377978217
84605289074951180
632306887907859277
843178351415955547
842255401487412529
57741749501716901
36688792869203345
579155346712495845
565690078668044131
531441678699810930
66278266868074753
752100963189176177
472217154609134940
188334687142799321
603188121737933822
128981839286418331
54988321019916769
64485587085015626
11335013840504485
59604651133203750
573059649988875388
787079985427655940
972472654633229929
1717721719950242
828124128113112071
344705547743811781
876580381578454393
271499085750114823
493818380030681383
411088989399999641
18300272623222849
234374286444138211
802146636193258133
23101310134295952
727112217054201553
569696504261561909
42440795099583351
310752859644055621
169663691268921100
382642854401592976
504036440401937086
236812756230255379
149536083344887849
42440804569307525
360126496838285031
80147295303159552
85406729144855711
914170319145031937
770454425579778031
29068523201644096
763655000494643743
948438877961045022
581967130299895279
685193275289852463
257383955676559953
187291695982119193
245019828977963601
1523116680901256
175768336289549026
78511895977266049
4867595242799562
692534786736006240
253378924250109900
437322551865850999
820848985749358723
166736797779105302
630249417462418845
518456437295973673
302261603142923959
256508250288075660
46088081823141151
679045600119541824
288826704642615921
167530821090153375
106868923837474110
579090491692102511
52121504723837803
345956268818503729
912533272135373476
942639434822602679
556102098461103690
925736415010286587
554891453199303763
288863996437962087
956200475341981445
968941002822264082
212487391340483507
38084594661646009
46143249316800805
154472377739323645
769890207187640543
5287195891890301
905674408424978771
584130786709354543
293097960970817
564224840920840691
108307553489479667
15963628719687771
1930983645675681
383093289027440661
199909150380464121
366428896225028142
784626521697395747
96603497612905025
32192865377655912
45848500744218695
188473267252471320
6422897163137421
75098034699615001
551776821803508180
715594844391705664
152643216342251910
550329036582279486
139368369473721413
18585304089101113
170403458322517913
837056917446973609
353779627641225362
279865659349216250
150300530303299471
29038483109664673
418794285713364756
163994408941459593
883027283536244857
919518645588876453
549176061699027930
578205927467755025
937569793764311887
740542264330710067
11309174587227609
86989270613058661
699748674457936992
801226471439475762
246735079503277919
801795706170129133
454288117759925171
188614890476491122
1833239501158231
793996214029118755
152753811559467803
527349308354933820
81861358198047037
344721598797074857
189095453088354817
20716890484950726
618954778753733407
3675056406973292
23987333500010257
336996801827541403
641158670346517122
625097004075291757
300917448167041691
818211744844247357
287188526508969960
991574933894432159
67223133083223050
66305846849681713
121376589352629157
189219687490288474
99245898069256458
18018866366251073
715821791133000484
50968130012813977
253295189808931931
223767260866056881
855167150989613591
324031842782341
183739985254674467
669039444385332019
652502421924890644
472217148019098397
128518073867424800
909544664134399231
6280201996923350
171119981081913590
283750016283506051
162164848285749249
597116217915014753
760312690000490310
440658421605618852
166134209370290107
518091898752148081
412666913630849359
571573271738787550
620940374417292301
24128259706319869
505394814618408793
319536480779060820
22595819160865189
186940582208492532
257362614661127844
681152846550824025
178250668366905738
45938319820030225
182856170459275278
161611752732675031
4063289950467540
285544159227238735
498258309135147079
202674060487702881
713346054405718623
96403481971232590
943840095325311407
174949730056076149
78087900019546213
886015049189126887
276224009780859313
38216055076111442
131452962275580626
788483265854101506
150094635698769247
717784905685723597
158978339749253521
178899424315040827
25489803961530757
97867745010327681
201606311626043329
581538987001819037
530310485760285751
162129587810107912
16217381587401769
842351450255945897
87867456929198117
34824506845923000
493513890605170931
64925649182195761
576448823795510631
87738372543126191
374877834387457411
991612856888135219
960710919380145780
467086816417644225
922838851952770500
881036369078661377
9991417242383930
303877960471607824
279427123356125557
625359657705734113
420323506485611221
665072448776226822
86231577603360021
78507862829749019
66306434178136320
231617323485533585
768150132181304168
33183490637306406
529952675446792463
159672464196757451
17218752566639780
167530822468560811
51891378288048367
816572041372362565
201682259685743628
519926579556904201
225630661085509681
989365414465428037
327607091206318519
723185307480359703
734591003398396297
296779839848801297
279651513426714497
231616946336017961
794657028484411529
692534003979101185
260319596583365614
46494384154213177
926682528307763610
629977142790179031
51998837128671816
81920537600008020
411190639909334491
35965994128501221
951407814543454092
642213535457912491
618988435084452622
922887888345232682
379338709103084849
813098553227735167
285544154300985361
758410199943647503
942585681559444477
101651375203984384
288826704585326247
985182387635134080
30111841323386682
734864873401869336
505032402763094037
690061577891701402
238819773614301901
969519792424602841
96545009335825
10100010101010000
406757682153253903
870017548410119041
658139695891770930
187342726067892540
690706744026783749
79792944526449651
253378896057034275
232525040810961920
186177836901620892
59689247605984303
154473173820449505
31093824760562945
108256826089438416
240818928080454108
266634437711764329
389607368007627133
75098215051593750
481998207682723557
97657046875000000
755097095092032901
994932303806650243
208663501754417173
841208940487233691
572114255609610757
26270612916894317
451289620273223293
99388774080435386
232514462338434753
225198096851222641
12447809784481009
928323948720954101
154823487428537488
57575407074235859
162451193870680649
760231058654565218
7929754232443056
424071023908823591
206764738302210617
18300340269223936
147200459216677067
664666848280905756
652363373624949775
527265459319038773
535183619178058507
234151374090157163
81091530119538461
838944297517950625
885808689527174327
781847850285662449
416351635203320711
46990912258291061
186940255314998724
525952869385288345
67451923221458322
64658276952366642
889207415560113131
27618754614420561
316507208802190757
150636389191565687
175595688209297664
40938441859704970
95167954137212188
437615130475146756
342187442860474202
992243377915711321
884475361365001009
794097771385687171
343872357101076211
967725513656385650
35459642129992291
76843841437565185
853054793436563738
82648438804730723
37155831870914561
720842891553254471
478488974100339793
946048223838560712
280709119548351342
158430731160873761
847625516300612671
176137389071624253
108256603777486632
939494492622897461
214736825645062380
469363179760023943
878012666201935897
64614334171282506
433250515064971399
196579476579784122
4821763957961006
80869093254420929
109947173482391730
80637966440126001
43147530475586732
269949641653105523
135382321714749697
285581884764682438
76099344201568201
228890912102933683
73218185852093539
604661760013179660
32467545880901
82125338880008401
274134135180287412
24921234774722882
53742591632157267
27206626205107542
21617587711048850
99609390631375050
648948494409048731
258871099500840361
167473837931190645
67439771941190701
241693671091337287
430185021442560000
412433073989317561
936994447106159353
23768217828738505
6371770956920502
31551086846636693
871332884793813989
45857595864377086
262786439443862699
411518829529107557
472217148019098396
996292587611207757
985178510201317509
308820133791665216
295260405800305741
51998697841102848
121423272304162660
822382360491960913
790080064518139379
840126305683286927
749867326203821911
750815162046728101
921062598519213461
186275176193793024
950769343503886381
991215335968886513
754053907268975077
372595139956689807
438231904375611731
271813162963213471
209505748757562420
92975452182509527
455592262519096921
368384793412460500
259093871575382693
529842359515080457
86221338883368001
914595990520787293
992700313463114131
567264319831674257
169688923822091282
975518552899175069
547516065756534510
55349538117545450
112034138170722683
136496885189437351
571611155618567183
123334091951842982
364907901722956667
431380889723789329
180630820280132447
599682500701466239
81454605178812201
713534670496481224
839521284389005240
25985461439604422
99780861276238927
664928332316929157
526945304359862351
784780315296744139
166086536643380869
472161369878159148
330832253095965857
330627036653136441
508764376878829681
650435551844445481
150117794562037365
267489617547721441
12352528937550692
923774420589708493
947064086741854015
842840406509613023
131256867834895379
2572065591767297
276860334254762442
316440306353863713
980513305938365807
973448657262276721
309914686498817327
550656613155022205
717378239790831780
794411479906214983
396480867131249290
573059650066110864
245529277597482991
857174294999578084
691199009822780119
325366702821351671
719919333262284109
398249893931089225
584315580141169777
390345651210743362
212741145233648029
294396429629522773
308969678297168100
951419780736695557
720161316908529721
852143556179331293
119710614224575090
79792280144784053
316152160446195331
525992494601961120
135379422239045184
378201853746861371
282909234764584129
27212596478481751
166794729044385889
717784905819524802
119089089527889106
810209471213667947
2893449626732026
72057594307481600
27612693882659694
917708430009717397
430178308201024040
83697182475364543
374877647046139230
387562965246928223
845318128773950083
355742810674587899
31544265011716945
51404690412300626
7355827511386641
81920026947200000
3420138709730304
232536924545901450
650139741995216843
270330542157229289
477819421222932390
362033365753341747
648615985906286813
961032124319912269
884141799388693609
200291342386987165
843273323882514422
531441021894327030
137070596103424833
360588429191548932
240522353511739180
910158832924694473
336603980372144942
839302945214333418
797649471643231469
976612510004962601
456370800595823961
305939684540713609
747233616454198429
859293223734374209
584657414142602557
228456977547023290
458118599012268100
289694688551083692
67901680510681081
290613830221329343
859337404176838849
752532553137863803
548446292504845203
579091188900923696
281295294250892945
467086818980581891
18672137514760900
391725161165618191
4974359871256165
200407937943850128
879553484909605039
804241638814196821
964090613184094679
47454472112544676
407023983634081970
313122411810922981
90978400419961341
731360114378274307
117041808017763961
735975238373760065
108089613611482802
826274349680995823
160573373982600463
486523822117416521
520411089946175436
867839331698891970
84605481741084304
52731071877989953
626055473732327827
128122010518380779
842017648445160283
715193878388091391
208215748531522453
324697337333551204
51313866936563449
10000000101010101
318747901981062353
27815490034241537
869373362167761631
399575848581472093
436451269731970579
178282523180188565
677562419784782101
507129067823392352
580157324046032597
1748904746948372
295728043040483951
616234347030444162
31544363879199569
67439771940780001
642239340048026309
184598378922518593
407387488565393129
947334597634255952
37479825706181970
244844898647258117
951407814399943999
325019636911354225
336529033171399687
141030712315110763
162416018107404872
148108653355028323
469889998972600429
505484715793370929
429922881536064001
839299422683590473
24526797498643233
42325526830134282
497635919743237741
752879876165234064
18484193412731983
419794696707248243
547282845674991301
60896985093152081
908128185335741171
724271082230850799
260354793987530573
38204471650768165
633058796431060661
312424506836425650
752837226506648761
419436953600000000
382795636967497636
270949953509416591
563751695776506805
313311067941803190
2034721830467882
98265276724382881
186275254390265071
52073729410125193
209568270198381053
1421714533696900
227724441596001101
444384107603495157
320075196818304577
19723146707252642
9154478886679682
9947509945520317
461697807851759959
565285979480943569
340108260839640226
763331147612532077
121368947880479682
835750026043547905
720563188155926531
96052109660555351
238572167729308101
568439300153161097
136163553122968140
189220010539072548
43362994736549257
954324553480690817
35385567170338842
634090977478617089
337464401717760770
743685719094575617
914530477311000577
200797958385941905
970653689412003559
478331307533385001
535341901292878752
611380656829890301
155572167267350218
902988550485190457
52652421424472871
822317566611156529
390713168757315893
66305859085578288
979197067830943469
70680090404568351
178051096000583609
656542671808644433
748217216318978563
44697871149482811
37803144668974864
98081960947280047
146652870710657032
600975337897158073
79825499233946452
423110560578223801
320075196818986137
243158768981029225
499202097094562
131621706079563636
820499609491492226
168625151384125329
375937011382529183
197893447370630732
380895412876772653
510007452619952013
811481682143188663
2913430800006
14562089620024772
74103973527146533
200292085434177228
76942432954685091
238737269415043266
998542583914712233
929527224745440001
312021895081900009
52075135817521575
563759870705903886
24128259706315512
342996589541756567
155867212995455530
61448313794391616
18018796573032512
66552562055763223
220208291587717063
65528161258411410
639893312446555806
982505215369345753
10100000101000000
99388774131413761
839299366799253237
602514089754986784
572909295014044789
405445622656712641
481570093597781147
231649385578607226
333683004005631182
597633998205835013
823398184149430399
908758535252475625
469041699845446890
439970408448894226
134217728000006400
10305298879540324
831205312305935162
220850570985392570
234384341653760323
426246839585963269
771240712513761307
257900528712445080
135688534850407010
778093918639638720
692609148726027264
12572455054416713
472217148018328172
17379212837608806
465889265142506059
260354389419659380
144555126107325649
66306433918023984
572994802307531115
240870715714428410
7337823367921216
533249073796097757
45640487050413649
616652129270176511
640027209311625127
87806958518989711
318994792617627131
563380319158222501
824934177735087029
45656669136065123
532051829829027930
322776623742160897
3674976137621171
576020564814314933
477293558609534765
616440711754363456
24128175799749847
235755222553440282
10100000100010101
927718121890931123
134435673431946437
253380418501582626
46494254275464385
725231907811780746
481509613779559373
53718769561400496
471448845970118573
893122075873003683
26248542028504324
60757960729198701
201178255002814099
34051002589569420
1086627504589122
526067078129886595
140630222298483369
579394710002254410
557816435533983409
491548333994403181
854094075963442609
64339461393540025
13728175369118913
715295656108119221
146649081360683016
35459642107325239
655274441369845460
32855192675280197
2989087012759393
253414415292842897
873509502853568753
162195162632230266
282601730347631033
48937041169586762
519643949655625349
58871738042499605
112696448902227481
257985812766207680
5591396486960882
20716890502522501
52730932590789192
4979629581486590
40930088804714970
135895449640966481
272257356120476769
352783419189660931
312089762970484627
363367327017381050
367749811865116522
366030318208287749
891124663540054021
168994846282134889
534583657476852673
151095096769273257
247660018788157806
449299919571221162
488810029346064983
622279848042070991
539538986688805783
546059459291806321
750965637313948057
229155759065772
543046706893269812
97953729012140420
921243674156026279
95575762408876256
376762779322432652
812460972772732541
617406272656159531
788509705505814849
368498212375764307
402943087701548290
140914891314681229
316478846292930112
72339073327435792
534952471359013787
525950989780042054
85718323862411933
66469964112930720
564079267833821249
713534671340850544
247197134902695990
947557230322277923
497094342693426506
664694359886410001
430804244979613399
829947649704253513
7258021247112
99290842444267303
171032860508367107
754458936516745849
878076179657883673
769494943952544079
146406579990958600
52073729410124103
883779819946859923
210694858790423701
242897059771398211
35973442068447588
260354798691793439
13204248691596822
144555125727118912
597746800704516167
958639024725479161
43343373463102848
188536947739188679
358717031611255799
220431455325267937
196313087330428247
564079073076651045
447257503828492801
3765745294768927
23768136427125486
154839374744597487
254369988363461923
8527278129143906
25216983610864969
900077086461808561
376034665732987626
320116059101303961
63137166700294404
121017535369554077
207111104893943891
617434217094760800
256817560481835321
338561017486432453
39638419641436009
31084587910643742
438359929377125537
143411260649788056
519929110389127981
47068920960912900
4990716432742823
429916323942401601
380336641916644057
702561766153249353
555173529410604007
960927538717124063
345693021320761651
511263625930900265
52599132240709731
798849876105179029
1571602969328705
267946161453794401
692609923330089985
888809570769938957
901954165055655626
371933137266096876
483779863837093880
563851228970540671
639999778886720001
929305705814972816
614910263629179661
658142356821010491
130806340821486057
253378896066348305
48498019757252940
419535510142240881
68111093589889837
509624279028605709
257658060499287617
234341856022847501
316478381888843328
260828162128871610
459431931355894331
296533779488468256
52075135857841768
339650276318893109
17244002818198507
144609593749434373
27212596458330630
92762282575426829
76861364634652673
543939377529406681
156875734074403133
34051010889236446
986021775444306187
238741617207180319
353815301296581633
331034291048003173
119088191772318655
165507788897455225
227107677003236649
511266114582381602
43343373463102848
138982946932563889
857932417907220899
235012600024103342
772090230724118797
99610156250125051
734864878890827034
34067452345171920
21030558828922566
299037316072044961
526067718237195844
188209625926388223
835708960300331651
366371837875230626
945780583879953109
91418947250525233
680595569551796023
421275424043542877
168960448820773478
53718769332055488
42440804573784981
237227477207141190
477349336750473921
270557378532749112
599943793147836793
451507857035597231
23768136445812726
287088968719171921
985267177041374113
296275938857113644
7356903829808421
177238431992368037
309944153078219501
64195505326254080
391773528135908101
37609893874684321
664743216086379271
169957593658063
18270125473548149
64925661407480065
297471401609353321
18295874559934464
132822804968009591
249714546816322529
257840917622508953
23762762686724689
177917719277114646
723571631584298603
172154637225468517
308820102960692737
18300271549485120
51584322482843329
130516452927230881
270257672904939323
24981504569442840
625664714997966437
225930165216769925
437903155241859600
74694398077012082
815562899087138249
579668553954745950
260609450785236001
479553822790571256
604664606793600001
331936635887051776
414100847554013591
30296586132190170
64488496194554171
174888645494851188
36520347436056577
179178181241735844
368496256876393863
437895859829318851
66277667569142065
26170763731315633
85718516561901456
35965994128496529
104482324636121306
854189073705539659
2933601043198283
317531829629139129
511999327677286090
750961831440111060
782204603653282490
479921046633482282
615589633930122497
750681086224543321
289895585228048831
121388151788966640
285544587927178800
52720903885455433
829300738749786767
354966888274614529
894260717973740809
405630219679893253
3713388960944306
708875191799522863
360662990648786965
25764509846092901
580569943380175447
113726969724147025
992850521646065952
816034252195534932
707461722559521383
557959240285003961
726393503757460727
952927032189614040
1920076454030329
641442814654266252
944101895019031363
487304463432457483
23031510294895001
103974669059210
224964030663431557
849736328183994443
75098034667974376
288864001480119559
833748648065718462
477224957509662281
323863172744405753
779955956395775952
156874026924362263
886753656802166147
607014533936196359
35973332563586038
202858781327942430
231649381193754811
768068492248951587
803977570413976163
399776248250875457
36029930923917345
566338865209683361
18300272606707713
551434733110591881
26075715150374290
497319815480103911
193249243615519057
373131107091298487
839299365883354951
146688672350109760
231649003992038560
95151697191114642
438359966800976343
13881685772560357
487816808510888281
30616216854834313
180148513629423
354250015430152052
505038246812307599
981360762495925213
45011494745083876
929293745792665264
439812546332302380
985178447677815301
473697988718484797
602310210606069997
37190981916852257
7733203965356406
99854532817389363
238737269337836918
10100000000010101
113842643844525781
27815802220653613
68171965603078690
27212595107900338
79792944520802549
6107263517113361
391725698445908190
33004540089081290
232138353749098639
117211060141137072
108256828940072281
549156356829027900
836452086378182387
924956709190409810
184992062616163153
134219422823255791
176418023080338480
692609140658110464
61988836914453150
994271117610656580
574701221352060100
993047518178493227
79792958367739254
1010101101101010
136543975791956330
494299536496710851
430934477965486504
123535507856900449
97695312818752551
50588560656894184
72340241541828609
169688623523369658
49851987750194570
785256313786085389
234341851586408500
51998697814228993
20171379705090306
159345240433646232
546874654078008457
995615006610153931
155986184579395632
740891974892798353
327186774499014257
277259529130577431
477293552089580140
520938237404262657
27197680381144065
68778498280159050
252988045429415953
59678046800167324
419699101696001640
374881218093562033
221165568391654883
27829531001640017
59689247634766231
135895452876806401
809339314344980513
72058762538586385
649974514694895173
290932186789690001
129986956096027817
504036365341573224
985427097784542057
7591580265605626
154489095447245308
341962871933639056
165679854939916753
144412453155355247
647470234451282899
913099641690379103
153402678168036023
430184857600000040
89894160991840507
768149290533429700
81420694025052151
156508584420475951
178188408668603896
502856491395815002
122976004772027431
885167474324725842
554872558883666173
284279177136454919
792645317613059330
37189881332531201
612152212044055490
604829721600003601
492544466169690007
359205998687693089
935421138869273562
623413776696375845
503976504484476676
98500185151354272
265666263421333447
95151902906710574
344887386004188226
269762626199994842
801709935915214096
440846708172371153
135895711784960080
269370901053982982
620652888269964079
140413977849516492
608785999749947321
473551610148122621
415929081958416889
255334090978059844
325771989950891317
563751890530847885
196439059607421919
526006901085942144
630752030096354521
23768136426833568
596115183914031682
565150658488798453
877206782485018987
573906785102085707
163585906516342116
371547387678317269
304976502934953853
411006608315529907
782008179900869357
257902051138528830
872870269116718079
940865683652900721
223558206662286283
66540413024072625
900401425160388091
321824371965217829
201576003860176284
922838842443840301
477293552018710976
101886974102009491
713346106784762168
532116152384389320
642885782010756709
354236008550417371
648168585687129737
294811268680180281
46864900113150626
40361960079000000
614739456777819601
926324496987633719
500712987667777601
374817137054935572
42440795300971489
853058371866181867
516904980478949353
240818549779355856
135895715020800080
399706851172029463
66579566411417419
44497432098836881
566982441226542841
193349223026738221
23762681285399101
802057480921965133
45857725743478676
850391003506884403
531441656100000031
599922342300777049
316478851510272088
12103397808501693
99648437818750051
339824439856205891
355128478885989461
324706966091433631
200488317359641607
919329446940189481
263080690667900321
210465051342384103
306619504361875601
111832750817949682
646850135273000377
52075091908795462
702722890829773739
111731901916084507
143341776692006641
882229469389515193
725037110134537028
665575775348019941
25021287407197561
226837980405512100
232152877347616513
394618252905855211
604832568393819661
210694858740043776
215928334691723933
549155700000810030
27197680220061165
52075134527274376
604829768268963661
281578784129280577
29212660541757457
167619554162870008
17375049140059811
56073978099505809
27206626205102986
234341856022847501
6495106972227303
51650491102293136
482230442524807799
27829531001640017
148356207039409541
15568160535829226
231617323433340100
775297038584387623
240808362618306561
511263584453173503
230121802588385252
71726246515623844
571578614469898798
52073685539312581
734458207373176357
717434946385595172
277916593074914304
178802164904588671
404485741706468021
308707664297282256
677427285402224390
64953253879679233
488927139424760831
36029897604334593
550031127397856391
16694492908616070
352554260577228599
13478657504412077
18295943296450625
288826709568884433
386279103328785851
174403354833637099
725040252863527208
701228778524570497
36028798126293025
30704369407984130
748222501882085136
182788473377772283
253902642385613371
180544203787354226
182726208786948628
941393840372212053
579946024332348130
503541153513908833
210832544059834842
281882779110182011
325616247016692880
48374477462429479
40930206454053000
27618754593964255
337011550125787681
815424970466921443
1051770377189090
445106932709021951
412906285365793459
154510739668614323
626366996225709383
233044169262601711
41822099803742659
238659114288888169
229685368444140197
166193195777992010
257597847775863643
481150514641069182
81241887127640626
985157124327367490
134217731318278480
842256287329802997
489773554468076990
526006901160755902
145507726017858091
154535433575222401
131624524952221248
281054556769338757
403706868481764
164661345301092201
781046117325146361
399558094485304943
257362210093885398
363136452567399779
18014467229220928
435823686798282697
182729813565084883
200597064103764496
91189075166633521
109369712968457533
66540577200981522
130824291921798872
432691246697973264
178865145851978106
380193256385889425
173701620265494433
15432855248924893
122673754669985689
86371976776882919
253056172989077663
968643046577633783
201584919996186624
467087431671622126
243026840905202069
48696745559383553
86026241283208421
553317120473646321
238576401108002569
533783722280951291
81421372242357749
121388154866029280
672562047502131612
210724020658794385
60016309919547961
99610171881252501
257877959745541592
182859680371179319
135277862284056421
922982043184287480
504095411280442592
614910263616003660
174887492956111838
150094646144793252
84605291577120081
582669039961805131
6806497007241010
190656056182615291
23762763920370025
646496287707769511
387468324594900000
44076266684001740
32090463266618893
779297436907506001
992438441591718163
66306433918021681
862940919873545957
359233152075678901
81420693742692101
400896922639228091
609773576742640003
655483009572703343
18018865292509184
542712985167162431
641030693838761701
177921231825913855
72356661217529857
35452197340437849
789852092753990736
161586251935182353
42801881130684026
166581952063042052
121388151827916721
734855421158440890
379516319797888276
555988281435956568
444415538698038871
553472912829632803
967954407159095407
58871740115565868
135505257753510545
247239241978766743
576927588500915569
853412586306198953
814368385004006479
316105427584993889
58882634106792340
238865106983463641
259443072382618783
380378630263318157
231172871540164400
271464262938978481
15885971457015682
53742085009138464
922837910569651000
170971818343844069
368614428519963359
45848630623320215
469163373088550850
392956436031276571
941831159636099460
350356409354999879
650466116391203647
899555415423088531
625362018424188007
228008698644362527
507303086005755006
6205402471738129
822776671693627307
17365340605753925
42421183506396768
787027012195594042
74825343387106225
226995325160389696
920090085833533697
109041377595511321
51566708418139850
6047534913580733
467919985639531277
333409481485584703
946804528685332533
416903286772793772
198338342806292021
18295874560196608
20730624828382226
429130553905092511
113350748839884870
214738188906018636
83232716216652865
776217734685515989
813465708972970961
14983581489761040
475050944998444817
826828993254269879
144276703190093479
106520748470381429
75084686311359375
35459643671028010
298728771497696164
316691542280503297
354250497851669251
612939887653582147
827457668247588004
71970028020379204
50416544404282657
316478846233642136
58882634107181356
39464943949174593
519403355025191407
713346055250545625
91690103625570271
887784065921445569
913611405009451896
331987626396060461
280734306691413907
97696109381375051
17230920013026802
789733059824530050
75098037041443126
151846592765725272
381423676664255626
346600274876548361
923278440308964101
690868426924797162
537945857369615287
362673958703449231
60052588824349483
317689921301861160
574206748752011791
579260829252453823
947998115801266997
354292992575937453
988208037815971711
81626773330368017
155628861278144366
519929068923313320
343489411821691506
325621599028266763
168627696736205889
312446594296953781
36064015784379425
288937836513301924
82125338944168021
494609714167418273
687771596883721560
877385274843925444
58882636180252950
53718273488148193
70416430600571137
162178482836814465
662491924173151901
32877670585152065
616571919398400613
735479526886135379
208216099829553985
76099341828937576
6150141755242760
230709299574882241
583797303919093321
50867207201810291
244850376489264819
166774359255236290
37189916732458017
843279454901856663
857269908860796369
904523359129304417
99649219068877550
416433986507377837
355597265707573825
13924509764665601
34807691720441251
842256287238497769
68289747959517184
135895715021318400
532032146829837031
28259738522281561
36029897604367360
429916160002625640
859076212855890457
24122720639044435
714771232696480807
54530001074460409
579156036661182474
34051002585559875
353829807848442303
731565081767977049
242451373190662133
142961506693987021
615447021038123541
929436520198490659
712868980305763313
234374290881805460
364143496094813417
602461490574570903
357431991637082569
925935135370603121
537967521604572739
270105431906561567
841182290572773300
260320005854234870
920980402506675299
878218848314546359
774624054010314049
107099611908253670
625117238691054517
31087200639231760
78079190697518522
929305433996284007
243929578802017067
278421948663071957
385639338205790245
274101519322720081
116626737976996
97696093750000001
419430400102400001
214738189365026250
42421183510971606
37304720002082
913517247483640899
43954531149636241
973420617059525419
876554493920626753
37848599214990061
58882634107181357
505826806630020876
368386782616771807
140434670213682
728546086531701707
201682192608600769
608648088998036656
108239260484043001
74082484240674529
52721043226772041
329744208640231037
977021704229266806
255524639086057031
191966468874659827
839656713220686029
169663995275041239
760311856939956003
84590836579874704
856345695359113969
585632632907090207
391773528201518101
904532617482224810
81506515417278140
884316123298724761
719721124424983057
39728133921318977
569529334986769141
67439771941185299
435215119569907477
466050236858820727
983893624213045673
79005454554149011
413503498444036027
139294744960337861
40938441883714970
438032289209172990
951261119035342223
583795539805349587
245267961649076026
902934324791730660
81937681728762971
437241058606833306
42836782075076196
201584120624404573
825603218184196927
178867049823337289
435333415979354132
665961752902651209
308721689395076217
458552630312773273
720003387100262269
499484439801976597
584651190293267161
43898973803951581
373987764128019581
788482439588174496
142969312559061211
391772990790008191
475367538724605229
574075097023534096
710005604550599810
668488517567772571
437622690413810922
396036317204972777
327154502343533077
129676153670927209
550495744793586020
187994125847127113
144609593756745936
121368947919423600
76085993408630626
951591297037222531
349777061991462613
949559944319260489
59689094227468350
731006509227319337
833748657104916826
21908540590336
661929586303664704
778653421033357333
813917329511153378
380847686427948923
439978520158001115
431265710513772883
843679205180169823
787663636708246175
27815802059487376
820886605409945256
23815780924493377
52599639088295567
921176214914063111
376038038453138065
701421316263612409
154823489147740728
247716385848055610
101037748424762
50592514987912201
951043188381082624
188785352782258860
329835471934232892
978418457438588013
214810491326362470
298614691222671900
545963385520812527
636954190678260095
255017508885011890
460897954624252993
110111011000111100
298083897040461299
231649381142161085
563759675954457405
24122804545614456
692534778668089440
999729050355914257
31911498601858404
338050339704373157
13180323485636443
76099344201990076
21035535315687751
95214896880468545
6665728774883311
354293495141279942
950917181950485463
482559150738780571
617003818342760837
27211728604771260
5855685837323141
108239260521064140
55170314944304401
430806414883576798
759297500569269131
720541682163596216
386897660691917363
620619715536389203
270199926235510787
630319251273478846
983988639589226137
168338672104166353
758613018224662103
688956812445184891
31087100317815569
211694102948562781
573059657405160019
842666669121094303
162411061715145224
767390629269722500
969097702802541043
75084866662505700
169688927529496439
231649381193747500
865641051411293611
941325864199755233
99099510296549282
253378924240956306
600003462852600120
118408583343330191
299381574385702453
926197589825776802
794293971498002747
103267819699906557
877380001295808610
368384827708910998
920816547082478119
837536192667531113
196477774804810
166869366410957370
174751853285955856
612363695454793731
144150930812600896
1247300236511044
178899305725822791
169688923867310182
629263946203020157
418192174426128805
285582313349384478
592131570483980959
308721689945807936
479392490153082479
35209419628521791
731629737032593831
542733490852070400
184893985514238925
1190043215982009
373416092318707344
106869146112885312
84733503080589007
48936760887819756
375204723590705761
139021026639760460
834141050613153529
746159657918377627
402703133131363117
59700170908218750
162129655305076737
1016058118126069
787558978565814007
743442060729138161
10101000101010101
848995372332401501
348097805793457740
652467075404344281
521269447469566084
821488372559401806
589500442977219685
651398785126028402
720564969649415229
79792280427256901
913518198473690899
303403964353530432
579155346712487103
168994720694363399
857687882813474400
178051193565707600
38212687847593623
619595061357106594
2753918915584231
141136964123959669
735483508235536189
195489038816747776
867884617573775491
456195646714559761
595270152483125626
208215748581309589
432632325406701876
787700918893742657
857885655756168900
535514440969674899
709131343059701323
167644786670834656
68310271986188582
135895715020800000
873684192708537763
238741617127891685
922444764809983843
929305699493530259
24122804526644142
593264813955364367
295170720300599027
401056189633738157
705615932499845963
282836675181493973
191387879227147861
379930786044412963
547261542909390571
387874026096618463
4977252974023202
298219415403766693
154839337011773569
124583467259594099
838633209353256101
507616234651070643
111889706430277417
943013984252384237
386531286937656281
3241061904605625
3976329461666592
603303971915790917
12518736349091282
231108721261003919
732239270406400
35729306654856677
201575947535311261
122872752078813703
791661156773023373
81217170383691433
127707247042672557
391725161165610091
152156092405809258
20711914016031940
42440795095105848
799123193966269860
178188409094543856
210832519724243118
138330909532963226
419437121638464040
813373742909501317
185797581898498081
382000355263050869
246081040810244721
223390697245504631
947155770667466861
372305134664334401
214810490867200362
95151697155955671
503873042101223256
477410220038232307
2688544711838863
29871207164971723
782073996585824052
170841390228266783
97780584864632311
2473233878629543
1180582421396420
395640101274275016
793919371594870841
411172280184768077
95020566431245782
298522956603593755
33646356340413193
672055907252615760
205061033742745657
234140049887560805
375973967791919935
125652886835284590
43522597160039689
183397066445696503
991185155461483684
419430404201025641
18742838834542145
25966758666782025
81421372242357749
937809279633979663
213426408788464482
147843841795596493
978616210323503893
11962123152934572
83329245111478862
276850697439953296
676913234314805809
340549668228233287
884574534378705303
35973332563590729
639971293524349479
67451756795556224
904715878776498369
372558854661864030
7832534884090490
162165389432750657
213340462651012490
61084247779132452
39327667787018163
84751595959969
889781033905812187
75098037041443201
10060706754152550
847542775136627497
194390854080561077
426908592143963981
308723386189840441
357631842296972501
454255823660542381
942487951993704031
329659480529318417
476370230279619857
699657169447124641
174791980517072173
438231865650562418
366450507945299492
262416786704472977
604925073133719850
769917981294788210
101708905993763906
138571340809448089
432632893343766935
178250690949313483
48776191944010519
257984263153620025
196055026503333359
91047836526201
829634629358036219
282811267760049007
76085817834380700
1646953875399721
353829290946975542
46494384154213177
390103830255455689
162831257825743810
20716890484950790
1414623691070772
850723924155470999
389507358864270931
626211101217040145
24663596566297442
167644482709926776
129602837801084651
52720901977784905
164662862600737281
97065960342351026
467512718427787693
353066252483156533
549765895599000000
388892623118915922
677534848760627551
477444110986516250
213554614817491507
342481244018298842
207307240107919933
296250586084761088
715280344168035361
703536859374432323
550337211511607685
439979062757418479
66277667824054321
97657047193877501
661282676979277141
662089929874991417
364796037674566724
816485370801566303
595459946551762656
519926622452358602
819645239808582221
273078421896121973
27206535766575732
34067444045598046
145696375796987641
111036292728522661
60094462639416680
238062702804444257
16221871627407433
524879340124816571
15378966595077483
699756348935989620
813072141088606144
180891520404355819
921463884137447731
156738839133296081
118552208504621011
151970532321884166
474587065264844233
257984263153450681
335035153312035619
812257382145494867
759461045880537507
752154172235923757
694166844969897049
418364841048385549
41421152885647937
697906132990889033
240807971323379712
626428156662153253
889609105607608157
505032481222382881
800235607099798369
999765983793083063
295188233870930483
755077918835139197
465121488170884913
687717371678766811
11546731438351242
944809415116853849
31550987979154001
647894637491145761
869068990048735205
4347637329531456
146684265713897480
526007548150939443
324569860269304813
167000899167593019
99277943723937857
445145505799177280
496383440025163717
575097041725453069
240229319053356053
909806358601255399
974013941428980451
33807852002490573
760231900214823076
424850841977406392
64925074593939505
878449816149232369
121423271959137358
72339137734115328
549746846100810901
18020477743179130
86426738954078251
104610218954535930
200291285632658701
705852608084671453
905219961398240633
76861433623613697
803109023670385301
214738188906018637
159493535826150725
284251669302078469
283177908795282953
147335031610616721
326360442503080062
50542150463960167
2009340421994890
20569582737047693
512300674275078800
985178448654498883
70286784288552852
115825712871205891
86299652512400625
432632899515513425
665458374374028119
867287243486965799
210273286058591663
156121166453553313
568349050637619463
607721836347130123
250529502921132311
296049658045404877
3003998473666281
186177160573279645
100111100101100010
168994727694253191
967689945242891912
853340078845437721
579091188901754281
285544587869238106
261608158393126050
635134759228370352
51197693170010256
52008867768549961
46494382375753418
99674709103242290
628723491017183017
525516785444873771
72357833996239120
2019782299093553
169688623522824933
979477804697810437
307103023426637825
984930292874481409
100364774182575509
92851901294493901
225008814753234541
260801398290584147
572542928589892225
268878463815156901
357628822080094401
936941240731434252
799870107398224817
82734510490861330
73456089756003683
753517745306135521
717784911305372527
233098859411604931
314849767717595271
234373913732296975
54380274374962010
61791313169180810
900724214782087057
699061124768155009
18018796556255296
425571615131684005
378390330786989380
454316816353582583
415495647809081423
559006628096652733
469706455127687570
65973635186915556
898946977444884736
53098233664744397
303403934053448312
36838504738318841
662247687975012442
406797994578337409
330798823394866303
6024272950116100
255471287837688976
161108500134915522
325825112608797478
275943353698550343
260115337966111369
5487879587890176
842255401487412529
222746763161076071
574492511457354421
1694971486866179
522887112533470232
147389519410991313
605851957248620551
50468467187534400
179384133685138429
76099163850005626
387468856035908101
204942718100319911
608384506178644625
121387908740461121
778375320342703921
793406207628869694
813097727849311838
256684368758715900
514235274240240827
391205919568780969
177921231758444096
19716854974724962
325830461009149279
286106885103219343
304256648531513522
58882785441402390
597934087720432303
260320005854234785
459149392518119425
108204885628464649
16801686080057124
622606184931948362
538797772303276477
162446315744170504
438359929388637144
364985305548670321
988908313311783119
744772188880446481
345245471165061185
92625963632929322
487121780891428453
419437121536065640
86220826880000001
672229054670270311
84338362022464
950905228105870049
745506080717763600
852094820943111293
59194536902701391
152810259516264121
697889543026350287
992526584405744941
600953277132007567
45825321290780191
88743098007425567
369648927013671876
936412373603879377
252119528707172333
108860696243125429
73914600250525609
432632899516266996
289158024142234806
714444815647120223
533064210818263761
428189437076687213
383098404943667533
245019826046263866
840638674807965197
453823289418087119
45370023683774410
357743103283671901
72315724225535281
325621732738216239
419430567938560041
50588561948397000
81420693742694552
709837000205563589
430806452963585838
82135065664160021
878681982433226690
955691326261547597
58645526209171457
69729563983937161
368392122533407013
100476293139721849
305279828775313061
549516082144890457
511927153938860861
930531785242329270
945675063352194611
119042441430798654
768149299120760548
51797042187022860
253380419004870081
777066520529016523
813072114493079138
996351174403905121
198551144925497327
9843133847579761
115570417344787883
860531146382224697
458896311206280741
27612692532534588
779523393895285231
769418810897335370
274611736264040471
804461732794178557
295665060514131990
5713064485338673
178187234375513484
91807389259064965
97656250312500050
50542149132170917
66552726261848100
799013156567455482
813097727849312798
121387908702010320
188840304675856812
763005739187852627
10101010001010001
115088223722381810
37189882405224449
147389499640238336
186967722245409253
466116743525030113
27465811084559377
286679193981350827
178304017268184212
123659786448640639
330665797785899503
469171410142691265
427793684339053322
604661806656003660
27730791441819905
541324285166089490
248410892819481241
28356364611690843
665836845353757170
700285956031640900
346411414548274381
34964290563571057
37155831871963137
21035461057092040
186967718306361804
190434237802921226
757303926022987661
437140373656224803
731850541352991132
901871371004737226
27212686936563224
169663695021524985
295280710958266967
619691522124864529
10001010001010001
178318811070391751
900402994199532151
737047998958854659
66552564304345723
62903647378746020
515733880725560561
245240550229368427
931130163987748687
178318811482155195
177917719346409282
561696631300028671
333572208380866817
250876302062411761
906854687762976019
533182580300958006
76099163818365000
929211763732990864
243068028443563501
58871738070897773
990351523233472693
459037224547009237
830860947002294823
418700706920131689
2052100745018939
21030557668636165
32499162697883323
58882787514479311
45848502548095175
245015481183740006
570182234516583949
322160822545718159
723638710438299031
562849440253589776
562469768656203870
21945630702033506
454085828341686839
257362214852863786
709556794191171364
447312808132675951
4852766936534417
839302944283182017
166797270528114700
19837780928922307
677906226268283213
335125721305461193
958445940201373229
119851599099124159
562615943559321527
506877989069017806
699823827273646081
99388838418188725
460161344690919301
395704182957238656
492849560150970050
768310170884398969
665439917935552409
18018865292247041
763497748616953907
198548883191003536
637368266124977077
7958451665913871
579090491692111346
331842256790393483
691344640063279607
366010195132892437
58871740144353053
290423019965200607
210061610378595370
546981955115247133
739334282056961273
48197607647555760
119089106779281756
56463965618797101
155023163676365910
168960456182731734
231616946335403750
825719413399254079
677419170880848401
244238612665710961
325621595507208079
806780505292771322
238576398097066185
717775228656561852
611592392992997359
81453912831856902
913611405104541100
218526517561452313
186168982324139869
253295162119310081
214710579015075442
1884339197368576
733347206973449721
774281716809959993
35566035908032813
38362222713445225
734448524724365766
244854612876702234
181278470294160931
52720901950911048
909080837510830757
725037057769789564
80140926144552817
195825708093384196
99493413205682
821597967279849787
37189916765979680
414994871185808603
846244426948837949
320338395163795991
451958315006680950
186560081569928197
525992412886429704
435383739420045833
500706491114462731
259565702035933067
294141436633616725
382548362677687867
160397269893342120
753140773918490897
361796167520986291
89892757066400472
714279981229644770
396861013762352424
868828598048921999
35452089399936157
189167454745690202
713346105926323686
9869801373571877
393922946071394533
550337016760159525
652054748792534473
438359967457134635
178051193498237768
40361961783710071
135916683264006401
123541470528828217
526067725120070043
244014585567348133
61992651611734376
46124632555698060
540218174957022431
4236938000998757
468027686067740100
243304516724737591
99240476288472559
506523067834895743
35459643694018948
733553069930651257
417399890545580256
59689096272147030
994915184609202127
988490337716114419
82227382647052499
334207172246740931
922612497230872199
34824132987843150
608537262001096273
495860142058890625
288864435106312999
67439771971171801
214810466072446531
125244658270507620
26485726305612
260319601286999648
519779749131417182
178282530155945734
656756328886968109
24128258435008267
45848630622962375
164662931185991689
118028102787617672
283395640829096928
646608684212444069
678135994207416900
129466629490345940
2292387868237657
521206127266498830
81453912831859254
676392222822512047
131624527189423140
352706827516605082
659952824952700219
766437049899565867
234373909242429100
911338363908780707
675271692062891753
109811434886889140
971460097614816169
986742706648482169
943309174279745958
763072520949781267
728659774788508903
18434966690876159
81445708661819971
713997495514875625
781099756317769591
316519254726480960
75098212678552575
353815284067949013
325830327299142043
338408009318170090
483518541958380737
99099301469924107
512640574612035985
615679703547872939
12247963523097383
56920082689536853
138113136624234565
214500028933532791
590018776980376349
520471900066535856
111115260594295807
65221409714249809
231649385630800626
442087519941700753
214736825177236891
114299755845135962
602715596025760000
546370622812090130
171728122901506517
108044148865687204
209827401035628133
856273537671394531
549746211870837930
36029896530591745
51998837128677000
229319223227672556
186275914006325196
187275447270814073
549176039854137000
674457629504536499
121387911818016799
225153458138184881
531461339125110900
925617523804593271
4303585994967006
290823749970354441
240788399310549007
880345198794032751
17178012709064569
513685198819463773
556413895346400737
785256037094250577
898663882983703281
810000120600004489
455727582841729
11003560735315103
184151889174325284
401525906803596962
43024765557774401
636614465963006460
939933842970433610
850903043954802049
894415330487709582
210724020708581604
798016328591797463
462730295522038041
1959128539057936
790663924176644813
691890758387883811
15882032476380483
43343373467580305
393638489364676649
338999841754314049
743190575401802107
532121989125283937
168994839306377466
53742074229925297
10100000101000101
309665924997867079
387468324660518191
589598839598377459
591814054477299289
6410992139682271
8223059267458310
925008649124565678
520411090020989286
92728627288713781
726563681302928402
150094635297537204
122089452605499133
34051002589660546
466242487619385839
904341184040071050
913517247580680601
71937067299415632
130070125855526682
558817169172349158
211991038353698871
871161467204149343
620887940862844891
68048203068855026
720565107565486236
179431425806118047
29076693381502131
135277942885470324
147336059682319300
354379448018537429
768069325221859877
903009444160581341
246453646915039273
52731073812907584
27618664156038459
82135040000160000
526943514778380001
673503356313432028
45848502523041405
214738164570269449
636883614038357376
345630168454917612
64998359054278807
47272408921818291
825678044895494961
462472173693563899
489472820666474371
117482565332260804
79792958650214552
15885909910201086
525992416432575386
480352336709224363
764428371954570053
172618974374782459
630250152554318496
332135912083650922
767147971770370711
541631150263466657
208834433322152873
316519713852559361
724763272036117320
293648370802515720
561429781396963019
66552728481254472
451005969562570381
238737266404106844
864748004636874067
273979369560560309
883707549527476423
833835460619043037
675482087498471930
551399896812677088
271195268408693719
674798796234882217
320074732354929728
735113581515134851
164421518592315401
66277680059953200
808807094137156
147825125702230681
140572860708795150
415140559183191953
150094917727086753
64953840693217585
85718516528533580
1949398132656121
72313938430333352
366450525195883082
301521234714165943
10100010101000001
101579093779851010
53646383270038322
724544901982255897
311774766470466602
505481862674891795
878076069383504449
310766315457478657
214736825177233920
569978670751719202
546718890465935221
308721689935973440
978443829958768363
911986710722684507
59678046800556413
244850379500199759
60688556779076101
770930844991814713
94230636768548282
872805178243863613
27144719490713249
478364335486182253
604829722377600060
268727459097039850
9742010472098977
720842891553283031
189220014477541488
667690583662772057
33163627602948391
576763740507136900
951419509068593093
245899284214464241
15885972433703233
89591830237275136
43343373673545396
296275938743499023
15812637719352721
40361960079347901
27212685586438050
524680410145979745
944017207512939037
221962153497802620
23600171302958257
392110164604683021
166892802267774025
950905221931515442
552064432918736641
59700012217187500
59544805065531807
796381304485478827
866215634325964782
221575488715137192
943209627988438579
720866062379555288
707720869231290139
944576748485283299
151950515041322290
470402809179212
353829790619077171
101110010100001111
842746566519351437
72075186493456640
657898517294414758
572994802306700530
210694511674511509
135280683452751732
9758125879497731
256051245500939160
176501802668199551
360031892343750150
23768136426833569
218261755865590033
146651711574985807
208245261798084756
46494384179977728
879524717824933473
288826275942675943
877470824675820883
177310770705624671
36567511407757619
826000259293142093
672461249654761063
293053797633922957
717378009382263853
182726208788824158
760231067241905571
549839573148373351
908090608727901917
18018866349211713
167409155491562
756847157122336900
151950200843843721
479212809351936257
636884349130248096
52730934525706753
66278254892286001
314285446222023912
918696694375579331
300762678393547633
84352602204252830
8773318525674031
76085817834380700
131035713950988025
852843356464307947
497523096816716513
432242991609283449
816034265316687312
51264107678324161
39825939569576251
125878292111169482
164235579751835551
21660076484335130
257985785085570081
765808102946181376
725569520017868593
283395638334750194
346936194010358404
14907262892566507
350356403708198099
869496702501992971
15314129346890669
545948233987843801
107474090685570156
213320946504715429
472217754302460445
232218265089212444
147389500020583028
549628165127406851
614739503446776000
27618662785456912
186967395305035884
805035883291450561
125101238871006225
519929068923515158
40722475585187237
279588132727205482
611259743052409380
780926843106985637
3273647712424201
432684001577204196
903149767227539417
721441042415387981
552105209358944543
67451921002457175
421551843462858883
265091027827497482
744155370340448430
39059932169760307
134217993462272001
66540577230568277
6094574761078807
376606466711895973
195227400022748921
913610454018431697
276717700747171045
99309958494242510
53718273722375042
849266402555288209
841759697084851631
869102690271535607
752387515961715823
176447045736481129
58233533238011252
351409884355520850
334757424774215249
540222882467075040
222686860193790697
566265772927537256
768150132093678150
984930291881790913
620728364044985653
83911441659343219
416863203246210249
27815482781761005
253380418995716431
8086753460198885
179844622043156311
208245613046329152
186168239316016285
627445691418336509
175663872784942891
855908353219809037
31395655317797131
660683040573287867
88178532684595363
10188413023153562
427930368068377357
287025160720851617
504989250011815630
53742580618818910
438231866295602632
351738775090758551
632453445535775243
322599779969506381
108239260520583582
187058445328021037
186840435964186625
95677525214312083
895606457992707481
166464866593127845
119761447952548900
770854888428846662
581347836428128051
493235681285530404
80348407888495883
143700669891578945
912839542758818690
156422576050899103
234374290881805460
158119619838486085
262983942144160000
415250160772465830
379781281648546881
258415604809380037
458036737718489309
913008690488231448
208245613045743589
174736687784326153
21035461038966725
480656518159088737
164662939777798665
250815967218166507
234373909242429100
22370487460525893
66540410775084974
362144795522698557
85992777689323889
117323848487902169
27024127183012890
149163263910529651
151377965074143369
8290478722868356
42206951569323026
161828896039618421
18014468319739969
693374514559091297
623191153149837179
300171040971881791
134238964982272081
472901523366850693
214199523458193193
63670654483219810
926449115643871861
52413818246194092
456592014343224139
895996465887097302
745931323453512919
828959128746665941
854186027745298789
30973930802556763
380792500134048671
189398133812393923
1829107854292971
874450264424286571
987679925272903663
99299831616721691
9485884199414016
186878726669057285
238741728611771655
292852859264092533
94915720863770402
257813334370336067
56836347537255001
60480010252465589
278229313789643429
897576724780857081
140650756929304281
429922877440065641
163075586076349490
58871588810132166
354979507835457056
2660108326232645
239560105544185061
510038860699310602
288231823577793861
1268620304713973
972696160805079869
441700092644344949
150300808872999598
67439605545269776
111000110100100110
707285607005502121
122745200978412544
575610557776220117
91881106675754729
537586539957217909
878574497249333353
478579781041462881
10208685527041601
116238189004140062
701616608370390761
420134519397021871
755823269259378962
14757082814242757
517085128171364446
115264354931048071
466778450427142633
619550600180429323
135379500663630096
95429173532438981
760231058654565218
939365948898233981
66306434178025728
914423828977520207
561857096010497923
150094952642269171
768149299120770054
901548067060363837
35965995715194931
61191166629089772
114706361442092176
66277680059953201
979386168752623983
282553309361566406
18018796572774464
12408013027170121
759714136626455531
345572490122461391
799776609513629873
130488633148111207
339242268886426085
85718323861972880
175231363749060570
145790424553965129
101101000001110111
636656676175782282
55506023871336827
282252761363425309
214736825185897356
214810466063786010
526945300948893122
87436266054441360
7187318948695250
111110101111011100
965699682097339801
526007555032204930
748136822993921093
629906374896794003
213379299955780730
793790222966575171
740607061157845902
10069928925780260
257327417366371914
698408225113891277
305907853603121641
91515112859593202
623964546840404490
84605289074517980
699029432804119801
146981154787061359
687548217899244227
166774390291980379
135916683264006480
711106456570082249
477349343268879725
188098450863084913
70251348016279954
551431309606162282
552543390481599589
487883630175777397
967447538728394369
45848502548095176
111100010101010010
925328919383251597
119851842186573359
20711912837894916
450761054967576917
15420251989365983
94305377294140717
403730579009324961
801453681851039681
577775315278080739
339249637439119813
504989253416641100
92741526330919291
969358826166628099
305036144290450201
99609375312625051
320075196818296920
154522043361033480
285897982154521233
520471260108041395
61988983154688150
232736240150946827
10860588747580052
847957479109368489
525244822955892029
695843285523497647
61210775335036013
521217294388116613
811788562396304143
186353476392862087
342250878685275067
291386659805678869
730958977535770710
597260932801241982
211964293578431601
782341988897580701
96549223603175385
210329931043456391
501656651722249
604664560137816060
76033059134388409
320640862583372707
614510406494701023
985178447662058371
28965907943831432
59700171142969401
795976475080968769
99246106895864058
18018866366255105
492284649682492757
888947865246341125
962164637361607745
365923247819346245
156692426813943307
104229386364206406
192804612932803231
478271754419511081
717378003762465025
439969872793359601
21482824114320805
52073686790459236
457470430226050337
88794135281968705
154840169028727728
137188656169006770
28133832609844900
852836509215077689
137271463080390
174888645494848433
511116753300641401
504989250005378759
304339277129007
617169137628627359
303403934053269561
61569951030187997
941474770843535989
747720834072384150
695084335393435220
631381302030394609
888504588517380582
240296913046992991
555988592685053001
550337021507439727
155568097139017725
132170039562311099
451769055843045701
132449000286846569
50253500078882701
257333473801747957
135448587543941039
441000734955215045
24122720639331864
177917624347062353
539845519279916220
18295943279411265
214873778978933057
27612693882363353
636884349129399746
808031542043953783
360512695566406400
29458572366825006
754209502988728987
229411129554229787
4848485839713831
747766717402505897
303285117201230741
235068333174299441
539022544943815741
259888714896346951
573060339936722505
469726948726898944
160768564855717877
2308087379183364
857481347658337656
760231891627492228
553908852893781962
145673214826619237
30273005689802983
995706130325662999
555932502524037263
551811059205899339
7054634058113161
489849533035896283
97925630300060117
819438717777588481
185427045492946056
26504805388698253
638524341894149701
651030889716763637
124552927317442624
734324340756311491
211174218984652482
748313268068091420
825739601260051169
88780451515316682
801220324286126220
236419887561331189
826407904962713329
368469795073431707
151947937958965606
33448618407543591
149343545691855402
673394932651899365
215471859820031011
99246106586965833
214810490867357772
27197360938505341
106869149037549366
491745895013829682
27197680216315005
165487753088449543
240522353494549980
25787769923557
1959737145159642
97656265631375000
10101010001010101
835279783458162084
858990081008420069
3359409591051396
63605929760867760
930805477104590839
430178304000064000
472217148018319617
27212595108201033
615341409660077437
814112523305194806
255321084063559556
915425279917196999
951387700420102501
519929068923518699
298504798830082005
99949252189117772
504989175105643100
999858426890790223
551814169551505861
314249661140137379
268248866252310784
182726208788822826
687984536287030557
854836234614845341
299500776125042783
682383028600399109
516331042351222633
178187256547765094
987516572078051856
839558376608098243
454251583822751167
856953072706200347
19711181564541741
5587932576009863
93018922059281296
449958586178936101
95290589418152382
257327417367000489
287159404312061532
572249843665096812
701910534633948439
929293739471304107
483246183976503593
210724016476667988
873637054682310449
12100637622022007
274222173749456129
70188843683507113
131723344341561636
15881969952874305
769064474562893323
457892058036896742
991390662133902409
371992471479452880
50585145568652
106886714606410285
419692544000065640
878010134278620696
866495753374660753
591767591063304107
214809152401155348
156618588056440896
332270979216504227
124664243561497601
214265514398309362
705848359963862923
192816687973569871
81930265667360420
246419278716106860
663122816903029841
681313747733359177
423031511507351803
176131383398249313
37189915657666593
311166383989259347
90019585965467522
814408096382644081
251715248026083856
151396755671302181
856484072679884333
99921165088063557
342017279309684357
964087717983186787
101101111111111011
618165444357600001
431279802274266057
456910511433754201
249514280153233936
20751736424436901
842342214040746903
178250690531269730
257902051650960805
254732557047998899
699987373963455361
75084688652343825
20985348369334043
588768366783415957
839302887483188605
212503063790458116
558629902914156247
47372111027427905
106869149037074815
151947659015688727
85801121160383963
522207688702211490
463066457728697957
18014468302700608
161845719121254631
135712464825517103
6840474232558440
42571014766555470
210906160619298157
881894047340468689
283467996058099876
703720868323082777
399438259943272242
993625446235078499
76578859135336449
189192874440059703
657745244790481
376807590016135256
96549221764865660
185295681601102801
174888645502887791
512947689043228561
746025954274872179
14878064880666709
8734303184760036
144556154179028176
303139237149549125
313504252527117857
91959939625554730
679367736807335539
372505224865628150
15881970929557950
367199177876660117
354292992575929621
46494254249694793
136523726919583457
91701124619966161
31093923628360069
108782448262964627
813572971495840001
432684569377881367
391927902752475570
571401879105375390
249958704705442210
208245261748304592
430934477976806365
119088191779081255
979220277052303787
433011409688874967
358492251399208401
526841185486533697
520411090020184929
386778073187544337
459161189030335233
58882636180247621
417054767069809909
21613984763438116
868383344446941456
2216284556637193
95151902871551604
362146716123929695
1650509861528557
641585008686369343
819878770416565902
219440622221169347
427929806439438486
804580531771031629
21486570734277331
10100010001010100
310894265253637
427201530699787693
7914311460557056
34067817895387500
130233222834465620
599778065673746405
121368947880479760
913517247580670898
391772996760510001
1000000005721
725228765913537367
50588561909261575
867097155240387290
20287273720426802
7236802220874212
154957641299475671
692974537236688909
155368321171205340
771703034964892210
432632331715598288
575684696529064261
884281272783853163
280132044765033119
238741614119040475
303305520497659961
39733598245091689
719226598295604913
704150459187323490
139617460803985800
939227282899646887
699748682525835264
597810878311477637
83854503532198969
31156453842312373
449733194250385503
19287289702843970
166519522004897297
844911464835282306
634314861849329917
301938437990289733
842343099791822441
716528737456842026
10234432593063757
378672084051563584
108035520758083829
167478156082403306
166680102489321765
95059919135826883
181674557069450993
59678048873622678
46862375738590830
106005369850561623
708495624789277863
913518198570730600
369039399357349162
504038241400406665
27618754594269440
972452166199104751
914593775211086424
836603158341516793
15882032460873663
161117126377452442
387461161837750879
100498443608255689
531235761963275141
889533214518148121
817188380321371452
106883432173720490
150094635297537123
173588922193135081
552645470130671353
950917188275267357
37903938739566947
851627181738501170
761895623350852481
296277148507075164
531441021895110030
17893107729909763
350400640689182429
27206534396595711
614907464268963660
942747577398559183
174949730482010384
549746846854110930
52731073812907656
127779655528616810
325830323868366799
558990806720372237
366238000505947651
967652214641143441
619145431083314361
150300809289163800
673861010230311753
372587040188866667
670863003254353463
727142774858486263
812363337707710337
737048109365115077
898240760213929681
410084258331425017
108256600889843796
172068604250344493
450678423731256900
210640344659515522
50536274159535025
2639927469677568
17387037579386973
245598579435952190
27829531005386177
147570617812918169
59689094227473752
243755839581379241
208008810420669241
526527401532282241
350356409292257637
857409627033812989
288604490704441409
91896612220797509
174950926939467543
563751691142257043
101973904882958761
529070134344035633
442524546244650097
43343382937399791
141108736287447184
376034666381004457
528421240102255573
104058841239070203
103769625234650762
997174749612748747
442664344120111667
320115594697209344
638342977131574709
208245261798084673
130035571162824756
23762763939057330
35459534188833649
720842765172540920
793523159491090561
307767707048290327
328549501578316321
288826270959125238
610023940851606437
238572164720511725
610754266513611593
659383557173287807
839521285305138135
214738188905858257
727548284346935951
275820739514554610
492473524339047241
208117924369734889
42440804779843176
316478846232952920
103980602363996243
940469994618028639
358711218893985173
228780867192188281
483510200580781139
790779955965996650
747983658514435226
863379888349894241
322000378834367677
87533912092164330
310647696256673131
875993837600352689
906502754946082297
35104249805322243
364195169848859807
59604644785563150
117338170431187217
422796338354952841
325830464530148683
154822657126526068
75469723825728439
963215935474674907
161443121067221904
908636201978843882
835308201638976961
637928251337371557
737467040727463301
509819567777028497
58011133915260037
208245261798091812
710168492009792209
8277363033811831
419430400000001601
599725682015278507
34894404757794482
790600714813177636
52003218984032450
416126878824007733
61992645517985025
86177341160117479
984871003622522257
52250698019545357
842255392356918540
965699332395812621
168658456653030401
626280535135940813
855500596647226256
99310020993771911
578093691330154583
526006901160747346
913074845942822400
304272105512865757
717784680635346282
754440189700854347
508922652598392367
913011437784283200
233984145088797869
541921192295209025
143268536196956416
601308043741178951
8797703497813476
354337726476175560
37296014378619361
18295874576711745
423802912884587783
659951230732756800
357893228763788611
768149299121682727
182726208786948629
66540575011961474
532051829100810930
339794828703792900
427929800130541982
52731073812529152
27829538257953917
466659535411903392
208245257615379600
231649381194361711
6645360936214747
70122819600622253
264357640246095479
97083266698006885
666331930422577103
946962435370443841
893275400970420485
781929015093320005
857436692676479400
133108494654949291
28726590568505747
734458437915695389
269078389185468617
360516623814463591
913948708152175962
457652188756770503
434434241811539293
123274746304561296
722577147754196921
511941316095555025
568030993359187223
79826191575137000
737775235420155481
776068264305180056
665440045189913981
562403177345425417
665440055731695778
263367669713519863
939482890797759457
432684001507875664
283422200865513183
799129308004394838
771151799205810065
269068468305046201
636358942208055239
870179818810757773
354293489495191141
174888645502738914
936201009149605
235106135215095693
626545873535447557
111011110010010100
354250498446517772
354337223848090829
72255061299588197
813890889859439105
133010243600727330
5208798089204013
704944099896107556
467596785132206003
389760192930988441
72255061299587040
508900828504037639
511263625918988223
296009264469934890
134238699520006481
316478381828866048
216416849921793780
557213717635927637
155807985093940804
299281666407594449
812053436573285776
878755586144827806
592954152628185637
79792958361972052
571577936287182350
956185698104306443
438468400927502087
491147682561392273
23762681285399166
395636530808937961
395872280791697183
169554393659035711
504991051312500309
31544362424947012
838862854196539226
293090286270238788
66277679799843121
198947828338219567
117416446129593057
182729813565135536
328435483541391229
833748657012679913
482166281284897411
534728965390199450
502387655772437604
449369655761025871
20627465305777201
451569683153475757
248263553616789349
168996744097072473
905332803347427961
265055505567893056
166774673060517898
842043865263107719
630250144898817025
716905515978456727
706206744477822451
616795972870196389
579090498953076581
288683676997019827
214810466523105528
84605484277042880
31093823306629445
230605830532125089
423004581112236552
671209415797308931
484615024417379663
354250498426688703
636469701037222145
9597039929457289
387421020506610001
353829791213899651
354494773470402847
717378234301872360
1177194696093441
283420990983403945
951407820717806892
579090498953898329
206699127050617589
951407820717806891
859479358805461139
85718519097865885
1897962200409664
599786784501786729
40930206453710001
347416219321657601
167474128661599004
922838852049800499
126653033097568777
520411730054288949
906501278939474681
816651761192705351
471075321115882171
154839336921923367
129196278622229083
787662811302087425
787663664220830495
713342963197106524
378140544573691073
581152749755905841
257362214852856304
505461107654206453
734458201884218701
213560240692108399
40930088805053001
207717276151173707
671923597993782140
588464717479411600
19736826725425489
40930087124010071
633787488034895401
30225399770822989
96551475478521910
120688181364526609
541025172326265823
31551085413765377
189534094734599899
166737107793229037
601206439473625993
452470921328329745
233593381975275057
511197480020370026
99648453443752501
50618220520356491
164663488577536009
42372892360156783
641054425467229181
312891132804491719
563751691029295525
239843017449869159
22886092692605719
210724016476667988
1440422011163665
318126402582410305
52008869703094344
176810598448384451
317689921301861200
41798194516214557
187634797045790417
385986837014541761
18295874576715776
521800382366405289
79674076645159879
867822053884995829
360508735607816401
31087200639231828
40361844111043070
78006578700279917
22540752736479961
46384545525723372
313900157308360423
257327821879534895
400041609870883163
525861510724163556
75084688652343750
537262768449177342
745613461901009983
725040252032776748
361301304847650806
18014399583227969
122467925299838977
888855489511895771
150308152041459861
619795976202102062
763285596651177629
152142682253950089
411360375539622413
587172562592474269
55716404068400625
113978712983409561
15885909910447101
476310930570263953
993329621261342137
782609306186934725
440493113243097311
41198751573259537
624328105947448093
247195254039399650
510918245249986117
395582144143023370
769320244367777702
468147269797231391
321582873701700626
168412105867367304
789637515726405026
112988717060409193
830180903957264213
40930087100004970
24122804526644142
675091176292518217
273291416103024225
922082674913206632
58871588781339506
152273539868068261
641507931449619271
35924052800588641
429927775562199621
483973468081506273
210193533485280743
883626530557061087
27024127183312979
853054849320662584
699823819120803936
385787851353749461
542585545273538219
323473723874977521
172723389507601260
833748648064777172
237227741680813636
759332640271571489
503030951007553
355003322692651609
210833883452709937
958433894431169641
202946879571053117
443348988680706649
579155339452352264
42421183300533244
768069325310389159
46329928738429924
141396041213510417
438362175441497298
16033242564798482
79826191292659302
23762762686724755
720867854607524820
249019795599813229
230393495061308869
234342228735317225
30053196392823506
813890916485474018
168379968552915242
81453912831859254
432632331646261384
128588671421575876
378004609964432026
234373909242421961
544230935206889039
97181528157400727
396793174883157343
168038239173855625
224292301727870059
922293150553943423
400118324060217692
46191172963099669
996790662102703722
813072141117266079
76006864584201533
76376028630803749
24861582063638041
608455638671992226
296249433810195273
409640141783449600
464799784614405696
150097494852418698
76085995812890625
34300732081490951
978199924781049900
968630540230120189
164662939909914697
368386782616956943
744798179178795930
46503477495548785
178808263834600093
201701495220833093
395636332449752587
8463626760114813
298599275156266381
539311033453452517
914596416827855449
154303540948231237
134129359980456516
560932689181271569
749810142182389513
731457164995147519
119851599099124158
297378412213498225
233866538621067513
151947655529435685
690150244514475763
64065316296778429
851877291441970
95085114428180647
626729679790283099
865002334949253497
900502020228807517
181611550382142347
394971759618704651
506517985024222635
457478934934915882
99245898056936359
890894354271744002
27212595128352222
966467034668031989
870609990978901407
555611670264758493
35996661808818907
631384432933447651
288864430064813943
426226903829889983
997983423671387210
801663688819499321
402942087655546151
88398788154119569
644611915462646071
365177336996510117
138506785965837799
525950989773313152
189219687489716603
469041663794172976
150094921256366806
197389128347911369
494463210767769962
260319601342336607
174766380663628172
154472417448833946
658542963466573201
332592931428065933
550094153957404361
688413587101919339
126771169289146013
288318427276574977
101626177356117823
294523861463377203
2365538265603200
304923661516079833
40353607000343000
963545680699380101
836309454960300311
88215298591434213
101111110011000110
126416562163485299
519929068220711702
62552229156982532
899620826014205881
66991255197529410
760231900302449093
125280167141878226
24122803293286303
607588069548092165
116700652790226756
314636303156864417
70036084945188311
356256291820968100
288863996438620590
87636451537322481
240522730831869137
872442626780496307
429922877542401640
573060339858656445
894090295691965681
82290035020127969
100637958948792589
164106853419283681
96387430775878166
151947655485851043
222343659610356250
106886711719235917
506594820916667611
607228174348769299
12493828344098561
117881638020492025
288249412520526865
2301659778555072
18018797629739008
400011017405287489
131723342223565860
45857725768537487
776945336504475757
186177836507244624
155624810139340080
168960456206869576
803348433209099556
217719423465139600
228369824900886727
35616480914070
167619854462143082
699960439450032091
558738710050151557
36029897604366368
720555619984042052
853054850236557150
614075810770451237
734865109299470814
502271003582270400
9906594028310053
10100000001000001
8054025472129507
555954070187442421
125128928532513443
305822350118696970
36064015750791169
939567850375290547
3854307828957185
18295873486192640
46825664069595840
727937578567056401
62602897316604100
967018650531427471
396776354185264897
906860756204891597
563751890530847885
626290465928529493
253378924250276330
362041100126915203
812114887119270
990871517925837025
387420489000737190
391772990790737101
13692209224831097
995929775132910156
429922717698560001
194335998768140773
9812905987572770
859538027504158943
11937566993903103
447651440657475690
491840486422186801
76248813495543130
232229234857303069
86016001344160400
140716959350834131
766794106464853636
692534003978216448
46745662300332304
148730444666274769
549766551724110930
506603486526426463
592940064134797697
34807691531812501
815925265073991019
822403745645848573
883926484632933317
495333403607510513
34051002774097546
122163008566248541
748106719566726029
813917357022872829
468909035678346376
82125337603208001
182072232029194442
525992491338734713
18617103217584036
81098188755467701
797533474281733249
911462791263710420
12021404894098057
639681950584721659
121422374548459558
27618664156038459
667959633262312651
100100101100101110
150303385635881481
584433412216470841
760231891627492228
777415093936685401
77194579102926501
24131289838674127
46494256079693807
169873255400746723
61108670560413
223374890189904312
679386704466635111
49936132463592059
327176464123529899
1359036777693457
480209578486013897
790461454680861264
62084204355485000
387421026346629090
236814642239786209
505826804270317717
96630224887153511
815598611457629809
473294901465276490
915575076081078533
661161985325586363
27206534416446135
52623450374957281
83013509244543150
171790176329015273
88933566280338853
640041532740615661
129692275063792547
150094921213326646
946945508338085689
892130942979644060
820473403115947349
218522178525482923
283395583458876659
152105145803118377
97656265943752550
149509710590064733
699091685076965
109178935494417751
151173517427900156
428162179924582553
378638654227930139
870987898046120976
3673529127635671
76561266965024784
579156036583098743
314311340179805377
159364048144891063
255772050443080027
626733508146748633
605411201902245026
950905221934934243
395236122718178437
34067444045600071
51701140312851
59678048873628007
14694101004638899
469041661402141725
13326248838633130
95151694449628047
214810466063786011
682254746606861341
971036888125584067
259184413248944921
156108312559575709
666133341577486084
15885909926200062
266629504884707413
134217993462278401
154489891610062009
156366171295259143
232514853632725805
553693362718428010
961385413319932690
509658799596983795
102790720481796481
99104939800210682
99610172193875050
641732009436068851
41250827035896791
934972096255021152
33076184937931056
307657733270934784
172552608492213963
712385293665840331
558850412781424081
40353724673353070
918824520003455757
353059753319481391
748660773683519531
956754583641095273
550656418519499208
162178484637903427
52599638858952768
57689160636876720
240818563771999724
427930374307936956
842342205002470425
224896022071777156
477293552017940753
85551681795980481
83769853406969284
631277907694923133
256273226232140882
874380602998197089
515003157164608423
852836452414842105
852840031760354737
62084356933984400
400552792783812749
841176482194213639
165509027686420056
234342233120169810
40361961784057901
135916424437766480
182588621245994404
113898668684672059
474406227899377870
407157049375885429
24122803274024071
576002226965647387
168647999937930586
537144687449969873
549746212599027931
59608459482812526
752425584147349225
560791508244855289
15885971457015745
150454938211195693
491727238234428191
419219061014723525
364393156242830509
18007626922057501
8618204100124090
404238714053694602
352271946509828869
306333100730746116
55860831004433779
31544362403565568
630250152554309471
32970393134325749
628399284487228817
913011437784282625
559959755022768553
52599143020031091
214738164570269502
650854185272232301
366029800712681371
540040330129530133
168833273718055411
669681951737092113
489579359513472484
101001101111100100
118700137784601632
990287169008978491
888562549932083269
963814138513555207
178249516230283166
39006137030081796
953179551492176756
436379165935930183
342008966694116929
95547416881932305
697063876298600711
278457687525882702
722407492361318724
764511267823222501
40930087100347900
3154832541066817
604829769046560060
315469109503977793
343922424315379271
297763552191133711
284179790477651406
261270454328415391
121262122924768997
27881950039589881
811417687478806439
282464471479088993
455399953206410483
448499500290194981
821892371258154631
866382697696654399
604661806669179601
893921825002374317
287563623311417690
366015793238806291
190654821446544400
223032691588283642
724875376489129409
486584306170626304
68574861731796552
843389474472764721
313828360286441339
317684569294973479
436854129188842226
95167745714837950
637619412275987262
811622896485740965
364637292023867101
338619237625620082
484904938033345600
151832656359724201
929305434139953200
472743169495774549
951301478780269351
282836675289730892
431632314332251902
237893590948277519
852836453345751335
35366262704640000
744729429386624402
815981003193631931
664565737336438829
654071375591267113
974040490916400610
256771506627397696
502819004292174883
100778036384380356
533499376766776543
272987559176058647
232228857038095120
435202856361874225
573498012016232773
355088713552851643
435849864300861696
926437089618257101
752358245595152957
913049364533979557
165566776059555769
64953840688019760
99388774078891885
457171616797842913
670387425048381901
31533128342611506
312249208805545284
564948722822501
146546119508670903
24430189849956801
439907954595891011
483185755912668881
20985787304180683
815933175492895453
716928675394211995
238741614116953895
79826191292661752
61641997560144226
27126200184411890
779807391835959369
585369934397352007
499816151044471999
151947659016220167
440280562236380377
150094918128836440
907084596019712323
577547034163662967
587974930885114757
353815283472417540
787372240993740380
604832520972963661
629839584411836543
505450192886529528
434350838157781591
564686253604609919
768069325309476388
394248286252689977
252058455980855939
336720999239372306
937393926129701587
129114030409594547
439970449614609616
35459642106996661
55863372382355233
227934944077710
873378708271939585
10100010101000101
18018797646774272
313295329399389019
58151262132649985
745198725690232027
279237078575910006
563751885899427328
616167940455922681
44873213957676196
40374988758031225
319193079632707601
43362994938034777
186940255315577483
131956503446937581
354515096664771912
368386782606404190
348469880465456923
351948564351400900
121632204321943937
947064649875404981
992558176034492233
62084350839844400
143069438509698890
627213232324658029
292827438903460928
222236834282140963
784294579427813776
222989435453840641
234689931194144851
928042135876177711
717775223033651328
240512152857783296
379516577718027585
551431592538626338
63639909964221842
119043321590213956
460377165329203
21030558811076101
667319367121303159
833835460618092240
261416701794391597
194894876186101
12710601853103026
564052009126609489
177994626844417277
170945246646749263
788482412963988517
105775710664178567
426841858601831111
99649219068877550
65359480303275007
930265051306379849
699747899852989440
841182631138043399
16291426496326257
543901833208101197
108256603740471654
161544828203475213
939999525929418530
477349943033844524
594250080013640957
34067826203346945
35459643693690438
652843264066951541
33288118720751442
626776317812465087
345200100042633124
492335469554097890
687026740098460644
997481832410021303
88142485129202389
353815300701758341
874875141570876143
709121905602315659
31069940539288950
599915625777177617
126778996698167073
907467667618012499
720628289370378911
921846889623126833
734855426644434984
595527041821005451
253380418995550056
451683402951364253
159310448943774031
674770800800264089
42440804779843176
661107924609139226
579155339373446879
48676324292965
214797726586656289
308723416490101313
252282187461407351
917280722939882491
123340182707204101
899098783928724283
862198186673468176
187509990879158071
150636094220556383
260698852948035959
667938356973901765
363143723740500337
4152299984147306
303644408405959319
106964474920814883
59569774388640000
524253573157161973
31551085392698500
38499271528744447
618980296930545657
809711540586312630
65324508390389623
163653792897533749
240688940439596021
735782543886907133
519779749846338001
322720831952664290
461229551279437937
260354798637100019
233018175054752283
427929800129788502
139453332637776811
760312698499301287
154823449609762248
425539695046779793
364369030821554642
290421086076899556
629547997638048803
438231904364298599
613591887505955399
70809319367142231
718765169794237830
913610454115461499
119343245339008969
16247423352658973
144609613900104704
14495870921041201
17996253622813457
808962680172117553
314927081731935092
86029669096573610
849554339131511120
584563571360570281
665439908089259706
81420679901407350
594365033484188023
594751270059007783
882093118321923917
108239260520583505
519872301174624107
316478851510953472
97695328131250001
610380342492277541
592271218720671653
648765134208316820
38381126973796325
939299201660721169
172564796382683672
161011153320326402
144608566057795268
526007555107814395
374877636640387398
101019324400569
178250690531120800
768149299121682728
257327821934243021
672745556685547018
392317586416638630
762928797537960061
255789941251996801
943321630824752873
776838806764782973
960947586391394282
780156074076407681
579156036660343054
299377258968288400
759084273940567177
429922717801024041
427981476232485995
892641765130731223
814153952103040001
454430381356028772
33763227413165903
354934162826337656
156403187013351185
852836509214839423
4441100718029057
67451759044549499
829831896949480379
244192244507612083
821365711050888667
52622943751839027
734647573919969687
385211864020372951
737105601323258753
104423010074375791
162892764483298781
118405712920121345
303860546333335697
408058663968353611
141992527943393467
76099163850427501
111011110011101111
474788171607977536
10101010100010001
21006304232992807
119088209713499107
257362619420091527
384261810081882663
32487390348695156
366168451509895819
99104947832038435
549999676639639223
844534302768223423
533688688808177057
560575688851258937
16978435296755625
423650244139881119
345985858985809829
416423023389666313
203456770423392451
863298279709448521
594246218927469011
397169309558331102
23751392538657425
106386173192712649
760309199063680773
839299365883116561
141209679849146460
106886489406803574
209257532487433
385316578991616432
999511050782450520
386695415124709709
416596034360542611
511266115297305902
873000061397946730
64777734043178210
166977711620924841
341500437587350571
511931752041765783
649836848153671397
979370916159788609
117895375755640560
839211075456987743
145631465997948101
235578658894009903
419374090976771091
362033331467635692
431203831195144201
320116059101296128
600351744444614033
469033629313550866
391725698511518100
370954822390147843
27612602094307961
247887207798080827
66082145934812701
387468850196618190
74277521510645756
353316519410835600
304559553014591297
78435603444299411
460953037508413721
117468256765486787
70188843683507147
134238961705478401
69498184650381972
971235850644944617
131314536108322577
34807309562785501
719781245191736641
34568975759475600
560624208432471185
2373746779444387
220093616131790960
228019776896334329
464075981915000625
245019940461901331
622718441835007039
734855421158514936
905354736679398409
950917181803477063
857483510122708451
520350113938318981
65215115799230016
285544154243695600
52622954531158225
959798169111080477
439969834362200640
810559826931678671
852836453345755179
614832465191788623
256137152498628901
778427670292031213
945201251471455343
976677764858987570
90718303029118057
34067444041406295
257362619365390710
984842583285268962
232019942608030740
228629420693216011
150102554186694339
314400167367440400
833748648065708761
178248713441082769
747857341000010921
336972012052794229
396793373820754320
764517420730496293
322871293225781316
203784254389730389
77755746923466103
649086724215253741
430379801799145337
520798205788923001
99618624894417489
552956513246969765
573059650066941543
526947023790288933
168377826560909220
71604968166965162
509658825320049526
58882785469416870
162562105215413711
701931546838556339
362144794910635749
186168982751154444
636953447767118400
480264093741093721
373347688891175077
316519249388503040
376034676754726944
116482668831989477
620423278364587331
472161969642345260
878076064996429849
195819856147568717
786346821281247433
588834564671180356
147388491719492869
27618754593964188
221265224275917376
429922881538561640
455047706978617600
21046208115510769
104874006514107617
592978511575536529
651404098202278547
509662223356695453
210126774122964551
71452330851426047
162446805370409536
40445892145712882
240522366523391232
307392687684976704
461248170402722
72075190787440657
244850262152862485
114084292718704896
299520819232927256
59703833007813151
61395468566752279
676762200893623367
100101100000000101
64925661412899121
803579534040301439
61608280548703716
71820574464844881
517135300289440000
152179282573610121
52623461154276432
611870072218243807
434406401594334183
204415316542780642
366451008212223602
586295238755143441
1843712635325625
767573818113504221
353815301317825321
260320005909571657
21030634229962501
294105735477401407
122333317089001801
1623601963369081
148744732787825769
852519802956696323
640204697206858126
75324234750556643
119870802968667197
226617242992665721
765879638395431
652417326762814117
841502410596704025
45335635000528897
95665247236636082
396035898517210392
614237958679371121
132763817159613025
13603330167889225
120006633354218843
643342495210422922
2420683000990969
56753757447890479
396278917554203561
34824133172371320
417200484939273683
154823451406563387
323498936741239459
974726768373855290
363463939906646436
18050093542943549
500058964987677151
51998697814607496
630250152554309375
213870658674477209
669550055686560383
511119242679171362
189192547499686333
331561288125433744
827572493333313225
493451127066845991
333056572909103261
288529741010781456
854392413213760931
83054649037441225
50205156882932081
234194907370845977
18300272623222849
630250152554318401
195744562394344682
417832069238549681
654106279547530384
30292345851664260
303296724712153379
366015310221052049
135277940648220517
627189173878296569
477349343268871168
20058047090809225
699823044600800352
857826929707933557
477294165035388252
551396758579157546
507881524736124901
811944352482930221
121388151789465919
937764280650975467
487950706148049226
669866553390072757
713537814083913547
108256600852822656
484649787691903777
726334858480732001
657212666137171600
614907418377600001
172347168830089273
383359669146513299
621043341616969992
18014467246002177
547124767744920731
853054850236799261
325825112520947559
200398279300867020
135382321714796388
421367333622981769
261314785167007663
476889182639175107
955304023771074917
193747953802254479
64925074344554497
27211735864918397
20375357500402452
162119481877130213
908737906025107183
550972549023032377
418886227159196053
653619132163834721
37797363115978161
3940524040903243
196388032305526727
389808441115467233
90740347214028731
66540410805471224
593461730454349499
142648848152191801
558822530547959223
414395379297806689
532031490000810001
548993343740907227
699748674457052257
950478771223800065
507883870161776239
287219692603588970
246889320953360933
853423752099796900
484775825018851810
788673832719756201
46494256079698848
932483888411705423
111012454131649225
312443731935547505
7241896477044890
1430946651728880
182726303718827131
144809791285636
867471169764611653
885583695406700011
44646783805123673
298657949062457053
40930087100347970
555827139069727716
547235061002164262
675382746049848677
716410061614060507
48120602477205149
573103718023135740
438362174784948724
147336039904395317
922744694524950099
157391980468676142
438966780827068471
700724596894587137
40353607024010070
96746368866669461
303307247582850561
150097459640194360
262135887934758085
99386520417756285
5614818711224837
542429283676005599
397987474016747063
393782077696015820
469171407568362975
70190683500091874
150300536889979143
42899234363539112
562797057342620941
629611979781743899
40353724673353000
659390660781499092
577934765411783473
472228088669822861
725040252033003729
187076160667305307
541495855618601833
814136153335833970
35973442045785229
526067078129082145
472304270177897090
140436679649513329
636398465826812509
500648907780064920
986932610384832400
842255392449145851
573059650066119700
922745645418940398
760231058744007172
419692544105025641
332863175837076931
383966975136000097
842255401395175810
939717052559371722
257362214798799026
978507564111045157
421608415038425213
151947655529429125
311227458422581406
885144398654476900
374297212302323329
178318692917075000
853582716107611643
102997780277992256
520411729978679485
513276715676233057
133986024662230225
910628028293438177
988954132896504461
168960448796719141
882799408286002859
6512085053695081
718628826951558871
177921136824691397
408641269790733571
92564751376563353
233336018644879681
381983166521297557
123399254473713199
660325832076735552
392683589373917663
691200889072276127
389463639170738357
301509750575141531
914593770433857049
184689771148819813
306015093838961149
721770842412021601
33270485921034889
111175240319382493
121387908702010320
571027830917613541
914596522499506752
930514050827520787
836543594547987613
866559530250559703
367202219306876256
69632849143576161
10101011111
381743085059481091
861879353363179776
99240685103198106
430185025536064000
362033365764082942
47785585903043783
485666577393400789
96387430740725124
209075729877614713
195110834830440161
670291688649499226
288826275999973186
34807317866460000
2026364764871082
664730498013753906
401399439984807321
465007718766500280
13715335079775122
347304269735296023
151823596577621100
510041690020264281
611313401292796891
414023140917287623
579880223650270231
680753442887353903
235369869488552929
591816684683375057
235075276154801447
506271233123958630
78166552120821125
67181976487199045
207528052575163603
66540577200981522
591142622626284002
965612344425925127
906389129141948159
740241612231329551
40938324235053071
53742074000580337
50588518038450085
210724020709167253
79431624183743390
324016876167500429
177051520256984120
515297296324936322
655400034130789249
66354544675750081
551401152266285121
432684007748205487
203279804364985571
368496222579943308
106886714568920754
549746867995110931
475927776878659757
317475974643703317
947181260675568739
401268133819943083
174949730474271642
880520944058600625
788863048214087089
303403964343517184
275237282719908841
99104939800228232
2821678942992484
246858877634461849
234587116456367137
604664559360219601
250421126163698803
914531244371129717
302137420013300089
238576398097011312
21035536457857415
419888131201668299
154472379625974124
16468025921101443
792260989599212721
147336040284739957
137073314719198226
137456906163857207
656733058282815806
46494382375748376
58871586708656931
430806414894889931
570210638854673964
381127292529567359
468889793592348179
798396576514537487
384456351712238269
86016001344000401
378125042526991939
745947049693436644
472217147947459100
7045887002207525
321163546729323693
36064015751872512
799013157461327601
30701856704906369
920484773066222081
97657031256377550
430806415540125256
289576696227232791
50588561947212135
428938848900364057
87963412586650225
833747762131100782
134238964982278401
76579958394257664
257902051138528775
279602770079147524
513701285113139777
362422287697962773
317029166160871761
429922877442561641
733487827523243521
150102261296254260
282811265157464846
105361233999572256
112874288723936100
378499964895385373
650347556611282531
125778772650944191
976885684215403289
31770060484413242
922837910473581697
719406874732744969
897023766973134599
657341086804692539
186967722245402364
81920537667200421
779796824208529863
111979621127212303
15380289459117025
312173431910301957
93664009356297933
891757512153163063
303307247592509496
566607816770354129
802254868204450421
76821195827477792
76861364652478721
789371169392402437
741325927511188183
79624954256411723
412020106415085499
531460705623327031
256467810881047013
472796758142762849
119088209375369056
36730298218856004
975384585214747236
83606617843175699
994148012581902370
52730934525706752
303307216741871161
141081365156704036
22813713102610190
975819930297412273
119088209713496455
964713524878516877
489268338630818911
722196374658811873
401493993247171199
692017083839870507
3584609444505665
126024340390742051
372254277846503251
320116064317972120
66540413024477849
149667736770712681
523924365589974241
472426375078090987
46494382375753347
58871588781728523
223966247766524177
922597024578704021
804427182598136987
652747663687064042
982596439650603737
127972070065249281
765708137143661029
66306446148612097
733510038470331659
106886489406329022
484699314108453501
285581884707385021
230370811054253087
361998597810955250
890833569066008959
515817289028561587
720565117359452808
605613944959632324
427981482472807537
76099163818365000
938164757907671933
436975400010199052
352966092280221023
220727397565370989
320435795389178311
79792266580207300
437476246525175311
901546375298975597
224788363774742783
676886884565946407
48673915096182336
671110885560348507
135916424437760000
333049497155926056
182726301085680209
571578031164274464
958537706101273322
789195916502161
47806758555019490
18014399583486016
798495125258578327
849289731408212224
58882785441013373
35407576700718121
922838851952770600
439329927538626643
53219749780671721
218248006795148443
880526262695504881
72076790867335310
694330958185679987
301464598416610561
866212025047740007
573059657327076286
734448749771479680
10001000000010101
797180109394272601
553159259372926442
53474664036220379
99648453131377501
135280761758081280
692609931484692481
32946026215712006
18126957108322933
244850262150832220
148088213352314596
207752832778984111
988412717282059981
358677839670391229
178249516230434851
801342945608813020
24122804545327026
36065116337242145
320115594636558424
53742085004154914
741708893993953399
400858340957126263
35354943232313699
100930154055150841
62355576529092197
37191015169262624
815470898212638530
210724371957411733
159657415236431561
950916909988282865
306673160967559319
878498821156023667
65327611679765556
636883621775318495
147336059682319300
21035461056817415
582101533526231071
653387367263087601
52008867768181896
800899467743567556
214811987648294023
147335012220348992
273304913740989900
624337486596743743
692396455219695056
150308434857905073
847817087162913047
438636212822891890
640269023465006885
217843794024436449
675950462969333137
310535432178125156
539632412548125041
765621628628711402
799012834729183141
219328353560061377
645938381639179793
178865026831040006
226519439988189779
563759875574758969
24555815949029071
396796734908630875
24122804545327026
192831325509781407
7173518032300753
999469518501268363
97696109693750050
7677546889478545
5995393517795403
643783831101857233
96235138345398432
186967718306368609
39734250153294413
505030676671064640
15882032460877632
34845241581796697
935075023034229529
3904371600870842
815471752593633437
699823819204853856
646827899957955451
279553290472521251
274037945486564873
162779056957464822
186177904011383040
998410779907345476
692627546115122929
350401132023671789
262938676480415296
733975428747071940
189234548370450625
44315414557479290
511116754027888499
144556153791512529
210724020708581520
178318692917075018
59678048901637231
734855190616071756
162450643980652544
38813887920896431
144555106336715985
429922713702400040
52599132470158608
50033945358270722
588033744783451472
343478271740338799
7900969612097803
298138618457500006
46503349395622775
34006528987831056
604661806656000061
19316807570451642
150094921213326565
178861409292329605
741061847323687121
591589114518405181
472217754302468909
405939395542705097
60045223513130361
155568386288835436
569554389112408391
75859936677121
66552562085744248
605756794497553513
878947115162500230
720564980253945372
256750224807833377
10100000101010101
257902078819000056
102668222773542977
372732044558104651
635034755073971720
602202326993320847
517254303895551881
13240923550300945
72339138003599377
27618754593964188
846832671537625973
474202071273255349
84605289074951104
27612603423976695
84503827692884597
23935720695044261
75098034700031326
50694829187990006
842256287237566278
145301081597992261
347029418552554373
799904258804009977
9197466836750947
568979959943605609
523085432500327662
15881969952874306
833834574775711377
254003830057769402
82265007971587985
36028797052552224
586315540005041160
55032610496222113
212674768648608613
81168659288398461
147488527745649553
604832567628960000
239129701288046957
179552112101338202
354495554809347923
298050573134166724
253296712244332680
50291280763237801
660449959161164177
10611190202028793
325621595419298841
188326491325830006
616458638817458617
481806421914841212
147389499640241041
154472417363271547
566336170577269302
878010024195012120
970175492561567162
154840169028913410
979999753586706361
740133030226595597
536797166881326613
744921420898905347
828084408169744711
252742611438852031
31550986525215876
767207788801027627
240155811302960810
692609148810962016
828864667920696707
957908091249390109
3358378960068007
487286812144684442
954074884826937330
446614898134289411
434723745484462129
924119717891060111
801025645351523927
20864142369172262
156362121723095205
234374290881191251
573059657327076192
855033637606933583
483811344618850711
458595790707128663
947080236921225626
342650160899345
571199387657475600
789937026470879797
972742212307575077
83646578653238306
66123603116593579
222013956828871091
177921134328308981
262897389420921617
144775491708432829
52623450379836962
972041893321500651
537356585458256100
194201997410172249
232459600526394091
730905673374876441
419437121638465640
605059435206637973
351575534695430810
209665337336244729
156422843176747365
135277942883742721
52599649643045570
288826271015763979
472217754302460353
27211409326961596
437894469765759616
991113112838602
928673375198009723
722045110822605376
973564869758918461
408749026947656839
50589925699400934
35452195753739379
166037624512305316
81920001280000000
63019165426245672
156290654497368513
155742104134152823
134238699520000080
318104104933626161
371729177598121
898497770158275263
99610156256250000
756218727609357377
510824171180998567
732993140987834597
550656613155022247
96630291117237886
999223042556216851
66278254892396545
870541800268630297
396284877140150729
252492019840493249
846144328224985021
842255401396117003
531460705599810031
238741614117010172
13388904189337057
241392481452116832
951744646060758072
925112544778478167
935932866908892511
45848502548453015
841923576595076441
53954348692368793
18882843748819601
138982392573320353
734448749902246765
23762763920082529
167478157459808777
55362775613803849
720866190516856189
66306446403305520
151970535808137127
105206130021598080
934954084689418081
10063243024383
186940586147526202
477294158444572929
316236310636911006
217569923508307656
266258352331143551
167530512544791691
253295190312382681
144609594136947317
27618754594264950
258076696092150016
349963930724700767
57678666200924225
155867212995455556
238741617127891722
64925074344443905
25915291254352901
320074732414210136
980607297765757367
10100000101010101
526615221915604693
738495153585626599
396861002706595356
40930204773014900
52061740106635562
214801814046241351
25909602292195400
835202427155019557
564079072960865446
358464732105503473
276972624584280769
510446129572522657
96403479299145018
816785347416436007
325788405970251607
317475978164762041
132157931432249653
150102543324571741
673054931041361002
1855566742173701
720565118169957034
673603505199201277
256797023089597777
248913279535113216
490472135172630
488100507928819507
234342228735924126
387835604794842187
931420294393100672
509812198835541923
294107188786556417
93028198562494292
931636445780706409
426001804963637429
43343373463105010
686702498629131533
42329051087283253
18300272606449728
307935253603097023
313003375559966116
141272380021794811
791193993096304403
374877845407424125
52121503393198503
687927980622488539
584196600711130937
76099341828521250
363048456949341049
13648530872263330
174887470791750763
43363430760171611
446773296272573047
922225046065593397
387468850131008190
9273324448802405
181168501573360949
75378398741291713
99610171881250000
257362210093885398
361475273033492311
354618183618010225
27618662785456912
108205785059658006
562279763831858419
465206807799721709
278338541863376016
822531052505990529
851078828746201879
27461826130642201
455374772502600079
437761992050499870
77663331902446473
40353607024014971
64925661667590192
40520771025277463
7191969438030401
717784680635420328
96387639198258177
4885032357609043
370044746154315750
86248471564551643
999881802903927469
606880397006407083
125296740662030412
651146657225544661
51340444553321401
550656418403641325
247860752067096337
535870203371970482
604829768268960060
40353607024353071
805843603612513177
446144833222797497
766933088248065601
688462765404939971
85816643250414063
649150067208694957
122119263897326225
985091680980809189
967659782890515006
37505940884224037
514340920375370201
320075191481697345
7604425297662737
519782280666242639
96551409301002285
167644782963436224
4462150956044222
760231067241905571
257362210149222271
85703871333967504
27612603423981184
257362614716464717
127492095130385891
8051652450731001
564107968833251719
173907951915357452
257327422070634608
232716858570132806
72057594037927936
800075090149157021
47105152335191089
289471541413129621
722086718776650457
998899988837730851
30041211055888036
345701642524299899
922837900962720699
728271673355557453
501077119135514183
111005569630225273
860081750652511550
76860329564311825
60300693633942021
70249614698954564
300464619995480493
129971134443889216
853054792534968853
990488835837931421
569140233090784163
9232023406729561
950905221935015600
10915268321774083
187994853522215290
995985307547703226
672049982179579013
817604057320593665
178188409094692679
432632331715590006
593061096473011681
556993776744504650
110918096118379225
320115599914566808
320075196759008857
409813346562165289
407531648784405080
520471253150361901
429922881640960040
96403482005929176
528520435247697990
788482412991664386
584512443591624287
565774670103012511
317066340038046481
264081502459954881
693530080069597157
181566833438117137
427930374307945145
168029250465791521
173466424879902050
298023376767578755
6673874344238657
482174239189730401
870493722132698749
918064544429538073
59700164804688126
306234416461324611
136674754586949121
157854290397913063
307281475035284977
391772996760510090
375985858222258649
27829850448026881
106075820490487393
959318880304752009
994165529539253233
70251400538334222
34067817710950500
424587009788058810
820890846936406031
242651523418274857
580087144640205067
350401137607739158
88976190781461947
815155190065740305
338084444392686436
208216099878755472
172108379706645523
179266535796862891
630319243454218845
31087101750363137
77493238057305079
64953241643888688
10462063706692900
554957226180395251
27139086880520853
291597964704408023
11495410680522410
23387090632851457
757076398526595947
325931925854974880
35449314530773572
519577335016556827
913011332295426648
167619554162325364
374232312072090001
342340093791437999
214738188906015720
510695285824146150
417312762717082699
2139009622742053
650548130721334217
102463961649649109
288826704584667745
92077460955910443
813071289085072385
83950191208289317
393176653487376767
151970535765096966
728965189200253051
368133643599471684
360035102597735150
472819063786578391
376475123587515097
383707222450626953
634574001581348556
599388883128186931
57342242689996812
800027366128515122
950916916453156092
865023153123631682
561618026692162537
668483513939551691
354236007935059354
166795007604500448
275374854905932657
452131614075692256
934657430137482661
46503349395264936
85600597867912602
983677761042532417
801347445967397761
395636344081933519
141134034443931900
420677305906924663
642763499691858719
61747849680400
471071947715256970
100923115913900157
957969062990845267
496987381206849080
43363421075432121
120515587277602501
75098215019953201
976666566802729663
657508592440570361
76823386852112723
422785290894039306
955135534622078527
430178471936065601
285797536274757
210944297598372529
187282951673334012
257984290825107056
285544159227897324
45444140533884479
980342684479838909
12446647477927937
302931005816355856
747390870039126391
42441240597403057
260320001150608060
352266237331240187
63050797044608383
950940194666256811
166797270527583258
737493001957230611
1607525257155949
21363827636181102
951464480851046465
12008548293924485
693292232027760143
372278933896075851
549766550994300901
178865145827752103
178282530591842123
295665117997988685
34067444230126126
43343373467679757
740909741937382729
257900556896370025
906528360299673241
254888572805523930
240522366506202816
7778016199191
405466505603225362
517545797132220481
155204348047588730
4605870577032661
186940586194419625
860989538370953180
400956077363093617
813713003134697241
956526620863560067
20711913998460101
775667034665666681
167455367349806557
44422053204863803
988750291212862932
120081876697447879
770063158244026597
44354821354357559
121388151789465840
51998839063216128
54738640654266533
106886714568920755
1537902976335911
308818375856008761
46494254250052775
288697585578422022
803071842715846565
36029896564146209
688056624700453369
913008795985022976
172138309782202
97695312818875050
338083870501489800
843113472948670751
396857432273380633
347763039953640013
25616462325713533
178051193565707563
877060741370889732
582760180488712249
670089949916828841
586795482771560071
51998839090095169
34051010889327526
506743095012025
106868920913759238
826213742303110981
977370926036076962
419164321746229057
329726921982825593
59608459482438126
167619554117106547
320468358837676267
438032289038262990
244854609865765813
166980564197926947
257902051138359430
564978387836677501
27212686936563224
76099344201990000
284957417395003019
35965887774369558
200399016686358540
155867495022670762
96551411086703126
159816217985693303
106868920913290770
252452670468989707
839517763705308262
3122735805733109
150117512089454164
308721659105004096
354337720892116021
387514124234724407
912306527089850437
24122803274019648
81920512064008001
119089106786049508
253260706932770593
214810466531454036
104434565648737130
104455636317024785
20711912838165251
168962583404048890
666136928105169379
188449720067145681
665441710101142351
503092282537436947
636954190596809471
75084864258240001
489006547619227879
61992651376969401
182859775374274534
936527051146442007
179909011629273
255413663660239562
581641301911715719
178284546149929687
601515356156100
438362137372613006
81420680183882600
119089107130942108
100011100110010111
283504717335754151
685590055177369992
67439605515688498
760311865615835047
898079766411051613
644824147880962624
414349520706917293
151947690746495481
179151681026765091
64953241649088816
790342406140769317
296275996108811070
8097027662728710
334869713457003971
382660044965032811
200398279264763905
39612082333458269
144115189168504905
15885971457269698
275712426781728049
155661321848991588
504079668066079873
858975098009900167
38230465478997763
270722811493198369
629560737411962339
514575441775939601
447003004582305889
79343244949248900
299807149551221671
243880603947964173
733984117720189451
26645012031102637
243582612076155664
951408092683428290
380684825861498471
3968499165800625
561429685128937690
726338374085488741
915687375114743017
593010214623950987
839299422683594378
884765537605556406
458907263779752192
984930291897797826
698228887393126169
648666436945457791
883206224209979687
25046006146202
662119209601005162
297096862051039700
715813395679211161
843493302603672829
240807985315409681
374881207073496805
407328775973133451
173135061507850225
162153497560692721
549156356100027001
84605481774440704
218759728093010330
387468856102239000
362144795522701864
962855662051458407
214736825644902000
413499412147283551
4861012123879681
182859777870657023
567838064166034349
660426632387030897
432632899515521705
29674503615677882
610691186294394242
762775921065632207
469050568058549839
7303561583070006
427981476300307384
60777998919355249
208173430330390756
192387357023708225
66540574981569675
362146750409821000
517795463469183661
17604722364135732
52774716215787807
70188896162720021
257984290321825705
219895507658771479
166977743001918768
561325972236212836
950905500071570954
317684702916951318
453083211557108161
174888645494851241
28524183054499521
402168203073496230
653901633485004025
24128175781058184
527449772563118502
119851842147629599
684087569602709263
632056115887965330
374813566587603973
12206390401632481
71128669455095743
121368707908537681
432684569445702757
800094213202582607
154823487342771367
35179719915755777
112044532397126309
221339750800012379
56476242524352250
6821833259472100
107429750632182227
423124965670319597
89944190774991313
121423271959004706
519929068208385480
2338107430194381
790458082903815876
211837558556649877
596696564882039357
515638223612372983
288864430064163010
266827525077445543
159114064983409936
289276401760343089
831855597703208599
152970134623179163
152176706270404344
650047159693965463
528625804402069433
300506598193456905
7477995410487812
805527993940402771
586988721288767363
96218085182731203
122357572873036203
813218265960205717
553152121708887241
21035536458127751
394130252212647721
656800473155565081
519782238485708940
630319978546109375
28989610396382737
27212685586438050
69118629156712621
462165344405145743
168412217067811063
449796641305446403
789337906168343723
44992990006791122
34807318051079251
225908165989696577
307523723190843149
210904846021173924
40930206430047900
1891107688449424
341410095413778373
347773529871983490
79792944526567350
557383017100802340
394198429057279247
802150099229190602
51264251235473959
929844430119038982
9666474448651130
17211912734678220
364349273024941307
692012690012896711
759536639101859789
997066324774447225
885937028846380309
446939188622966343
365964331904119882
697205462830213487
529750156528230001
671026551810544712
375810687678093919
826789261858461842
558652265628315365
23768217847713307
979006090996259041
541498302681190806
315855042668022917
308820103501414457
176903160056345677
638609433733918507
139507018739923183
669016510613464037
285406724165949847
366450525195882270
788462417691575503
768150132093678150
970496067128256233
213827270154208272
504932554245417161
863404693755269899
722186423131763529
247174842931577856
480595680219411811
370219157844315130
73261195997483026
121261112023563906
349481014654554361
822294015161107903
35459643693690370
170341929626758649
379026120100387511
732980402065935073
7552626329693256
768149290534342471
162195162721886469
649676388481727970
115791540756596722
176732389872906256
38171878977260
97696109693752500
947066424666595489
260221101352776369
719233612599804161
112585444121115167
509849718926861923
559716855412610631
453181797267147947
84954665006397061
102885769145482357
415907543955881009
542492419077976753
534671051828233849
760312698586917797
147389519783740468
170041236783504071
535428782382051829
821246054250565442
18516414978843469
285544159227904807
383937438874092608
465186549004726881
135277940646542197
713346105926320026
215969158788757220
121422356945273853
348688572492591731
701267928582650141
174887470365664735
505976167296200307
378512938181039791
804435200331400453
214954902185173264
579156036660351796
468593733463584667
167644782963442948
288864001480111902
730815501465694157
76085995813318200
40353607024010000
927046189648922663
167003413134428772
96628037403537535
142334933506285506
600401743930420500
509734558819402793
782446048621638025
974962759329567161
684787648192417813
984132074749369111
457471159216423019
10101000001000101
210904821685582255
614739456000216001
119043338834578704
296897814425879461
141080239335920839
18295873486192641
280348648404598802
801759813501661771
50542150423673700
815941751982521317
175653563850766693
735483816052409999
569792425816355123
627013803982245223
260354394069857486
19669850582820780
9682051573874472
501770394471451333
435788714990251223
20716816226346501
594227232530953
99104947832039111
374112456018841999
712714725273519223
818134131508122347
820645084868002357
212043648746319581
52008867741676104
297231488414632837
366273729813304400
463182870321132213
842234377778490379
456697864278297010
155112652262930
312351416308675150
99388774132913125
21539023591051264
342293847432263281
237944180557210176
398959230558461647
134238964941312081
164698054354796545
574054719864062821
75084688684406326
913610454019401897
635450463948510773
19736216720682367
810658493397983599
426833475800562209
42420757167613402
369650891636208401
623438447341426275
627583588482565207
283394376298108746
99307706564828126
795276493645716779
587416377358543290
485197533626737499
929808020430525101
237915123044962651
150102543711972547
511116753312964200
947819019080640784
284568995889205439
183478924154671202
354292992575937541
579306146619620
72076286005088513
271716451824840013
356821514968823917
702543708134035301
354293495078545621
810000121500004556
134555310865558903
350356409354286989
885105595312659197
240512152359298065
495112512384055443
29990776756651662
704817997419895769
301256925523096889
894325136523051491
465684501321461601
467217180412175490
448354898810224141
697784139780198689
671561985564227851
185264345018632153
580508860518994271
720844694375698295
5447882885550625
222527482882035157
353814783226687472
354292998097951709
517569963719456025
31550986524901444
899301209305849692
737127072864314471
550656418516602845
329652812271076010
167478157558192348
717378239921523055
822637772474152139
81920000003360020
303307247592685056
712534010254376837
5613964967401609
416427799976669756
955702036445974717
31204528975953370
852840030829683897
189771500623028501
399232849195050025
813377527073900329
74040034445910225
349917936363412537
366436500451595314
175424943969349711
829364655096285307
598141231329272707
395640112296119670
267756458373900611
569983418266405242
178899299137603080
370576037148936192
692609931568751616
5167699937264657
699823819120803841
99039234192655020
51917636029973143
167369072970491370
520471253076352408
170029252992567260
354337726476183481
779121880938588673
175545620522832609
10100010101010001
68963398119186562
20716891663087751
64170116024240521
64925062368659761
548294276316146449
889674453264411364
649260682711814171
557822370049931533
35973440504087662
120386956445983460
485558250349957481
984930291897793920
459144946555471667
42420747688739598
659206865203295809
499389537958125157
88561953439302420
837999569187770896
765579533925012361
906399950811454450
432684001507875755
913517257090581099
125531485978675985
292500117462910111
10000010001010100
427982050409872686
2551159030491000
334388054934767879
928931991656803580
151970532321352726
738535905866074829
995786198046831857
283164221707596441
64953840948019200
490324665790397341
10100010101000100
72356730189713408
15885971441262721
42146323680401
174950926931574253
387468856035908100
212548344125562217
403512877330175467
774588094700235090
339011372050886681
567541743371884781
424682179545740741
77708966276358400
123995172445717806
368386783207911112
151970814708373926
80093123929085796
505030676671332313
6065111227622977
94813319826656657
247936659035923456
303307216751705657
14826485344803991
760231891715108933
183287009681263362
842343099791822538
585402744765216839
67439769751760027
177921136895910884
261480997970687041
24128259706028083
520471260108050044
260354394123929557
520411736935563178
8323756342717507
99104730664230330
17039751724960000
654862858378784785
876491090348544001
993671306344417357
507682258720617253
44984432540275153
692534003979101184
35459535775532049
977683353169723524
187583808672586226
354152224808037604
20711989435197191
956888143479700621
96551475478523136
147335031990818048
35973334149955929
23768217847425810
317684703007234836
332799460187987893
312035344859989229
111354206374741729
64242216790705249
592636694629803012
508670973949228092
297770870295943531
942139639260375713
137975285996361010
479821866831875563
614756011473764899
97657031256375051
72253273960918222
18295873486196801
389711836175328723
306359504207190767
303402237248843320
519995188629672562
35965995714866421
130593734352756989
984934231854866622
422522652729689513
135382243411051777
61992804209391251
339204913361414833
895249495483882499
250517381907406111
354116532098302843
166797239142271392
547419234053435351
12408689292729912
81148829101198561
631006075548391591
636884349210841345
736897910048017147
59751159506893009
497965730004263161
196322033571550929
630630832760359793
833760148197967513
22890799608158306
737355958841582429
720867854544404854
123368405335834349
79825513351944053
928131513409333501
345206828081385917
181615452745849670
545778482396212981
8145388125254416
727907525168626057
9148961716542026
201298045636187556
208215748581316561
830899160916110210
675921424317092836
253751774172541189
304495581132048306
547136266874188487
807146019246680293
79825513069471254
351210214964031161
106886714569389145
24674968379490
734458207373174634
234342228683730726
99609390937502551
492221411196765184
13176975173283043
552059038718636781
669680159576726819
424702426986844147
313398706055377627
760231058744007269
27618753263994757
768886416232421323
241243859789277490
5673627392545225
14266089057899490
699747899853865056
114625740544006757
189220014430089972
24128259687340842
534457273380893257
27024037129604969
958557148162625125
180438261323375623
112148214054005251
311950226468458773
728173539561722501
16594784402090569
377098960674479717
966141400322856241
604664560137600000
162195202256169348
293492575042262107
753127529610323281
735500646468687611
15885972433949310
444572753481440773
52379832481956057
155937918352499713
787689251811781568
799007025503674142
311024777494504303
135895711744006480
248215915009565159
553477292516697026
432684001508637606
661717696412676289
40361842454010071
384512164941021601
239581539386078041
81920000003200001
358374685826873581
394882880143857563
162194955689055749
696961073131383025
548327375115153509
350356409292249627
635653298366214489
150117515576770005
108342950168939409
858871803245836690
929793547455222870
630250144897950626
905287060400895283
31541999938056300
717241079769855497
71974303271272900
391194386087247650
921961365060518503
755768324288315557
99857172047439170
613411300257678569
27206534396299503
188853011467921399
101111001010000001
198324314553000942
396861212699955900
451940255562670841
152153832921746850
168671396621782756
743039955501503717
109478041291864921
489777280413923712
654290876840671229
443000896741271003
54338407823743933
84940112549901589
96387433482662246
9380955336830224
385950834395343396
588759415872304247
958277347005530077
407222441152059551
867221809828948127
993021089072670919
736555754242636841
543957691575245669
549746868699837900
3943069481638226
155867505870464163
178693089779845973
312428314220781900
425512334769694225
843294765906443833
691546931202287003
589717039345590321
885725245278824201
164003044391801761
520411729979483749
867587331806273443
427930374308698716
436018919455444327
493592918419792489
968875469340562757
692439387439995471
925388595401267210
491326231920788291
282811322635922543
92357152024400971
516465646247481817
573060347196866179
167619550409714756
295666270282861303
922718040858872953
156614583085324817
945639880339868225
632022580835907029
913518198473700601
234990108663832872
366015293587216650
64857902211358727
131608513521051293
866638097413166849
196930569014654203
290709151694565590
63772191321349226
121376589000703503
524662205116037
352837825364360833
152158016861417502
447224279432758579
149607164351258462
52073686790460324
946116265827291481
152098199765326864
554229786705133772
68498762796718489
59700165048843751
298501013477050631
110442708359861833
99648453125000000
547414866423408349
42566463256449553
497822560488645561
184308083806115881
454669997015377147
309752594234266225
842513138416156397
843279437965346362
556160444561774281
137078720931342096
9635899867101781
451632185701330053
827486691699332025
98929360257474780
52623450145612321
323455291484272933
924449730644488879
350356900689481229
361879241680528487
715803273652358081
37364767254600806
149514456192240241
953671617608740021
841350374790850090
248782550901165023
908489869948409029
43807093413977922
215777972545229767
503014844400838967
651050671790608471
496890814431757021
66540410805471298
18014467245740097
374817147464565702
614403577921000001
860794735005999050
12860478442998450
354235507689353674
743164515269931941
582613332745560637
147389519791192693
155460587887998649
6742645850481841
757984740687061571
640237930385199266
231649385578600085
998995041029884733
229549998794774219
34807309562694421
500497703701637
150308445304421101
90142594532173387
84590839082471105
34824498353437545
473276799074343073
476540126400743023
575888011876643491
326401924883847083
833834574684415752
60442231596450343
211127184048742201
164381936155099137
472419480533506697
194389994207152189
950892722990394187
344638000608030441
81920512067368400
131914155011213690
315403483887123026
66676478974269990
105243492585585161
50111359200303556
807847663090749431
985178510185814595
829048772183322203
150300561732779259
767140244462161476
359244871001826420
257911113126701502
27695158247634753
253380419004703651
203144213596085400
783606142201593511
635771153801003839
391772990856339091
320899121354731396
623718836605797121
359523365797834853
843389474472627921
215438951537426377
204922649943468901
3094220002384082
210833882993547882
612584119097611025
984930355397733571
74870063550986970
688435865012164963
134238961705472000
83380171625306251
504989250005379287
871417828829582747
306499356452909021
260354793932822447
155692560390445817
505204910386182400
357342773944800577
914593770425548800
173538403586209872
167202712655744089
152153864346384531
108870563349516816
278112229490440901
64953828712120368
163666977535197781
42420756957075635
179501177574178850
95434595004764107
514025366489679643
843389475317114498
40694013305015185
151970818195164889
27197368194732077
395531723377900619
31087199164226693
82135552067368020
12173464542869167
150102261281924308
779008631468677873
485287545354819269
643307467774701512
1680594657438193
148526242769755583
750579275523207821
90360484980677099
560207621382535721
78517185116690762
467086819140813601
940112271771983031
204605182976133001
609591573292015757
762793851499393507
736088345219839921
301767453528986026
95434595004782333
865969155855974777
141645750067652021
135382323952046197
178316795512392298
922448204672358487
97657047187500050
876150299137319031
12554480460181285
520411730053484685
44878635563037307
572743155287353445
636883614118959650
383162485040289040
286830348238662601
224070838415174213
96387639163099284
630762062519116507
374320061996626517
150094635684440049
350054920164544056
734458201887254586
59700165048843750
929305434139953200
477349943033065744
832750749199751099
595305492512422329
67439607764687175
541026895637920921
852836510145990762
46648872680004
827496589773821333
95429173841828632
325824971859048520
36065081976455200
86231578944008020
337094071790291111
407292866669494277
791023860146762617
833834583815860635
186168920407024320
998026688451302450
80694300241726084
24217057231730603
79792266303494451
919113740322706613
943898707521988993
604661807433819600
600661016196225246
35500063754135237
26272167943044103
217514668339548363
451625990256793741
53718769566383999
934089877403605159
66074991681566407
496724019744474542
267894200411399027
555991443658330010
334936872873410531
169663995320797976
950450925445917437
511309764618347803
947554959936295267
698870291473329973
450376265146810924
189843230242600901
791868679190901225
466246810273914362
244557850801800649
119871046056609516
109933159739134429
10953403551758417
849594533989126537
18662609036545601
35459534189157327
345905045220669971
438890147527162687
280389237282794851
832896654524894962
69291782193342539
144609594136809413
38114273026170442
146683647257219073
49430118949806433
184915927485421189
234595165615839593
66540575011961475
232229221364989996
106869146149906453
16531499693937413
354250497831158913
18295942205673536
40930204749347900
3821903735294757
96082495447390093
896032414477504063
131723263798936884
917849752553203651
231649003992031336
768149299209299239
34824506657294296
286383717441894282
333839349694518883
84590839115833356
551396760956446010
975816641794193762
927259006512723432
564079073079547367
615782856653270571
257362214852856391
860646553187448257
236506656524730547
64953241394284849
941887047708969233
178249515812239359
353815301317800062
22947451177934797
67451756795961448
308910944879007587
661968475689645853
203019990687295610
711283264944518587
35919481414991957
830479307293027876
783206223067540273
700395119855535007
461965908326947601
3716187985736481
247822232722085891
8832300359341761
169663694976319615
31426501144195370
773055818844493041
10100010100000001
851139785814990073
266576210748905532
135280763993698128
43427194613597551
295983063855038280
145709446493069556
246263149897095481
423808046619331723
944737171062445141
210724367774699605
507727190561006903
35754185141748441
379573086214635823
510943911077219303
69892804480135730
398950512020586437
432684569377889648
69105484044929181
859596540404293411
178756584422857379
58519354671907601
585750884992418682
111001001000001001
76843772465385488
56676001952730062
717368321241235692
325043061923683451
571611833559063549
30599923260513907
27815482781761005
191536553056074959
550847801682818027
624083319468029969
388838469242493906
505161241859988560
186168244436980573
473095176094350793
439840662281913600
370194861971506056
238576401108002568
564087257393229530
135277862284057681
477293558608755984
169688623568588558
84659833400849642
123253761399877039
799675650043599731
932138473850463782
535168432224779699
131723344341609552
506151637413449104
525240803447463703
441127909911953664
799271755035880009
10250793115686201
25047111070914143
570683092301875810
153133575671382463
202036260721537919
177594920069335129
345672132150318767
721828697759947391
52121547341093737
31093823285248069
146407121290826304
255294651278428213
560406908201907215
997181730253769843
909961114208892793
839302888399083108
178899306136161464
603037886598882701
191627908121134783
11638680627302090
35973332586253090
977636257217784506
878010129692135425
127934708059587073
869838027698655626
112262341186660463
981107054894961290
891688199965351923
282900456584943121
24454184235061103
177921134260839186
40938441884053071
807667012692705691
348297740023840256
736567221677387971
18300272623226880
898482184106205757
788483265854102436
399073701725345221
154143210045609883
41181151700816249
24729415254203881
382242042673620463
21035536475708040
386173860355200996
130266191294387429
121423271959007308
303402206417525881
469033011645522750
317684706525919278
97695312818877500
774670731420974821
375973770078861498
45848502548453087
96387639198714710
78873981708659520
626770568612488042
310687426888870085
34414696141136669
757591742569325033
296772004028262901
260969471128802677
692609923330080769
358356092386191591
72315778293689840
166393869974289641
378324734534767597
142034729278911347
182859682936904360
984577702339182407
614907464256219600
115966582721623813
196076477987497339
809704736893870849
547713744490818727
381557693050646681
99310022781059126
282836617806119102
162195996625871670
792205880608048842
895453093543455722
753276333785987201
104278470908116369
938878071027780287
178187234375513485
744102553546971037
542791194648497737
839302888399317592
792858603485026
115968017734896756
976732583981645863
77962545213836645
594384107440036
922837900963681099
27815482946677228
669533397825557959
263557012075926133
151973078066235262
34807318046887545
41876850607232282
368227717271682613
137381315752820736
35459643693695199
298887101092873399
138933877187984151
325591638570656131
744436793272747543
260337992657624471
585893294438424253
333479407724916611
351323083167407311
887948398680289883
80803977269062207
105853398135820865
986655444111755867
842342204910243213
504077870170208474
371215571715263756
18018866366255168
79825499228184004
787458608162324670
362714666042068729
592778045971848025
651350392552262407
914239959441942193
713537762563312265
655564030046282281
614163500518620650
603169415446111153
839862395964020
24122721891381301
348377184056871026
53101933441801249
1574444467732901
51998837128298496
59689245532912783
418282828182821817
42136123296618463
562517053518066887
830317946466958570
473682325907545177
530843692107814699
804552618761026381
8693934897419257
283855583376060221
807694099849478981
572476741930437185
189220010539079520
42441240597403056
425722867449387561
328874292469140625
427930374240123847
285544159284536065
79825499234066454
557382824482950781
124787685894783030
2963355450060810
135139508662132567
64925062113853440
507290909623328879
422204081775649883
316519719130560089
112668948034422026
101731101369468822
121281202249977193
114370790948014333
655461021911553730
358672208847843521
686273905315090867
366460501984675345
342603571089437101
512377819745362777
81434854210295953
734864873271178147
962731355459383273
52772588098859477
121377504359462157
73599515528256
669680158760995916
172282058510118860
548163236119088221
66714412186334225
104721848035040256
859822700243595001
386961897003567293
786887983130116625
760311856939956100
526006908042834487
318739708149853279
996082842562210501
86231552000008400
998909127541302617
144469487937707820
59703827158203126
240433164614021413
787662784677006785
826153295189363159
210352922625980484
846000788528723339
252915253427325353
121502904876638224
510568914993266705
277903511573783663
164663412341903880
22488810791439204
467182737869275639
300507507627425001
310541649405856819
954249917878739227
29720629239155120
796875485438374949
438362137361488200
106071861405369762
636954182941308000
149927113019463303
813451633916292797
23762681266136868
155313321487866433
201682254093016320
790857550493536571
288353702867880109
992625019955930596
72057594037927935
399101163819811600
84591119121680101
728874428661295151
819809600185624130
422572231615923293
157589170663701607
76768630519968677
84365135585751289
320074732414899352
365265309501920730
788508880127391488
778148510748618329
511116754015771139
717807569689797751
72315725724904307
136510853539550359
169663691313575185
951024292207534309
295666322772837456
52730934525338761
301518623743623226
14852594873644506
952978658029733353
103289418328784233
78050859416953922
220332572897073156
24828425073544517
803448751291620037
659315270123418791
393766830686585791
733624755678156833
370474065085100387
456149820505359569
631312692482768503
255777051696563306
787690077218804227
28160069067973262
24475712776935492
78586776189222230
752038048760021802
882684039875988641
802531870590799519
564991507093429730
21532334414478001
473209949347869477
589978897931549107
325616246928780601
297742602505488307
707897176547762029
288864435106312998
76579958378528769
541303991836470517
249061270361703529
475296256225990845
119042441775826507
18295874576715777
555306217286163461
27815802220740689
971396495541940033
519779749131622621
45753633522980101
331270164613342459
734864873268068173
221750282494008311
117645225272578907
129125173434187482
636113783861081489
999881019850187407
479200789654466611
210833858190133530
39799921823176507
195872766052973409
240808349624501457
171130856133559716
2124889290001
693970396482908737
929305705961981259
189220010491049412
155432812328139737
288826709568884520
62555668640472657
597544327211506799
377145065074254752
144115189302956609
465874710373825279
171820790151715963
942683534179605047
423822566260863769
843389797110934021
13180093770263510
614683221504698081
506842726638145319
168412105867367321
648076084910843299
436263757259231849
85703873903294109
27212596478477329
711543833696436109
905643513371507593
892479757770715024
55492466367192101
374813379250163442
317475974553539998
84605289074951181
234342228735310085
733800294037537923
95570131801484783
880688161318366513
96403479263991900
292036047650538409
15885971441266753
240512152841210320
8121715424834160
70190681956624950
372313687699539557
317475837324787441
21655492307364389
24620338566603025
881901113153193605
168379012029913807
638709547951356661
5197538419635980
34807683228046876
391412986275606881
291948203386222543
154473209927986006
184893923163656593
162202042076534851
300506597910234381
386296299877193011
623005936371788197
501749512343326139
248037290458719833
31093923606978624
54801755321358533
996325607461781983
430932308706176575
489629927400750156
42553296796810521
27206535766575664
91910445744030737
560411656085302077
387420494905637100
5846994406472165
768069333897738728
395554441754816100
20603794416494959
240818941074875408
813917356106710207
178316683874710630
288863996495910265
7572406383820417
526007548150134993
162307952961822329
446009491596231961
896430965999036063
723002523179794243
706361593997038056
232228857537195820
976237727426543539
154823451325085088
25180921766805552
810564967872444299
99609390943752551
45848502548453015
131942829747294737
210694858740643621
37777522125368430
317690055014122597
137807899280593633
5144458267564642
397342050501730381
916128455070259973
525994214032363345
189219687537739905
388630125399616
960643242985846699
50149409678998963
981903617028429002
899919765853820101
262764207171164693
779033252203886789
72357829718049040
615056705749615610
118919647902787524
155653696265855482
15902080480212852
908740757466381450
96403481971232667
231616946335403835
25409834152581376
177465272869864229
587827869557192171
45655180509726097
209259417430006597
427766217785345713
975311746231102207
167644479002535150
843389814096849358
391416762051681921
770087742247588579
417390772681052642
951804687734453181
411630112167767267
533771151565305661
216604311185469023
362144794910638941
137929480325525056
35965995715194931
257984262641182056
407507742632117431
66305846854877185
172358446099260919
306799389092509771
704380250013202979
12832369147331047
510363252475737373
929554528655667659
508822949616203809
467429705914344411
932615753728786741
4024836790475467
357209860417870321
208245608913996865
238576512512648815
167763550728049591
828068718346366223
421619640178067810
34807309743215070
123124124141241121
151453765633625156
473291167202329609
25323079037088361
280662288621463
867827155073208101
805447379015437813
348188599863806329
231649004044231961
672088423928284709
110445214580675156
1468201072020544
621562709616082741
700018626388019117
240511774556684316
311100579122250048
35973332585924649
224105390413050972
555520868719927453
21035536457853125
187850960751266289
164513145050442201
144609593749293764
544330964802702
186940259206588019
536360264817397891
67439607734289825
240511788049634781
339307378408804
154606512387574417
738952124305508381
566015790447714533
569983530973926007
421139951819387527
473095445853674281
180719457122689811
895790088318641239
205207081549483807
327943931482595990
933581515469288842
53885835541699985
146626904654831329
767105850488261473
14598588073196689
659403784363217617
99610156568750000
92292355032375193
802272391550114141
998985659193779057
125804527746244379
231616946283824475
852403232173869553
390857637751696807
876551852120716824
34733640104554689
210694511624724373
929293739471304064
2004766909566752
208245608863624080
166737087132140896
951408086218473751
348909786967886741
579156029243236771
577083391566002500
316478381828873792
555991728776754182
52599638858950559
862900916200858405
477969637764877807
439970408438313601
138932460499471603
30678073174071185
224513912295221917
186731483247379456
151947937958965606
245015595678557767
550664398578767887
78029110405695745
375099610111260439
794100213726797706
166058518560247873
592793679770283293
115806470070429010
467095466332968766
22415661772528471
892584698714767841
53742591632261089
680715542635991257
667396714792555621
21000154579218931
275412509581476133
107101002116518130
787600919560986359
121387911818010637
2701810879249863
186967718306368610
37189882406241281
6114361376361924
526006901085950793
322768598486477933
325825112611171720
592018452271357883
591302658807864169
779157073541876281
614739456000003660
350356403707485299
106523340309211
526807073896163623
64535844259722661
869172389677199899
828440124197712179
110342928746940293
864509799187023293
578926197698416549
852603998022198724
99317797061243907
353829308216655719
76099344201568200
405349917674031225
815323425806509243
447922455376418372
550119321677038541
4936022386356799
46503477470137105
30975670704875161
504156372473196323
213634317589545953
260810154092580233
681226916055139469
800152671194931871
486839925845462869
159391054902276650
792272605597174477
96551411086747261
966809142838972622
134238961664006400
15885909925950015
929172142946497147
58660517874442225
894385897595084449
469480669217658017
311858494339683481
908586929237540453
872898056156740631
316478381889517057
588279759220288576
217839676953345306
182859777868782824
131624603378531172
583058875942694531
23318334937806663
186940259207152834
978905292728555612
330549057211413681
54091145277225993
272255148988866887
430472292821704002
23762680033062234
240601886272195182
341791664547469611
332424207646974871
182726301153100722
792161072461230497
235727813707129951
156366150732096327
16495786932192257
674804520322143906
214810491326522851
948677331487843589
150094638826830243
376034478395436595
779543176719878352
261338710141914143
235191253455448473
185344432779186047
208215748580723857
377969662513763502
833834574776652666
90238210183939841
257362210094521455
853693092428108953
760231058744016678
713759877135099664
293877834290626644
229210485050584442
52121546049626856
368547730510285561
161711470782955897
99245898069257135
472591326792086742
440736856883423257
333756594124640557
165025704864040040
209397110666103390
587827903257514092
535943064217511652
806005092190624632
569894106370069410
479161083066229313
34958133222362149
26607867046991581
295665115390250409
624479518954046401
178187233957464113
542293802727248017
746368206909711806
920619891710048941
395636530807042884
337981978288492387
833748647973471945
178282523592030634
96628037352559126
108239263408232503
846200939782026377
257526353535126481
28535940433260650
354220681557462953
615063345274685792
783725206613740806
333092263234015787
779093644169977379
21035459878676166
419514568273401361
605955592221090907
8907373178812161
857569037953433947
65037661876330276
512899840839685759
253551353317768900
765788665947255887
275049068785583713
504989250160118665
564079073076721606
231496482816462223
174888645076804572
124066231286976323
357647132568375650
348414119550659887
95801280897552400
725037057755720463
709249450522757659
353815283451906391
85703873869487105
35452089399612340
537310993157060004
378150820663949419
327219322985183687
1741906634184026
118996303371833143
191573225024679370
432632899584088386
172752321884364965
365849439771476773
320115599973854872
741172572752267601
799129324141255503
4473528715420249
579156036661173638
18014467245998145
910611287568812513
941216599215816611
224875504890791202
10001010001010100
108239260521064140
16756642311502501
303442490280836449
308850167010209713
20711988256785540
58624667195347970
79792280144664052
296277146126330952
30889379233032517
957598617699443267
388323898860960000
210833674399279669
368496257467715056
248510766446965765
309967042480562651
569744669754091585
799129630692216459
327729504160673003
101083035331566817
7414120104931226
488053509323526756
710238923975939929
288826709626832697
851374858758547169
147766170620452147
22656367786544653
360072200594653093
84682070282830291
178188430840858316
310347880937609939
550656608407743726
52929975315108870
111987882655094003
755736167620273003
558271866345179153
155867495037040107
489360587287137703
134997040806372397
636954190597666751
37189012208550443
630250144898808001
437893931557972126
969629023303166887
201584182580812813
771157830368917477
368498178068572615
82549335749222
6593419943615253
189582241059284239
738317053452998749
734864878890827034
221643711367917807
540135235125810917
787115419956935987
26140966752775213
775608281276639123
29309470473607922
92262590126559871
379315287088601249
697366339262236900
618769769741736006
16256634594307697
661610295406433025
231617327870386001
668158960148798190
505606035816943049
844365255153315025
134238699560960000
40938322554353071
58370858758794523
999782894770564529
95428964693510630
181214652422911592
212479450717989423
487328700576844481
979122845998231247
820919071429672336
339738346177808401
229868237579329123
79825499228299251
665441847896916442
201575204563021057
350401137608444038
144139845400906370
900086376589106957
230047843249032023
10001010101000000
138652659211577477
3898134969022116
580285471877854681
727536249448596026
221667170970873163
994005017985988010
154822657130609727
52415804205386443
524679245680961573
511263584465492820
257362619420727583
240512166350711836
177921229192716281
312442816212891280
923027684310694769
69091825252791121
508716076956818123
402330509286442111
403062179243323109
466070754338664067
121450238466328996
210347021655160301
511116753300641460
42107739529705321
81930265600008401
545266366305442369
790748981555704021
568455442594705122
368158315201935829
889463490980240107
308820102950858297
59689096300156254
606792552381138286
242876912580692977
508726546829535383
330517290573694225
43362985262155025
307445877241835603
697059700197376861
202147561832557593
345019638904286239
875178064817158962
505541036581133393
304449509951988661
251136697541643787
566721112694513041
23762762667750019
135277942883744053
307469818599151322
239958614660181265
469163337197400240
428016173458656187
234862516894850244
302037453153152964
237401793447617803
432684575617449155
135895449600518481
330687920068238810
933883087161614957
30841032667670953
236005433141641217
506842540804990010
36065115297022977
953043150808209343
27211409330709693
151689642644340570
504077788602153817
23293494724864226
756208943514954703
556966127597894177
677305242216149
607518842162054117
398362219627285493
264413884272152837
375973781097031650
867246502539618437
50588560617758791
846266702768567810
298705866664329216
15881969952874305
10101000100000000
240808349143203100
56827713358209600
367124295350322677
85845980075558563
197899081576016831
649775686264650337
10001010100010101
135280683392284261
348217488351795365
158739919374643631
619236338208351917
560175068900148912
160041093838260497
374479714003306871
793899105514672831
229648269500199169
36065080937316384
477294158372933632
31550986546601877
786883659571166161
44092279267953073
372048219250407025
170953279934715479
168996855298857751
281745550752468101
18996003243828121
179366790743705889
19098760034415432
395935990357591157
253378896057197681
31222787690783811
813072141977064130
958596393782059171
987090460176168906
292786986840748613
317481326565113920
597022073011694591
644641289636513453
659931533251613401
326184272257657787
279277281715225231
135256661037769489
48039476342556312
235031676454958491
99610156568752500
210195412559086556
521085053654510687
18669161346184460
37190981884314624
72255008730840776
685498200494997191
59689245533301726
124501334250474119
79792958367739254
243469925049398090
476249652058149226
268461903589116901
16843040215386121
320137297017185523
35156881315334173
37189882405192705
768785460474625787
699748682611654752
638265188538495527
851166922950687643
565515541044347899
308820134342393856
182729721198932790
564087257390402088
843174109289708717
21925134759675456
62504756940025
921978777444803244
929294017758205306
24122803274307211
517751213478197467
74070300288056837
597710998927468082
548599542523314871
617913284008947580
34067452533802650
973181364123201602
43362994942417058
21869676568696010
548070916579380043
368384793423019749
863380995126049987
944016739192329307
586095015653685903
72313939931039870
482723900483493709
467235794421669289
2366700633318757
52945838345539130
27348647358915961
104689572006051941
858477993705755509
259864685944306277
24128175799745425
638696806600221053
914593885095642649
36201766479800381
814830329185949471
42032048605530481
918731468876126481
225989216315999362
53718780340615824
458127034699572527
741605948034386009
288864430122103792
223958337923762689
433192141537715570
827528940892335727
345796959513981089
453594152545638132
579090498953907165
285931459119310259
18567389601559681
579155346713326522
66466063085143807
27247076193469456
813891742751430819
155697888586816
549156378724110901
224317022259462683
669353985636827947
161745314571140813
97839806485570256
904779343277259887
354293495079250679
556495129266566177
313046520960224921
52120140932440647
67603135215798263
375635088596503697
939863051044125337
260354793986894602
529843825078457423
611492427157535156
257984290330806930
259956516126507209
228252171475353600
658684384198500361
922803337523517179
740711787832907873
579155346791392488
60415071417300625
920629347233779442
288826271016415000
20716815065785475
283985136047659777
100001111110011011
679079957204543303
106869146113366027
27815482781677756
928733832462419539
823614107771143129
753594244232799869
187084405511904853
727498556045397082
690075954456832663
169663691268369814
40930087100343001
744128359603308749
110001000011101100
99609375000125051
208215752762836225
830944014789022957
162178484556415909
343388542454643041
368058693160128101
973308466902160901
17730411680870465
600038330319361543
7440186356570
303403934063279672
965615638491408969
275119394583062501
161828205254590204
573060347275771564
833507070110024627
18018865275736128
231649008481285000
785927093750907067
734865109430236134
228334503671742007
982202709471635430
208483837146106943
713534671354696386
133914833504978333
449301111504719077
73354318329480552
586017596371482419
354337726476888360
964403708462284219
416672613824352561
558584522845498744
785436733436726597
608802240233335459
944535505455501517
357892465385935427
605507899537742161
162844096180631060
592395284677429249
150102271742789241
516965991310047842
479407339436625626
416499166816628622
65644642236106817
133039410484916557
426381085743386923
72255008732177112
424251011826546060
642382359894494161
759753826347356570
520411736935563177
987886628290510271
663732030356107573
649132372358781713
6622049307200626
395937923310580787
638609532323427505
120885382839177009
369648902646953906
476208526468300817
775392967516716569
403646977374292469
246447212293815500
432684569377881276
662691364356102047
366451007618106721
620335136435758470
229613289486400621
138969908785422401
717631399147073651
913517256994521597
838994826971025665
210488998818725309
73967087734619191
846281096520609649
913011327717249601
591405106048370329
469041663976368976
847818700863714949
10933385673244247
451285283423681219
294847491004930710
210906160151627161
31658951452640625
419699265538625601
505830204645230917
36029930890331136
893616925905361967
730684962446464501
397344139881745289
238970179025360644
119042424179538705
294170688621862477
50006776745424451
206839514860219501
653860791143421737
603488154801845001
987520459421475293
366451007597572023
208216099879348260
366029800733193360
735835309997816351
421138143450222756
61991812543496221
658467006768545123
911449101427322177
52599639088399342
59689247605984302
36028831413305376
261093837479416663
325830323780457601
355554358015334857
753284649044075626
591756465342026
27206535746420122
900549500530516523
555623231300035411
135895711785472080
281640203622574903
986732775167800645
880377313683528533
20713720835509641
312805207822265630
155867223440928412
234038068241860532
753421420877823713
97174433354477839
494585059813851890
769296411641862253
146536032931263505
473016266716530180
913610454018431698
84957138728898242
162178520659868287
205953739793392001
140421941680419941
104229302424325056
241375996055096381
282811265157688454
691104368109304384
57510890373242
162815058372110401
201072262251310433
946839159615592081
260834847920644761
391773528136637190
600159557781217992
106961395681579843
245015595599324004
83986760374628942
296047243764301933
723430695708890
129986389366743757
447024450302474641
969779049331710577
878012661416413248
37155831904501761
23768135174792844
571573189008029950
199803478247149152
258135579622850257
621479640684379237
704356309886756183
88287302427142241
882716478705568217
765561265327552933
68121339300422500
997446408817152043
175943707993668693
681855910099236881
604832520972960060
889594977910647756
817541422670100756
202133897120511226
35810146272372977
50706347165067527
19909489943384064
333754956877499390
317690058535240600
427929806370871714
541356051620043131
257327826638513197
60962673326783413
419436957696001640
200623141391135809
167619858124335981
85718516528972481
727189969100941919
780026444088229189
747124952262269881
579090498953898422
831563341185601
82491636228212756
64953241643778097
277582829964551301
186940259207159722
603310073894179877
67469554888583297
366436000204475072
27612602073851589
821773805416362287
518346879561562687
407161034199274370
555608842853417122
505450193100714048
95500311004312517
921981036956617303
4788458628517411
256790169694813041
95182393750273600
550337216261782528
178188430840709439
827535321176019857
692534004063151200
84605484309966080
295666267783584500
283090021938399499
66698818241927593
520411083063301144
75084686310943200
886327972579904762
565752583616024433
585348354235471451
699823044600791041
724558381716038587
293037493320549377
108239038171148196
591768037810007687
286768337090996533
150117798006306406
162195956912082829
325830464618118759
355997190058466237
50175223795356773
282837825188471873
146371454806560833
158919758006869019
961852128411322404
582982951319906007
182856167893547500
531441022599837900
190368523714830847
801226148801423444
608075716502294669
32837039817864490
825400285629932699
106868920950299664
144196789594553651
553419570759565399
122815229835101521
962508809021060890
286173306354242596
135277942825004113
16226193830625
845110793794105841
569066851515242677
439978522720891516
841060009857457180
43599984056312464
375970397969030166
766184976353925184
273080060725743756
3853512461675557
705121071884490277
898416321141482823
433792168334029639
890418893124010001
263411080837035664
155568117694686677
636954182940450720
917095298941610257
482857077576989125
111010100111111010
320115599913877593
6978172158521570
50172914223444545
403121353662980437
964094381808403320
449410594705736591
788483265854101475
483076388971743931
736435411469379151
98757972887217911
855712224598595933
529317597400955581
783197983199437783
67439607764281951
18439868938923442
288826275999973186
646957628888802923
709591830248059909
768149290533420389
845121532307402029
320116064317972120
597185332660072603
579156036660351796
187017714504880705
526067071172198452
118473249224276561
51998697841476097
46494384179982698
58871738042888621
66306446408613937
102726256762425209
194312652063391745
164821137168322147
288252715706877185
465852543246569597
352089747692937082
177917716780682872
963909026948993441
314064435908073962
293637605648475156
604661760777819661
31544363879195013
551050702210475236
232967297287943681
58658643024370760
354235507689353703
121368950957043120
162195162721877208
503992158228783799
99245905792169085
208215752713049172
430806453620134355
22319331841040482
245019940380524710
160741988483595767
579090491692111346
101111101010100100
562472413084628441
513980618256941056
149286395301706549
336533819305622501
546387320764508225
148734694238583756
257362210149222270
63729980586496576
800779046362254653
930603796406305283
406615806054561083
633604286828520433
312478669355532809
620173240428870157
707531356738545127
870277971942634033
572994809645740660
579625175639329397
154823489233516110
472883654908248591
35973334149955998
211316397498262057
391725161100008191
350078577273453841
210904821685585171
229591194424659762
215370777771927756
886011847433938609
525952865986618871
618933966939585661
3708860212343423
150611359953925
478232722228105021
94985359108211809
294212837257053185
854351118476996071
210832544068337899
299067903956331877
268790935644022007
10000010001000101
633808663598200729
813141667578322
97695328443877551
888883425164148736
969577205700014340
161011130448396006
52599143244392642
692534786736890880
767351000766889027
550329226589204284
606794341104924661
67430397493134132
681773249978216701
472217760964136284
332078771388864427
43363430549731133
717378009382189765
255812447418902501
669377432184939466
279977824993132177
917829177326944097
622312138535940341
504038244804939598
26922415566745741
14822431354718465
956547831418752647
131735109386084101
811680873301717427
992002464406172026
70233075577150932
886270426024024801
296249436299155131
237420456502868100
834141051526466756
870058952739978007
417843133614003043
709686189559846280
49784049444678163
538017643629859600
257565759675660467
15603864589841809
899971175436140179
330138350857442241
787690103814392736
654091187409528049
516941191572028247
38044428436446161
46494384154565976
637892260640525353
253702930416971873
119871043018509361
125621724698697152
251184268520571829
147559785423657883
869584662574589991
163894996469880900
214738188897358117
34134011879136007
640844404772177279
99245906100610334
5433277466571361
585186518397201493
74767075198597656
46755526204588644
244047424445478547
130672503418737361
37445729597838082
922837910569651098
429922881638464000
21030634230241351
452757420413401841
357727088633296900
977841263999020697
116744455150290161
119089107124174356
354337229432142268
839094764923008653
502635043793408341
11859629377607550
720541671559494500
5029724695984705
308721689385417281
580340973546869573
139419364363839650
377835254737189831
867007759559092711
454873122455197429
308818375856008760
30953263917547609
701184818432895913
439840126638478350
10101010001010101
72339073579155729
679992018825982813
967006212014016469
73362784614309227
172692623591520401
166771820488233070
570923069586896196
292579487989505929
725040201343376106
256178739212614730
118898909371988987
136658679761150273
746703634631897647
672912895942375057
318515403909084410
50589924447105384
496738997275425425
602359132406354569
809089527995521601
350356900751526333
178051193498187151
34050628920207376
968305891370848463
45848502523036293
46503349395269976
605030181302861177
50542150423637763
485771210788897882
347864924138649613
44953130362917671
64714634351866945
696965609387752283
438234073623218305
236879286030158983
314928009369180901
518764076461014583
75084688652765625
43991721665425296
938499743861899260
7377726840753026
391725698512239001
67439769721773376
20135649224495657
79792266580204900
558313645026240673
125785129841269369
657896054079577241
799123176044389140
7552106120248170
815409028713493217
68540885684678449
12231906212408653
797314805312947811
511626522338299373
614739456777816000
354337720830078750
155568386393710920
738512859863640227
295101501795024393
62318717644157584
372722180646575999
177921134330132453
99307769119924750
901468910163595187
167619854416386262
509661966340382361
79826177739612151
42440795095107965
131067940352694619
892073706515999296
123544158602480100
34067817899488126
276527739019089211
186570166314785344
106869149000540394
14990161220625221
152357086172903223
894602378343847953
457362657763393042
971383395639201473
544021615111818947
793386853917625153
913610454018431599
744638320051183471
575342367871367382
509911965192008413
406192852409876239
558779175120516812
791857925148040056
27612603444132306
564079267833819567
137520527798785610
472217154537495645
234341851533593750
727873395432096593
745833810564206913
564311036348068249
269064557821636943
401011671832913131
253825631010815737
479895131296740349
339308491639119647
751422199226438885
479965108507236
861128489519615411
573060347197687926
18018866366251072
636953455504918751
368498211774069001
104934030440730037
302368160668097689
36497137227681877
333308365492193317
229903257448338017
439698444602237999
428981555378431933
500958585409625874
108256826052904075
256927457571854762
349478298335107921
1737961089788460
718488303222330343
548934171775044562
262894924708572801
280577858004013651
10001010001010001
698943575531792909
27156786736337733
3227514263398656
81612635096947847
25804623588606976
317475978072224440
20368186045859717
378596938256635429
291783663141042383
95151694449633900
677725048442533507
357510176366873210
54014391134071333
57090661306519963
512556619004845812
156931177148869202
330994081101130411
560128164553415237
136723895600421080
27815490038076752
500123025494699881
100100000001010000
95151905613945335
303307216200977016
186967391365988352
396796734908630857
133091106763121982
5662991081248231
144608585455509761
896796395401908923
359214059822966983
174888645084546176
583419696734589173
375973781097037465
511263584453375400
720446351557232687
197580638937691407
678795747956750072
604872756835635600
432684575686777687
626812679227320576
504077866913418386
432473765897529479
368819336910885462
758606876345728922
70190629478710197
81930265603200401
864932521163391557
717378239921595336
169613892528440849
300180251715047609
253380419004700625
153882776547493361
7443710030655845
881396106915857
432684001577212477
254794817785798061
27612693882659628
788509705504861507
115886301033235913
876491090356175425
77942973407500969
64792276811379441
96403479299145019
395636343501829969
906937889352691
813496433798715587
169663999028196409
91414025873625625
136256938690312667
132396292957164196
114790675874906530
24122803293281946
683176956071407250
244901742740883317
518634417979045583
2362833762993132
253306328109339025
76498122975626540
665721287937971721
67451759014568325
490387896349892087
367691071049448103
339721924259530451
79792958367854501
929808020283516702
985142360953009297
550656413650644084
596468199185577413
430528388249717642
130353964166499107
234341851586415811
206070388679840483
972540025000427520
111010110101011001
468293159603623683
728565800899329121
117101499078127370
347117296802306323
559732889712563210
121422374548329457
40361844134714970
964901576050002817
50588561947176198
96551473587734411
167671964685494930
743481730149567533
922838842442870002
940320007251330413
119407983340817
475711883060533902
238737383751389209
52599638858952768
166055595904319999
509627728918650309
733939487916101173
423947365247108837
935579143899147001
144763650202539373
54010473330230569
317684703004921434
839517705973928965
705572855962093523
162179278832387187
182652828018297462
147336060055211716
166680103866727262
725228816589092106
908989098502022137
542865478981917293
177518857220213600
200300940008425152
504061833366672853
761353095344917009
556716710574025
4281698066483910
53742591397932579
357078845915669113
150094646145304983
1406130377544026
316478846232952833
24122721872689704
155774747057511410
717368557269598963
365194945009949581
588586625069677681
628260823226711189
309944183349625626
27197687472628816
244854724360583610
817463325990136226
363326987087283649
432632893275953825
831493331977203845
695282943511910961
662737215359307169
637780113105774591
717368326599500395
477349336678064493
25812405327798421
520878404454159844
918977389958798477
66278266868185344
863892573160781113
727801823949521603
715357483882179140
689409410312083841
443901176984519213
81920025664000401
931802643015861751
864477796197626362
467087393238890625
303765409286021443
402977474797922821
968825324404603723
75084864258240076
102916485465522043
84612468239186177
430178471938625601
994927145637612581
163351336127019061
366030300384075719
84605289074517905
111011000010100010
76571202016885380
414316704664939639
588728749315459217
291558834017688529
517293796719270270
265441514634537391
485874642192232656
234280321738756451
147336040284739905
838467054618608213
225607368339651527
932836188670140304
294160111353810944
308651078252295487
293103776826458385
672875115152277251
438024216103704240
156422575952979449
855415158025393111
959920542299641
826407049919283199
62084204101563126
880701493926150625
228252171953111040
144608585448198144
64925074599247920
154840167313590970
484511772941302401
524630296170437257
564158252963259197
33505017652042843
375973978845997711
929293745939596092
949615143961950156
166006527995778241
325616380731267717
36029896531674144
35973334127293639
431366021305713665
929808026751810493
420156944056985593
382768793692687656
492849338308740973
31974819838360859
989270028536097025
984934231855120576
550329031719074203
1000000000000000000
710191851417660156
657111885619230319
135916683264006481
587975766944333203
10108179752789009
245019940461844977
634657702467640490
275274838128678863
316478381828866137
585417403366427792
417154971032449283
64925062108657969
108256826052429523
310536230529784380
844756060059316987
585228252784519877
135873484704582849
878073537850344024
238295181779402753
64388674770583697
21052721717301
100396439572176785
111100001111001001
18295943279411265
555970888118778916
945215252700785157
955851110196782021
520471253075556793
411338672576752153
6356380975417225
18994170753674282
463826384433432020
224746093102883293
649709880866434731
169453371163356737
658746130430436489
164258699159026
925129393424797290
382421734253786923
693299144583181267
877170190635438737
455015328358843589
133959320463079123
768069325310398567
397736871515579556
427166309538081989
182726303718825798
772397685588712225
121376606596993906
949390759353289351
144119595920560201
905493605503161739
890459202548187499
949207419676319593
210832519273423633
830638302115157801
108403802007397602
505033376291875883
640237157002553958
288864430121452771
769506004319643629
323426791964587537
829088135999272900
600906640008838993
233348055639247831
23172947207157877
182726303651355966
10887379322528630
154489853786998905
53615646553977730
235467624612004097
1031550924948523
221158960689571183
150102260908833772
84188112016775006
119851596021568480
544175479354245377
354337726414138287
146641455552119402
53718769561398333
789993754925275951
8651840918249257
669169371596647393
97657046881375050
769128974920347649
257362214798162971
982256234769312199
657889988349981241
201691175352996252
673214728242668831
559128577469486049
52720901977790088
590255257040911225
5039173619456770
704720483047646629
841182614151997400
40361844111047901
1693075362118010
162355961873890290
150094921256366806
11207401506815241
215820925861700172
320533830175613185
980703433502754807
581617385373489541
640237946239340512
110510227480577797
851967849512892025
352124301156990000
303454729289527537
435205357311896617
158329473317981406
95167954137212188
159664386179568906
167209863241389703
622171074403499707
665441699491816338
21030634248087815
288826270959132807
955751141117855083
99648437500002551
895487847516828949
814337594116594250
435030719420278951
717775223167528387
96387430740725124
42095000420357
3650264760291241
486197474606383021
630035731005518567
671390618795725556
99246114928148760
66545357967413031
61992797851562500
798242609989177600
692060418882747559
18300341342961728
835494051626037301
372482166696075241
36065116337210368
42440795095105894
642321377646606269
689999748952122943
353814783226004580
582608468222143007
416093721782746171
385390573246233119
34067826014718151
106886711718761364
322585410665994870
56571594992665601
31544264990335637
903415440929361803
173498470139744237
423343599135409307
559084537415715365
257327821933599655
186940255315570511
34824506657205195
443310637250517251
563884116204011873
528871601316726419
399265445095400893
822727572633544471
811812301931033671
847684193098545222
1257020861160100
538455170881873393
795060636288284256
101101000000100010
316478387166162497
977538538046496197
317684706433381638
210277457024040000
936542841880062097
335104413543191179
378309533462484971
781485281006283283
289908147441678482
200301007124406672
16811034891890625
325825112608856797
368498211763331056
176085355297994291
842256287238497866
157737248741858610
417112594919964533
62765786721089090
85740635059155342
21864807906976226
672627104232971623
438359966800972920
16751244658133401
35459643671028009
604661760013176000
83201731544598587
574558797099778624
214809152401309951
50941872873285033
497803463155514083
519779749846341481
99388774078933535
638603993865825639
977911970263067591
960532110361250023
387468856035900000
54837220029332887
519532284927247042
739877078857006609
293890959870517881
550337211511678246
301309153903717781
23762762668037449
3026214686914723
25331789978725019
734458438046384857
65477672631690917
306370890195918026
99649234375125000
285544159227246304
24748951865456016
99999999999899999
485436628735747801
219165097492747261
494825892335651791
258857454721729601
979163798514135364
391772990855618101
746075920107114496
601773434423451071
353603632956755443
726996234054660407
401013677639806057
2663634833251397
80318689900092484
159680907213943429
590185304393312123
753603137398637573
285581884707392676
152494629098438450
685653632547419231
147335011832836101
5799974402098969
374881415874539941
734855190616071757
498718467734133433
35973442068447519
550329231339310247
720636718991320279
129776608806227642
161845719039767091
234341856023461711
471079888068032099
178250668359015258
202208294078010991
66407637637878437
526006901085942144
417992828913811969
936629627255954461
547832764490742233
33770674131507347
826171265440396609
271310143179732006
604664560137603661
818738747002718921
914596526902837848
2620358818703040
52720903912334400
131723263859403061
11148710336614663
96551475480065410
325089471105293862
220040368055259842
