## Seekrypt

>Secrets encrypted.

### Challenge

```py
#!/usr/bin/env python3

from Crypto.Util.number import *
import random

flag = open('flag.txt','rb').read()
assert len(flag) < 100

def gen(bits):
while True:
alpha = getPrime(bits)
beta = getPrime(bits)
mod = alpha*beta
x = random.randint(1, mod)
y = alpha^(bytes_to_long(flag[len(flag)//2:])<<0x1f0)

if pow(beta**2*x,(alpha-1)//2,alpha) + pow(alpha**2*x,(beta-1)//2,beta) == alpha+beta-2:
break
return (x,y), mod

def encrypt(m,p,k):
m = bin(bytes_to_long(m))[2:]
x,a = p
c = []

for b in m:
while True:
y = random.randint(1,k)
if GCD(y,k) == 1:
c.append((x**int(b)*y**2)%k)
break
return c

a,b = gen(1024)
encrypted = encrypt(flag[:len(flag)//2],a,b)
print(encrypted, a[1], b)
```

### Solution

This challenge has the flag cut in half and hidden with two different puzzles. We see that the second half of the flag is used to create the integer `y` which is given as output. Although there's a lot more going on in the challenge, we can immediately find the second half of the flag from the following data:

```py
flag = open('flag.txt','rb').read()
assert len(flag) < 100
alpha = getPrime(bits)
beta = getPrime(bits)
mod = alpha*beta
y = alpha^(bytes_to_long(flag[len(flag)//2:])<<0x1f0)
```

We understand `mod = alpha * beta = N` as a composite of two large primes and so we should be thinking about this as an RSA-like challenge. The first thing we notice is that flag has at most `100` bytes, and so has a maximum bit length of `800`. Cutting that in half, we have the maximum of `400` bits for `bytes_to_long(flag[len(flag)//2:])`. This quantity is then bit-shifted by `0x1f0 = 496`, such that the integer `bytes_to_long(flag[len(flag)//2:])<<0x1f0` will have `0` as the bottom most `496` bits, and will have a maximum bit-length of `400 + 496 = 896`

We now know that a `1024` bit prime is XORd with a (at most) `896` bit flag-fragment with `496` trailing zeros. This means from the given `y = alpha^flag_half` we know that the bottom `496` bits and the top `1024 - 896` will be the same as the bits of `alpha`.

From this, we can apply a Coppersmith attack on `alpha` to recover it from the known bits. To use `small_roots()` we need to write `alpha` as a polynomial, we can do this with

```py
alpha = MSB + x*(1 << 498) + LSB
```

For some unknown `x`, and known bits `MSB, LSB`, which we can calculate

```
max_flag = 400
lower_mask = 496
known_upper = (1024 - max_flag - lower_mask)
upper_mask = (1024 - known_upper)
known_bits = lower_mask+known_upper

MSB = y & (((1 << upper_mask) - 1) << upper_mask)
LSB = y & ((1 << lower_mask) - 1)
```

Finally, to use `small_roots`, we want to rewrite this function such that `x` has no multiplicative factor, which we do by finding the inverse of `(1 << 496) mod N`.

```py
PR.<x> = PolynomialRing(Zmod(N))

r = 1 << (lower_mask)
ir = inverse_mod(r, N)

f = x + (MSB + LSB) * ir
roots = f.small_roots(X=2^(1024 - known_bits), beta=0.45, epsilon=1/64)
if roots:
root = int(roots[0])
kalpha = root + (msb_part + lsb_part) * ir
alpha = gcd(N, kalpha)
assert alpha != 1, "Fail"
assert alpha != N, "Fail"
print(alpha)
```

The output of `small_roots` gives us the value for `x`, which we can then use to reconstruct `alpha` by simply performing `alpha^y`.

The second half of the flag is much much easier. We see that in the generation, a random integer `x` is found such that

```
pow(beta**2*x,(alpha-1)//2,alpha) + pow(alpha**2*x,(beta-1)//2,beta) == alpha+beta-2
```

This looks long and complicated, but it's actually pretty simple. The terms on the left hand side are in the form: `pow(p, q-1, q) * pow(x,(q-1)//2,q)` for primes `{p,q}`. From Fermat's little theorem, we know that `pow(q, p-1, p) = 1`, and `pow(x,(p-1)//2,p)` calculates the Legendre symbol for `x`. The values for `pow(x,(p-1)//2,p)` take values in `{0,1,-1} mod p` and so we see the equation simplifies to

```
pow(x,(alpha-1)//2,alpha) + pow(x,(beta-1)//2,beta) == alpha+beta-2
```

Which is only satisfied when `x` is a non quadratic residue (NQR) for both `alpha` and `beta`, *i.e.*, `pow(x,(p-1)//2,p) = -1 = p - 1 mod p` for both primes `alpha, beta`.

So why is it important that `x` is a non quadratic residue? We see that the list `encrypted` is populated by looking at each bit of the flag fragment

```py
def encrypt(m,p,N):
m = bin(bytes_to_long(m))[2:]
x,y = p
c = []

for b in m:
while True:
y = random.randint(1,N)
if GCD(y,k) == 1:
c.append((x**int(b)*y**2)%N)
break
return c
```

When the bit of the flag is `0`, we see we append `y**2 mod N`, otherwise we append `x*y**2 mod N`. As a `NQR*QR` is always a `NQR`, we see that when `e` is a QR of `alpha` or `beta`, the flag bit is `0`, else it is `1`. Hence, given the list `encrypted` and the prime `alpha` from above, we calculate it's Legendre symbol, and build the binary of the message element by element in the list.

Note: We could not have used `N` to solve this with the Jacobi symbold `(e/N)`. The reason being that as `x` is a NQR for both `{alpha,beta}` the Jacobi symbol of `(e / N) = (e/alpha)*(e/beta)` will always be `1`. (The two options being `1*1 mod N` or `-1*-1 mod N`).

The solution is quick to write up using the inbuilt `kronecker`function from sage, and looks like:

```
bin_flag = ''
for e in encrypted:
if kronecker(e,alpha) == 1:
bin_flag += '0'
else:
bin_flag += '1'

flag_first = long_to_bytes(int(bin_flag,2)).decode()
```

### Implementation

Putting this all into one script, we grab the flag. I really enjoyed this puzzle and liked how each side of the challenge was realated to each other. Thanks Tux!

```py
from Crypto.Util.number import *

# =============================================
# Challenge Data
# =============================================

encrypted = [8275388885893443678512608174583957947590309348942674029219139766033877421235161075918724281644541406737426325546718855424922421027456863273458919998545467221054722513118900731853582010191616529523149239211823326097059481394982405216805736026843496287510870984960606881599659029681463533442028850871083557245708431081611576195650081295754646614223075146244172640035745595201096575799953106958958823961745347809868725990094382564782459573369267084258180629996951381010335197918437224707631804268793231007408577148700601701733125925778103081617704618150464316944867015215136115148852858427081632945440226864874485969036, 15024296399248205807122283689218566390496831326714396409792698800299803699301917950571943978689203513033584150094505457016262896601569472975694249735868927545747376155035355172679069869391576487683339945053025561973538233598962491053616062448590875865853120541090533979077586759609748116789893243566792470265647394997623728211496444114524716174538826025238226744167882966331979570971147974439013520123807853304141074922819254390573278963951028965333115123709521490574568657424853506100358492167003754085320874172675844872523407009636278408648249022482033283263545795955048395340172016592888042786341560412169364360001, 8306804146139841703662296481670028512569861001982166156300978867964732343666844421908720481508208344128833750429002100096384052015432491831892049736734497300228735845740855915814234072220578188540365762661298990446887696869442265423101051767761814869830227497381321288755842752400643084896381346770315602771712252950207458333740221122576793634691535640996291946630387371059710336481841029337199092184199195481031420940512259368428183199169604313686269963008566029405931099768575763578093273177788903942347613920927708476120538300169317081584387486689950862668362006780346364210752321874739147678128956856905307430939, 9090926834832880131039466112389521759835027092102666051830975522775416131941390663603517122663639030241606461726928803519872080716380468494566458111754697844347834330110848437904571565293442668818757561252515736911844854788968098131116050728406756552916538064387685819180609776930078066840543172090378828357305032923534421583824825498146736224877546038077507027963258714149451501988469802610847930077560203513625718011204415608918856306514943906502065352408657406521500840695610237528570390850631051297301958628398021610281666561743392425150858199215990245235295138526825586977098559233597568287319243164987238349396, 10526789517277012439437477478714936461723275233079469631554614785653564207198044048929502315168773360705453770844386240881946111126846839174151177062492583563520701673511065729492968109502375092733986202426882625918910004477282670061892964406000653395900311729160009502037803343946006228979422398747388473288813597837921732768366801583756444889333300852297214868082499035054987339851967907090518876310425359250852198141165625500908066587940559435100607106532015981542704619533823939076229330235810171674557802079539863155524561515389817189885635848380361783695990224919666705106139855484254131956974093838150059627236, 9003753733613904486287458171339728086811199429996510961739387618312464105866856434273809012724471190111990704832234029121866642971810167675626855816956117520083517665771956881566340780821231541293176778611919702977766091857788798237265822668841618777558403360079306181115507146118237268401892952346082420409549162066462494546747598186867064502018101728457590400800594297072899646568026777506515853955050270441919182744002186040048976480858578894267458182096893848190609301499454615236154959261033187197098254571487727266947262729259719995265793914875270755301423038377698368020094207076171948172861958762760313218882, 10068658465473196270532475081894763591388192479211118027075487006954776823815932905382212629741136410019740441174914532976962441769960639588585947341379281525535404431111630135876546483887325907794071134248951814972629532764951869976271149237195543275466887093329843083399333768459948777790197819519649472898923114672624544076972927816523704276700807722016766315255036268147235529713638221779340326869921517142718033469669512937584217738178557790175375234407553853715689690070913626886156078712548648762981345905651060689958956808012506429003000317965674253524689184998783775751070497391445507519385786969701312249770, 8214810102194933594308069870478868225120076730504905518089087491973828409772738094104948640593886231020082757238243088298703760897031833051384729979196236196281037948707784493651795698484761341791837718155899264459216789782672100087596860897016195663248920660881014928850728908469518483938282453644668029685293765059050840727012393781023421906701085610700861703691833116468441036373319294213842117029540254803688164909913909868344334009471581518128153693297667410025638408608151514105372254633557289818450411361991475433531918919481137733164420298475716965179160550406340764267103292868867371591070606766226368312384, 10563384197118850441900193742522804083811132573837116217421570161888194408556070812875963319385759644134349695164901373327564658061652956314523574524858331080588808598125699052287605106201714043807817428043840087002938353845272396786298464072596481608009560488803633732261103163680918048927214992238818695123297980261564892408997021970610477765905671859944084662751303295438306158980334425975416649676628397645032798025850867299637062506376544547273701019783357763493914629835912448221445020936247842452706097884936538343691715463345421246864867121307125256476296245978184944842618441074671950346363986928642867431529, 3713782353555722602362010136405655520634663369580450853233803101083194227028982815581979442401966342688910148940472608845574797906630957771315963051052224920239010840042783700038909407468294955189724340424070183668085470878889818401857555483532483861001531382206901756791757661119914172473009261351815830944550751476990919930639905217202021106029596949501526991563758005356530120805564122955887170644001082992726258118351274254891995600317931435092579918036765780973708229340569281331041507397034175054167104124384944567981951563808716346233032325527604868569039009789632404139834354000494960494166920340102966477652, 12040023514607804225177335042780297822193547746732553466519151038912881078719897874792464408208347411501836057564926672269108734506545012430732069572960021261596112708026997683925081006646145366329389463991922779921675241812950844045889879479488609091969504070048031810239386688020394190896052330570608055098639243235625010235286185137892703432034792607936780969312252579917965350047449736938149753284853170574599762416700505075564239889486104402932263705341756606353866498729802615481414418542642085785813871503187709201327033479742930293511274076842779764083521469523134380202417566360604214150314597538775733094449, 4182704370322682566151967954208044093122433899611179433372773109642053644911092443070790653127271118424079480842674550632253217724454658947151418225883350873513860635680863150321440789480536414299571955505917769386201884467374326169106654392650118369610231355474229397414600973327860604128674774689646879819297819873514098852460160506512637179400640473917613979187172950733644503446613824474695557201475542639258478377647353778368527904475448263999287059425823002967619091654007184437307506239911395390724423421418929014688134975910290525054222919349601960265551396389808438794942485179059420646373328592562110875935, 4508157810377775057054934788581176681995962182195041651328738999986592464287575600715684275536558106039740714013972015497525136854128359016735231728104700742126995515000462057819202258786397098323015304576420290548560985846247230914302207611237825230281512357301333861456434604002941370568431718438304397993106014901561660714217778995969676367227729922234937595718008538102109056077307406903861612355089521471710135108714155082046775442728609020663950462867181860090595860127540827167103662236832592398100364230583869427792285490949436524598831956240220240907443660968456011020043632159227448218779862179238966321095, 11833836686794762493389692187087510136787100711221775614702238798372740339365015352106794720795072164791096760868835081265903098750755678972870578961427917570042854775096463138203780630379944995116852385085676807336079105458262604724150544983983680327979969572509186605523570417314442028748997757117402496428024597221123274971781806538907058582799105877279753527712077067817158080698721705008083382019042167248303815089366448983787084961368664566971502245945613482720039366747490938213784461659886532030988465916568032678500580388199557355827198904887485892236318494737576705141932803203753013278803086355315612551183, 9390095431026387834907673966762863332167841318149807124747496464189586038816758837037255434612736962103622044518634284148626919043575987992536043474495998254021043120187146765915745813716554874074483388444121676892472209976591010742020191195424033231885804546149263187827427242295079134513915454452479621230233448045464822891387804481796809579986819236273615909669010488048353973130154601370106243945659106657093087292318425982282198150305988679273988227357180313181953499890685971493534150284110802400195255863139638968663821481370007171302051388006212073511310495825495704602374984642735302764219143673669730559603, 7728868260097165258325512162962631682123733861487313442607852797918905627048797803508624254041009454363876137239781888812824636850880843157737058756183279779491022770077253568903973764963779014960229687098468556201912722007789009072431170773705177867920619390026701419087738421459966376817190718658917479912717869359536509675804300435230181896693936625733588808268139275251298351830392077411953476646681813541761652875492379859976230746747161296547953368828928660878504881275200549777863318450589479881637575104571789854005973284291393590410698338671978623530380813871981902958922137381094638485707719414917357009187, 10189927468040444993092586238703188214739132641516794090800041086364416360111257273753798484510942035289590486455984400350174593296678264236395189494858329795895824316008784030499984626523776787057050159081960248647967212717459484544082171685517415308767238574997212899452419105756096094543327981607204104137165771088778934801800642833430734491860524967876506229910351582714530753726270826171331426795703936458982046007145496201419210940368101786905862729003582892547000086022063991084745656657098091868557059922873137544400480190674901990237743439890808644083437587231116109855979440652220445592237956414058775070151, 8236255615288216737233342137062975563981512400448231144119013745026457396491150203671046550780723594554772587640757706132817343585912947669427757618987404207970871563791693921376286756061916676013021114894910850869347773818111958270870400028553657835178730330677854701702485060066578016912933205664230906064207875063139449929940796392586248219708958813075524811726954594642540262483443852595011554617713244371526401374774976888324294565456082067042857554516785188551315632003184886037774810362890645748324339409532729015116181993006076770619610663295692762727233056760800856291905688633850601016380834674290593033814, 3473198504170475545876730971456469563763342907454567276943754514011700006770395061621347422934046856292986491200899333031919410153559760169281801096803341507210554097181790112581399892174192565302155827890588668181693598484813112002176762588839108274393949813482983180263169611985281056897218601236733471927817801394248631621953026748465468104208319575191434559851824560567244766740867270643643080329496143421079763142847120271215457358260755841821297601612337573428415203026913617528529859990276538451041158949438356428116331450305732069080800157660087548860430662038190305327250449208144766777008500039860721229660, 5610735858540692651784723977717771076003573144440467912274200237699776316290955512277741145007783383494320363708439910220931439860424060681363730189347716172850312120665137811299217485507087730501693529595570764350491687116062496296792844505055171586439254883975162728236113520266068839032253295422517685040097229274479342431866261785603890137662762163978517720761085891749977330710053394647570278885227415573067135591893761353822036939946408487025978400577747834622220826463045374395813113748982087467257142559238532190393437414671349064393074880119291229404056767579678618604180524565209174089839044434714561944694, 11176076667488645406745652327171917716446417194575716127411164810986517749107802972937418295978040643389940316752610061136434837719599771298836271964842150829484308426927316298802698366195957896538751503612661852457519898398952483047063352436661213676754892680526775857714084006780297348656740092391036307237929318149318396079558263637905063980697091331180315812288287348814120865679219865801004920067264189322794849766132529995025233093768306677382369405826446770553217688021378597625391658554538197947552266599558574554006769124515615515197000639178644721144171154739336697234085766408323442588032184354448644204848, 11416572686491513123379507005215658875765086145522702191611409740738413742316073504544727674717006103070319445753081372530122925855788428643277346531956690560245411373184657786474084602065926793508020749128633339606862438661806372871784157187026048159182536921893628653939071350500128621520235865165493259329408598230549646504962479678459688109815966407672512249987851235673900480550554799532225350775159747820557497354188169949945626518394659729549200931136321198050224268435015499665343593919375884905049126924847184250423358509353981718421897251262850628542683327743883697937074219890770588170420880115512101564762, 10523724910208933464812991923568395076722472984209303629018412833194777915564863483835100760190427427880962824670722932391550801913321021076390293876616331818239012427337893327439918055828366974539921915593945621219565330404767858923408274666737270126919511526454745606640025298644609038052604294878709487534865955253633918333223333879424428507727130681734250516878112781986828292113888597325509521170781274478155608012102842983046339140288035115708874931661099364731034962030829368594443884281533786936798829872741389822449571270648093413601061283260904786333494218494975171314738484383857691899631799919938420856957, 14365902777854250531983507602664309923015005167645884278945840924939071223466766967290376724494723411730147618483955478391331518620286819246924772511743257805492912979619809893863280730458829905856759708728919947859746821166234955628968376481717289750410591787552618458209263578716314885073581177800453091495975924544696126055703989942738779484826213131418402443604738334502050551683568609423702169701996015388756179309333183442799476303038318215377678152397894782352599973842375297786468311754538017544187662407854492419166728270199868303381649771437224708694091369087106035183433646991290508264802262323861332550116, 6022669031166747253466015339055995683996490219779227431073941591159625450759399668388588623195297259370236391379380267063536076324830294921760848919711263267559176171057494193211176749372936677787531543149399435366664972464676023486069288457518007573954621546444552795842447567137705816940873155883227545339121574570360466854571283856608218146257177217725295873816126341807496786042068185326681194799568209330390811050131901061216855784474299081502457680617712775607031235616229511646164034787969210556330585465636862540037347534311336801156030134644802987586688204047991611117427367968627869201711276601205371093919, 14178143334702995711224677704872466715091490617379439831733487637228083284188901311983616663695808397085734913719344600405251686150831528656302047072340539968230723433301788529616623237924387814101388716293541588988502784101449665214818532912349932404266795674124745685709793582162386817707620066554580142149212645098447752026009855192781623817367254806186284664625011321638610247932199543750217700448124190971521157103000045031556572047178912636656890071698776287326125888236908608221740969951155885228272148079963328348040529492808084359765572305545064388149774570742147783615145500116629655283436336222366327543406, 2680694524573180510619388201364051956601371678626391643107074412361381069403125947698678225063626428698917021785592445711838163172162359861736932747529950301873046271424574982870967985158058371593102557602636589570170621892557141141890971308668815321321503846592691104760153182493173228131111669725218287430013076199633505869722650653471230844973353770543433580350352997695912141095717556776042423299523637339514996694804061478395355232111329297566967096869832367088294558338779659711819074452339499289329236095862199932247595807459057788640451741247616687346483386335709540893162289374277509809033849394952307960585, 7478797866767288177842590557744979347761318151001769080926453642372665971078854559404929429533831964726956415195994378611670569410451711422282005274821931987455210091843102814304596405241825589335607034784044881971150238738517391880937791655999639819771979955821435731333716281513883730007806365757816468753070749747852937599167905365829150573933335225537271763569203939077628984917567871123995663164333544291462730081421781584369739712819645132052534587203082434052907909075469922372615750377044879450432513785661204414594312043845016705644213917758530136038213977501633500345728565735490454571637088698053351282058, 11886840181470037072367499175055683225679270502498128458158694920914785565436864610112181200403310783097482126193153589047228843841978210695871814286817260095579253909639108860259637041828373762432612146251368747039379561840706451564261266647291032218038177218174963531324061931656772043667740581858687265351593183131721230440968373818535928436349273532930515825453633730706324750578097156542138694133418009576599035850809366587674284577915488229845838784023971322777768625816793683732261992862646935210677172812974476972934895449820728110690039646399600054233305704650273134378459145317845299276434637028635767223462, 2216960839748624388459153780170456316924086708811353035411015501288750028345315185724068026696346669655596020325162845908385816646003589421068916971172024307172818766796568807210583154992886441265716347716750577942103145646553615969178321374665546934473173285085041862023716353943428707418260824848718424309202872827500090021593693764154373923221927770193447154567668601160122224299767143871729287729336361625573566427425777162068174110188807322711625673306228759377160291466390815205580451777519597083906158744026660417700384870973545360482494491372172626175686993967315252516591053138185989262143895170934789837982, 8463755598473187211768479408502123448267857511527855998115925756697591210942507697141702867920476710609211442389921498556023471904376450380494335821890581522634876033738104980219758056801907451098156537824790701711317640988631514715071699331492106328103419122762416582995708093656829153328248772635394504968903357670121616456999817631902269048198599931847533625808729547462810703241231963410572023573441547403697642531584083965112168970492938486392199982540151512486445159210453122187155349626706949647814851489127140982364673732166930109951403346543701510594655823570077993298130847377564591662211212809798554006313, 11669029083164068827959305898870952163583409531894609836904587375987997016043922234590812448667953841336809832498377507968271207191887227096827158403842387580518522018119481580097590560765854651886856641375402643671911943942882941602771593524173196112352900870797272850926855475038472585864420721323469436582488256898242102198409339224792476853240372018721632079359601189385546918676811939444789798793252387321857199284972000847774042545236354893193567850652496133506686538610102264639466688067586885159990470325240532456931519979934443896574738255893331623848084516167731047977483052727795746031271729817639984706102, 7034591715586025670257400075150516708591163727130659288048895054931819771811408355732593769192148247715670310607367519300097082489935735167637024998529268936933945915618402676499468241051409227947394390861342738650867959430488928982695340486311994486151751605199891653343017626233945357380082727663135590875697586197058573555738489424694507764434341179890603171843509014876489820165022112170755148787041666307962104172311332366563054319249032363402167058599286377479607916057924347311910939053730031083618215189816988494907507543337649200172136826603966403082813112203821328587592168859202563557990701452188983077100, 2780908644277163156594934974067263877876352882525071854429514335638556765964233337918318546035803945521387422955398713321590020812695765487129768975055915263827753925026442274260317839160965674232285173318706423561470374130438804820483313473713303297973880689191166955062446627562279431851341431336371401588284505479465814444525773971892706977738596810189463641565306780755328057441692550104630288541554441782967574599396685201947336267791497144470269703474943409052519917031731113108494531412015574642110425099379094103092917223351307712292115474725049201111055438011639765944389552069634593117734425429987141240261, 10404513245276011341483479942739715224797010232802912687290865978208016528869669478119476869491971128071835088449597367454256088939889422708834976172487513080083443668285738241594863633871425978572680681776475953491893382826702367953395087449714577435707739417979162809997442780837328448083724182904991786384992232048285420209103312128501678197403108992511039199404598436244078174784966088849256295508766701171439989894308724609097757626248115475096887464919247957938896202712857176647085322080028586904704785513641861853598916621432191397458633912437128897702822612007877981950799633656963155514290763129663906274293, 348543172566425094267390019248254585843854038342942924698403095997551582634381613617057341711648617230193268606615528780048410943905269530808251238466258631838901987761955753848467526648584038249883600186046302077226422425981226208896846897766398750507395712564730011207725768780681073163348889651288372741196594043635156219216495862353232751600736243053824875057253386163990392302384455350591348919057205487763820268423171825380637011680660174869825118565915576609531001219841843425877889383347643934625732646311981691236936219614701861819483650539628291914744450424368276463407550933725783124804902417682926475643, 1862565071922487005086663051339057570593283826223227951030703733195337228156589818511419160496708387398431991616394703161049908289762833143693409180258557791440793006351157989862872462220238262161065914478288822467630347482923416613879230004853565574246549359456399823325227711410594047215142697373259250406926546753989593068176194347220446107529012764007148093717637384709823548379525463354373665488480355525834886462242089645285285249808505141692348453012480064035596741061739908582360334795011215987801998735877574864574207800331408089616207833602489817768744283098154895425356155561899103510344776580917514005999, 7791316716322855278497706884529042143282484239200017242538597106715404982368789818452435382237615495565127581707946123304955590430004621759354710819303625563207189921457901345457117694897840559645433585598140264675462377131310190054108518789256262872027562200433265093561868047839654850504509573900671408967204863041658680399004434677068216787576540232169302936462226884932793715950017402982945890864923566619561418294496820125983043990560866905439408720768051846228172327949684111225157456882994829527348579778152150931182116605081768444459716244226147342128825313465790575765812259597204965579364124277814540219766, 10911832963184217835532697581521167925334771539453317373311120843526463226266540240507961249871684972579593048012425564890483226594507101738145781968227773461699739460502688594113771757732004978258153686172814145067600010256987625470463432011925483723302348030331326339597983922765660107778917227640786682845155273428964648054689720988283106815377155716401054114968530271480955095080567937536715468218186833238272168555604885314613062998547454114911556456349426534084662186342131757605897563841613677106844892347086419471883283673140288230654622437038343205957056758415952085034684419006717730488952304523759073096909, 8805661576559823179168203130601768598992677210327865485308059735123403938745783870876580316736911840453558014732300234338477920142095160130643896013618515035270196229124782849216027958215525984193111812653527340495085371787196831505561539004481525429835570012691574546585686475226086768496241941291460175300643292326119595869720403766473861574458267142911056445306234232811597059008576858074218956825146013761034158794163618282523237907558497170989782219974596330256647101843879180996894925790446284520148008000460495881565442102220619914305464461756780391385872379310110325568134624005137129425003270608198685719855, 14039452113852900517934673829590693310305496339920559529942737533390764212574529637449012692384524696970969028053055154844295250283381816438259225112527265802156316500264008415557282357800945399230008272548150067835848238930576851814431739623840578739622609543235082477302534137352094899279225763851615377107058785398170778534220683470873515524482680439100969053275630766491667512816141982033638561924183396717269008744422741525143942610271829699215464945287281292942037229717356779421070398321329552029495108267364761013945538926625328401517176256932355308976341282931691870829621882734265030549150559397998071309367, 13186735669883811488444711221565076301786614468300919648383539567647716162597728794295331115962129863438148566109139888403691860045240775335568142657907134868089850280543415014151895787269676222086052449860266389569707664767338195752602843714561807424779397520082989238421798991949101093180483309917886247951815228077723352992457183543627141060883234700744890364455521423343959940973569181763779231696662314503390737946554621996497479279688283452957732781215536870142849264317847565523943592743211573460743410285553149358390891410245923189183511030339897172188542591228500082858661374191273333942300144555948256855319, 13199327855270764544525026558150115881192201465814851248503345382344697512404378154954105407236878264597397059680257805544550324230845548111911679518083356918070289189665278600968557293048298134435810743016366064559165440517221655462536573687493841312612070653768856647458406334991607474290969928240889082210493843013133167680556924962263717538057465883853017988043861317095507117972541820056607582691597492942481969173321103341435909448150967179826878617543815000082244921718700205864383856766050676285880221950158851533491847851771364705315303856372287397919979557251156127886884015623195126516870008651066910188793, 4454453488522425497430544571845732424572325073674451923313049338711562747358134363701610574752487716604138206684879968953162383009440101995844888488057187463123693776244658218403197677060122728972945658406112389886411608724508017432736511238674377043913889010500811525212291593985887095036218076264885402056403639389750598013495109077659221465125413306921482067078932552979552004063582949397080549825572832118346807523825939796908848853746692668853536137285414687641800203943386402884762589734026393001935667332653904213504113465757908637134479690555787519830780334820960373370311930276412368107975457894817968766313, 13344222374099615818796933720823540138227340064950390502126060414449574677165638209566178926377513365686061573432848574666794056784991165026855266006298073567634154732279787404054935073932254379754264312880390465486248694983081814113865151845482502278155757502733881982509297384739400677580991718054358755390327792121638673111932765766571228727568357983312239817790508307160171196235525275470164269779590268439875952024271592872393494659826169320744515891424492596940694466281960842867208935718694388051216929151283299161956973640159401046726410218224701722953236879512262435885095373920531937528035782075878686797793, 4549509528550102624007494101936308700006279417735836715411385802267554534014307483652229835093437957310922897449047559680642403359098552147563253520655539648325769409454930198229693333020071297407975575614014074223393137105123150721188243522138714832026294121315979816031927332597721915790597553638935547058268631060208658119743893022527672399387655104917532508245171452933998217814622107893834380479527023628204126612619403915525477946910399451175266921987244925461252546067922057868536614186988096034352636262226079868953643748241719660154663638810648004441467967931857402831046520418208115024127015811994547174437, 13669523792877420589383070144175360617439958319788222744638553991419667933200090690336114826937249084743715699659308574007244907830790951237114622130097462389102238337046607317486429327144205153943848084848839555725641469800873358505670905574929891568811357070868543245876488522249639656106496711161270713575619864729864986375546149351535679581517218296438525286548520817216590529043601616093165300928266260630645657433469332034492299772440995655775906538796441775109034453535581603747102102600938203696679569126789580219481971225045471692262019450742650946099619483074748707801615868626253472132366860668565806280152, 9810717995095057081681377169450969332126097662755664018993262167262015535143745461153569766121744153780103601863360742041288870965619732805892782566917196669385737593275663023745239730529655016737413526335593877974947060565336973407626793145535478019504037739370451850767086861113660828811456364458987663413449674889436698494766276856559756804401465798753915953848251237194546087958548267967378986385609076281539615278965291927952881733589808565376541084747600263267136259754773034546953489599411577713585750617139868972189700556992777231463905987248419980459295991430280287076517078865196020289782892011983557636723, 9389387710780309443091636019586422287143969636090102291378709201482074280456424347296341727105807830809947225528055325455100500820455679311534147538591293932737703994131101944117285125569102219878108174232259330656454757648944064111462544897650468829821835884750247255412852676560102138448249968723223765938401245604999872265507210907770923036639750311359327270767788825921786988029709543782110713592139551857176149961337879830947639119648833033471278283907139968319935753491458133378536728660305431979060276749927151696434834197830279932801445629135926813848276350946301251490164017195884321122789987495368888351322, 11302899383728944385854014866272828482276354248127517359680401891430560937057117297895951367057961647217385878001023004859153281633920258643469415310436503926251358479056466606322164478329332928532286281092212587861021543290024628427879736320812222067436295280326244938447659984749626126599113583322356455968417014672841390914488709205382999413512726209316416861865176477130564744666068364444352859312186555857804849370427183347317258395817671571362665055769759797611847583497072327476771618373735198123087262730267141005712221340892145688688879093072821246614421261054275525827959298857720758646652015848892301866325, 6009289352739863752658149671220717389207045166140845566674798339888331510717872847483983045605357759739827019600017903011626644049973226686249930276607390799260647969624198239661239266469378736546794809010536131379688822164365429709657839177790288435865140713527618299744638001391790357332702940491091324674870794434218611611113629638625565170861833815340217235188650054537405389349493728991507278846862083559316519276133969192337916458452628161148388644500551254704303992041919796186101669688202647314105272192922363925894763337564531845654721977625530947574273582553252571205044476936554386075352306802996916784736, 14700756711328681587104866293230523952825682058737823078277750591869753805504314398804774655701269673343291035346232705282336747061416310098445604442804237437105393076641175874208134045442267022680692066727963936023028600360673560355375814870709473306497583346993207780126697312783208535836149739190495283778134346528412095437566245226912790636156665432072779949155150315480110351445839102449687608087231406077890815195246148827457693476325233660994988893621900064962814258985086137517289983468004485957737322136319328347037876883271619927722386035097453664035985453065621029014416189468907092984431012397469475380822, 11617128762841905021290302101253512479251857297608607329472672629986379335422655846205036076502495515090793997724646701838097337205422423755367987412143338245744155977995853733003555520961448331776446748829755327693308991793029744436468011137157800971594447292257890472114356986875232596056561022278533349960034984495932365675062345035118784756871504854193280271365081645691337391380439145646070909110472695434964400571474217270325364523502885609211377132232532272450098093577989124900618749053290940812363450692061745025089069542484959309622314434797444405132948562219806380564653394520159657750227552533423193493969, 3841289139146089120342802569317450686435657828323876034319303961969867828040265078048840717217927575629144020301298454007157826779780100154211289985160199870187008181832956828489507525087082103219742383589440636819987820446791555533817028270539105643415623908821595552672923953044343121967487953269977241516286648329088476925046729918957104259591109842510092655337063553551172719944659659486232816495195590689055386035520513265297368033005806977946980751089421772669684205232360939763916245626713717579608435433837480206353104614655623968511847193908650883334304291142499324442927941997421156823714434031322899453428, 8719270433680245055264488365708898136467883129294384215502475925339992342826841155806139978976363680892591607565311956152627912143438044010468431239781279261770924887019708034255811534346491427645458875705022403881892378300857917988409604589156513054898362078407114284525447906040175290101864977588796355024120578638259959850833353119202176924691103989534288246672469016391884724051698831666033143284808314170296929255073391401744385745598528126483258033788294457242774281141956395447924747104424991599316569059159679631242535815027735862781657296987464439834923394146345403031876567550987634270136733232850527891543, 13102471757891171127862583467011117747136836313983687954777904235144186097499065194808162189555605075094539937535953029174900647835748933254049193264324966299240964085955612095143740732404233592680191496235343593880784892574536506463898539033104627511473907853123870655444750040958254994584213929441174194345648369597441512794890170676507520213193396894397537884286190418624573027767752992570246445298655011256138393286797248655555400634908606393947945125852864301851348371662116562684101327690733695188644513352081828440640344387730757687560739561067399510266386649232937420767485702877651350294648368163169965479713, 3310469721304491815766024511467222819648863019554376281061443198292371640031325800492210945125911510066983414717431087663200651561421090676846921305005409794081090875568665745454659233659290640617188085778377840269405142850784142549834307441172170897766863307738994523034219290754754993446434922316370131706116988817102378262212737267700998473861886007785367248682999080353516440029669223641879496346272490953904350293219003522110173296900150254627084099773765725193718645267768760710397290508305618088049918967363987779441994298639242649498198186429385324882102479495876112858273991428370408016418864488913358548399, 11393456360673115764250043378056740348721211239339063627043189413655819754653336883938551509989912293157496455630201707160181246892449377915844004340717859199785229778452350402743439383431752455846471498004684005667065764053728126662177447524756753197390508152676409864899150031189466370669588318515995230355747613013738765974423008915984325133040473813623185155237276500752489844955758716210024786581672859411752832191487684259828878050766506366368504329301614616638918141303006150128028073160171875237955677637602114271624387004215938601338485567035328319314314087326781498307130533905963593941303286195335680901180, 9838545785778026660527422489864857962654548073005602706161989792384835352084523628950498047170293195501947820374961490211237017579914207790017979143692562243785984040944086316442695150827854353642984941625528424214578080483540345816065942739787871633316246689533388158886732801430127682490593157816615923917658568829496994256361564018507047253991212518358888686146041991722293447731984650260678751590945978619515649110787802746043629346726589178409763006374274992204255855603441940579133777625134827272139909181894358205154453246052353522956366169248775067031318743419613141801378014663704258110570094280519730656882, 7190976065444706497618673039286644485190289593559052391239566849673546236109942550101501983627389019504478093692496145710661286873077115749602041416663279855816035202459884703957549506067196365012922763389174900109464306793540173810089180382030673728967126247708145198748331512340107359781700094743409678339832087407847040360838646761567037007003383571670675054572059119582882517296496279485019696785768081071561600956747889550638502940170782016847242121516666212226434110832302779378310669151246041338191081127301676225522885246840671726864237449781582406491950870039593748519023727437097913286441850537524798654353, 14996387091285881176266085956190520322780888380878072203302682078454051017314261078640824111737314993643478477781717274854189273713216586600845876082137064817948701236962498513410575052609852080003887916891332218721420738629805956515728867132640513602799121521855543621327661321625274019152835418696826395435503037673139570497158999097364740540086306853353470804425366689702276999611343203854614644158175927217990092790029677363119281756755904215372459376686847026568164818793242722757937655592546631510676997297276554354144395399567443303598805627825745409269728554232398813695840007155719008058532355516316318852956, 9583766538725180653577867746749041606972211826658998223983068169143226677052158702272583830834011693091209230976042257452717312129310956025349862617445486787409532567355901298747030542904721858800988522083520981549225556419520181667130161539225745674332173438354227810723686774492484092072767201061220163998280065110929774502670757916177810232762027673119964667030167539494529856470501814748588923929352012821765873499000015220820135618195178197053453726466898187950804201394075602145047162488514948376740380902041397307725916691647934635560394924011723753499548516966632766947613240088713911111183319975472192142102, 4772209830120888393586405787596409759116654382266072017946572365486922021418002232350140181024268244152880218843705854476176734362065951763619656615936112681037192127377374780733014904800078394487764295445371962377503673286238428762966041690917315940141514638685221287037032967368241317966509710051918202351264357665310530003926116162906292615336540243423721868696654202742720843925197143589706371346696026173693904264926231157616644874759600438300441233233298200896236146305278842241519288175589106989636179989041320631399888907081620371455951020892653879577611542189682359940020787360721634316904657875376289731994, 2947386937165173315184449667017793586788330772065645697188384559233596380183052593342088316778059613879762246120633746251592444387606122020157507616557284697507162914517064991413410439158551360151976097015017938810946172670228590438636630117544351558401604567753404619095958071635133277381060456444162299582952080779585773103403253404608745466319984291206451067872757807704676282062783747371603808117128885563788647934718612542131168277291936850360686929371568685673079360546883462051923988148208127175851486558346520299888177105285095462077120425620929113334739857582740781080665913903381891310589819105860413117619, 7863582313481285616923035849141551131897735337717653547843549670781961501147205005198086323014527965830786670103537136711238530566436225497230882502978936105710558368924795308012673772319147689399499424834667810218823704512152258126151588660682783208400463201955419694843240604908851457544687487084255551221922469410091963410315578139439519248044930910393164535386225527626266206743754101760574672882513654964556809316951207156222524919301574360335991486592433831651816217857690037283123582103150098648635912242677295826867229638193782734722101218392869803229091640500818984931779705040754258189256812568662454579632, 5264608052971023165774531703284376640943168953906399293608382696507920845545946974482141870583715889093558209933450553661701857353238232695862587394786807528771901552306598897136027481691828006260306932102713334732340921579340626090856585117109796783771701408319264034538002100333639987286979058184756112221021800182517815552765515488513264776238629626255427536513537761187973412234119794942677291444325900038961086944319613723241910634483279205014601946925267792853400760402573286668914615850172831599703618871665890208206506085706876885981979949559997142739044999306967291652527389135321031976464682673543468365560, 13846064466826463338830283194450290509099385429575498349083486428473127444247884974261410982409482629439892822274983453472074961497551841988290939636624536949264486740344599218119242939239003234229676926556513745539556846830536258156332258727144422472307509952942510519777935930079728451779906614393973555659883642442725984900054975287700275859664926595547880641820624068794951953342089879005717163181667792141696233522582050993293649514026347624765617035935559698420240628433019238460038054610700759297639508768510654984638539720119697312147102932449617068315042410313016579439218502505382246991071696348217195959246, 7453370682471740583181823505330629472799150120602186677178397978597262609924829512070203648538270601259448855781081729900048158927398248979383629065976348059129287365380754431116231667887507469925211038645268220382864084573106259118175243190437478516508912117025608140109887099976327071700559349261846849503067474233895679261342932175722417701276115618256774900582203593578885892281770713974411151637969703839939961613645724276353848273999136675595122874288466800995563811212939757933090563229110821724628967648944592623616661206202616410249373527860607709420650308392004754576364755732066893388454618601830589606693, 4317625227263533220904110400715789569869826367270947079962678689618303216432581071155136352680944411239146155962090597651286086104054924309245212733927313291497234228947504283684975384941252680330752242633822264241560013950309778017805895616065648480933032106204420655353789967638711081614116516938337443302076736832052545620809862083951492355670724315882252239716318446367578633257119219431192227715048262033428251860529445348036495575657711144834833417870023193636859211542817711300290205574241652765097721373970940812268885422218219735778766598770128151256064450595651688665809421872114044500999262438775316188357, 6009268210358665637068774288951622076773718680860036103887054718251611419268016844883085337174804354375826912102242950458059564227689876187285432560376555146437528325222293208852083855083230661399432566948274745427873585856548819818976369442522868627468540827377942538475211960454553095135257234200623459914804302570971821787071181640609193675183969351796696990261362529099392626214658829409066648642037121011366154508810870358481108521297843651904721613474413850824647575510852978393492288778976147297646162841248558934072019701399708387652673659289337463836086368161805253199849976551830711038337385120196148551097, 13536490421378380473804870021443019114072527439052132296774457896100885721255031392142638378741479597128417545054123676275647576713525450766402484527234394324052701100661770006578854155075921429381001877892971007806810454014951959552903892101510606890910381874597514507572889806501620210798981309965107919153208614620621618082598632030492185022549763233367164309728328583248114412129863480186195458648051380358413435912996702433769415325417569989830419922740885127453644788852914683736230200891433085336771773905393097463313218842185463406306807023929234492855566486921528735906031449023852161062499877703496340252301, 8441314907248187736374297029514958470569340253084036635151743806870111400548894977226940010903512977525188613276825119401187760361964701381356489022729960499750547853886646345145770328465377810159219394125017259461655984606085503910803178032020285778122538524611322503597455433511996067093318277500582847855490885712033124941093277924689768866910476843829527807091144442643107789532894148973268390216828993381877405772760804516071629109208331582828242345126847432013824787668017735393629986616077608501051918926810940248530522432991032297098693401211913738055287204527521763465779963109533834646372060856926253972131, 889379590594645939349612545372016712841005657261424943298191730124050437579030011916714303377281336753333261395215504804356694877258924720291947913277606869868604770841932878964543520538666232708315316563591758570930877852295614451758236080543553636160348518081854980633472649335981078842582741277912656024662315173239314261403084913581943620662631362687050756096257077860334750257684290444259675749868282832165378410838801669077267657328327220349099465500158494421270341281256918086643128846536050912734215360769390868313610255120839587401750859787467151379239418250493656144589320817110428374715541396771091349417, 513960913671954031639059447811665309014208604279725783623071049485467390076978927808940480426147383827417926327904764729956529028230129350950373554522583147673964911829835588454934507582644962521373055125073909648725277327778200497633983008561423158705931058201088852858495190084041131854716107500649486307877153084644145683755586325560901195638945035797270306765975243234530295540565642744492640390163352044952251789436983751074000359499780677370952140117540083241421706483548079029265031611432761411698293723006224832625670277394443303879430862406415222301286074978003096825539989658028484600565554077965163871075, 12784133621494786317206223502271650853557670299595382872838369412075420688824547188321385891026781105979520575690639149528411997058677263291454440551270094791701862802222067778300050961718119204734314033514413939863247765836379892565236617032841508670572744815843021392529577970303323931853472572533602085596203083247772716315599160128185395536006538637313397916527812773307150582188979812393327884183276895537830685957917763966959605814477150058333238398182752713113177540574589901113741662620431882349102082017531495479247090554300863256697917225034407596926780077069618334660971158267542563975482297152090672612542, 7946858568456275901353634795296449406207104010944282742550939518582039545180673182830999490481074160761552090458825583418491578733831333099000143398315025904922452929559236356692923505343709601352469065167497117411308572404001642182737523396330418015945514220920888259525578277603740594822862749014467288501573118700522532283379408856268078887566148137662235818843322254663478431852397795168643768676684838622562933676074433889438196076839463472625739166494273215019449005102876746446370633298170401862655149134054367406414018358417110654594360526155017664888275993629567368296213931757172095619843734838440847617346, 2175304100027010394765705893856450743510008174694321093330107522328789723938431112945437167082492503187928250015961816804557726018090345287666437208228760175837171705672474586043943235487138613777327062678518026813695034084346029193578873498451221247618059531690690343131091953433840018420264879384642811087248340844826617758755337651257675354653419610323598106865101289464779492771350437446675907542536464769122204493668040687254615483331338032165192224353004888172648547383850371423112882838441237165556385633123021902569144045897305613765810680100536135594511086887054346712169530301057660431139923385592854213613, 9115094823316681198123128999721751896418899466971022514436230540668968676985805982744325122282058769394363274855196012132626434220516804346615521276492853800970988917339787962562901680116963157877044518455130918445306280418781016136272648854716464244914398154297943577281442452833554819454969116322702533232164376705324798712067074532827543372625847145873578566088719660121617651744890925666798348264040060683787640616817056004029900901000582159679619898108581615876977926906895428593568821434297775504165523008042373836343264742084016342061321967294865148170293185425870262690503782785370023923094940429605629429763, 203287614655859984522450549431105006564070082490521737033581954425354279354236849478782458683143559002757390685992245999465879537464095975373985688536438329750472563274552149355767985257028400257758534513308415139433050467042311746934511834544440606716906319718859024514957221832451629225677360558118945851493225855158743977517448626221055623073419143595084230708279570245259971608417826711601796148003974135256176194351719846883361179502463020206709741519945216395865473706385930225721664690933698998664926934329196769173394250663418376928061872165256387167225954862272588659760135346564018756974592700544124145436, 9883107688216660053637433463771504552194450749677280642271783194846720115722699248763436537385082343267738838952775948530735856112893883748572505385425701499031043174181904911929131461485971225852709000773838947525419646020975418761381967623427493902148278779555242758944344783281168461405622553410377268517796108584521708038550435008981297207373724024699292241716586109516683295836952713733269427699780155988216939709095644601082012807550786501665071260290540182284370749131727920826736343476078102229415877671523432741036966276654062929599914472036053714620414012487290367264190112392025088865139525221354227713330, 5440207855055275466762348444906955742829015966843652742470170680815435563901288121961767237101399366567164805678891107666491148955914683316072739241197643442365232078620181278849280624379020138930546354791571843214552821142571953586149565766031162827694678104049473377751701524286007898882379837885777928353020770020801796835801738819779496911726153647891894001199100119295806691177466453444400404666710871725430984427445844051544100473368773100178377498934671254826512818149213881540330976826238090303368956041386815448005495476802458756219983890377087416670286965550095035797168916110165889335258143948804040549938, 8655819144220064247148599853028878795108210544521306508164966295815789006966766382751596729430321026492805544827599270064266835350665555898037643359115235549381636992655537757096589003565425469446901536326908137404916761916241091956829074197000402890922554975053670405533137627647032005103027360722035424166100765999324479514952439205906489561221983409633219231149322454662957347736311176702706180673534715956916758947535802243191985142581654852579066227825267540413174703994745139807164587713935223132249237670633264857262959185581256544460761434340246997809995215193108353890048976387601435637124444377815765054512, 2549828590736741620819270939954841824530003386890690798385047804121983717625257509332569248217109261907025032405654066905335721222708625902496512004053071698200153410648990348263614647494508411497299198749983814262139600459932892601117080831019616851677972726709239745473327003035712153321945676828244050889401417205802573291814220918367269623457878721579150106523514677533490208033553525965302626101958207906012695336450305889957479707412673069907097456944191972509338899045083809325982306691197318116088199453968748519246525587845771266969331986984885832436078708901339379155445782206172762281647967404787994903875, 13480255023421504030102744183638325967561401878406689357710142569357577646797435343864946215370603411980735938174702112727893710844456090111046674139272366093169918767584756196317005731428295886138636759215837636045695054948899816694383041007002307308870473301195816143843598814226408760750108939891079948650822979056416551888488589754585714832319035108779634269421782009331665635259507999230480022590050014935328308044638149325917197906205450093766482796570945972776055339214403579785927059751223476591696688360164638512279748022417029034626737298731586561553143168555996917987927256741538091293252996184749356542376, 10331069871306131580332051297906247897700538986341424956200077698833277001312631014597315201938782850596643291624489873087435835668158947055072435632524774723565268628099714819146753035651904172372959548440892514335761382632122749519251297851153422590501288857107524265130437650954235881208062204284107935962222897345575642182139522114313368041123493165904247859889513166424348321188758826964247416383490198739053575381208465121331449195784565739918106711049773977844356778334720135837602902764510667590686679199621370056710546469087024472998808616832387798016830118196528680004913653816072625013197307070576948211523, 12602890320015622303841526584089523995205379039152756630075613132458586272905429613993507082379221995062491523328369650737517871596436679097850503319962251745583194747271887970359039916760615968687205570686231128269455028590306034678264956174441345568404258182225728979257019385756813319267286424565678403325600063994823911110797136680649090069332376507660397511783307891707442307899444432996513798926990157486412506913090295545636080124153598190920281419067713853632583259279233637008483954734334337749339322664414435736507629082352291102793445092958704909994717570581347177300287846314463713792006783412965919190130, 11218364421055374046418008576701584653788374145397854887145800658658058696403862716885588703700585194634841684740489931325208955102749532329161886550198003661580633485676063328036789761413865999029576416878556976901431633961860029554286390293125810829938455906669545779449712248682674284187985869944920857560925414594476953903350415542311752435640429333494626242236851665280697401738290144680991245878537666127700398931069829602779932203463059351131234830257013763158098631150444713822842510949782751317096240807139506934897574353606568100668806891195657603877972279848147125239232994147832930998824186161686196965200, 12547000120709181187992416128929665727063806532371909855329736958793771410530805098446393012211346894305628029724243448974220276051391277115741195121539546786654223930016061373637721130617749420215448436319069267233078312128904914352492700110796144537150380720898010544721131482695381424827286940720749193938002739807302480331729158991407573785205215280722396068279043137290368885597946701535087824142792207031198690469208907620724305220548104234414518525578198006670598006331479559791619635671775698549772543328090563562859156340885167998420008920993173367822680038456280705489473697753152722854316159001812907760049, 1553552582069851866855499245390441122339447160680054294186866192261448984003003284171754154944701263851864342998371094675798493905999118554032626467197844320093059856399093686243682746053539557975186554960300009587908436518082810884609668917453158840057593161358233463652096896138098906049077184471879464884353404248216377946185892779417266833333426552355676586990427824745129050712089842887832008168769475048609616477512026897692700605821718416069345860053191404256745189194842985272453925208267786233022966597723331110224689423306424588565556985268577001833967320151436347398436703593741855114486824162057429056193, 1798670904280035194148247319250952946286854382407426762269754784998239779334736742900987739354298564249119992888185249567272619380103553151038112770137750506530929636706797401880376819354138340025409311137334666860508919379083329929191159026501070249035189734455174436828802541647353903886261890035897506128717581253109538419254939297246762804148702889467961335433584599042734907455423552857440313785236466836652976199672280251984938229683378957444118184963712477264562437232015356145770623271836297648218438126567466684063353493332216148884425276336427424136171797944275707939913882732089292901681069383954714370845, 13780762260894603579147347784171823112483632545021487482290137190284814136751912139703641193391470429449336964416944755725537929054894675997409533920587403747032998472646431246022086574209199949354501722991305831801652603198030922490261962100148358651740307416969907251661147263760400127616977177699600196645870894111658201912352231617135570147381170422851698972380024621660529110104640542642563848438598150018957583175110116957584911445720960509183301017427967253433136357365781212664726815564664160075125210883964258162230393393544892847591394240164059602253933037604898057935533661826669244150474781860043331231257, 9223392802836033158256889991749304834600172644382789822344177650654387656729394427470159084537256080861772219847893581973772890408362223403889369084120205685433230942133658883658234401061417801928825967964726138616687001021602273961627914377762124927752166289513535215349758619555858223943918159620754827163987231323830457281382633284807330369288316455219127696272584968044546233942171303847739819514567024362196114319475143430672820706513267956697324067735798389054925103899794946871575765637763144095273580871435277164100952200212982192161895398347229602149104987867479507441564605708424484792597661578456916954853, 1090863455756964360182427467342779585934581198994457125481584771069360691858519821297957653324050115418341113156488057494955526602250792052918732211166420100344869503163876059129397037201198694569059501195490165680971497602336259402027807865442242375585930560731684773677874104284047294898854430738279767404176151579607624423224261919344761637478549425740860516339382390777740904805500729551997933167330645492073867959144545207143485427833157265159591394575851681681080776614293856728076379096992267521498499030131771928423608321013706467101937829949777472662498993099005158298906843841854238067755955025254889676936, 10628624949793377180789669615963941853666672034090779688727811752914134046322431427784900342174276662629424828403465963458266310989547025336844064510225618136209408802111491984070441378988463008625278265264704490271140074100145994103955873425605906264279406085154403888265018292833420701444892206147146956813970257512688490374689363868528294466123929549565843136228473192658830507867457097875135399453598458493189232366666506876506352144898566936492604486451533215802508426862050617154549975965191841490273055288668285238504270662541962753860624386355569087073451273388202766654633925794997259512515200709781804681557, 5491460316141659382572371573618935138728959060032314654080033113339761974127308895474814330509707487974279174582781302555058355325464021246655616432291228466456692370970362778351626310145587150794910585269451030485654382153129953130886011576453911321603269378489083746893112254596762675698226686879135775026942158262363604218777107142861587217713582574114112523559282762541999722436689505829404129309534695089317324943440186788339026244556287828452218945970306373425715985340408912958668643945714398485201372669754250394485919923098793548882804150620263551112255149377944704293467019599084315645276466100539350798898, 260530033338771951684245545204745158824102147274534727502944137986261018085317242204900541609697372053642589087924169384237595598657260572836217473431533241852748000284926949988713364543959838246011166212185000074763133335275564638316684983264885075532186975109443737928719253221275036479933268120187011681115085125560106743825078469942562916521657973956698233732861423623511602823422123844252388665830249091880362357400332080879382288773654452002643217285867857849427626266228664237445040781898900347391651475101584359947907092853212097267988408007984431464791162832551001828763648415325561374407195339902861221690, 2948131840427186027835742978561324495505481406702585768668352240183277630737669415196341082117417046723368257860915876463630074606015887458974159922336653659557647760166541152143164802023331458313299235841791209120846348280925647031301270365360815018871507131955828412541933207047208770129681355265173046890822762573166564089613109048060392947535622867224619799466091035237993420153755155397493587226378958391874762467470122405430260496401050632440941748282020302510440830317995492050789776356317102241729475812285186359679200523658726262247786886280754975376543017416030129707101443101288757386491132315946825672334, 858612668184334550705080103888683962271126145615307700124438459189850654023076378478247859997577730588195102395876049513095005255958043445001518303458607347285157646570274072796338542025222927760121087768453734003772337029807086975788597836741307846075878374134924463234563469204025874735007824045230601920043092368446449239104454631923463784228354246932386072528570387723074777284844124263792623956556667994861598960005620833244681777802558482167306379426215460787882587649298888652577534323677604239732737395770242579535065853674192195293096910062302121961262664886516725006974924589281930861005566623633436521161, 12390905527641208205484887193041905291353154962763774562659251433960224210512694972257787528324902383672862495229767278974432368672550501215650229355499891900206977201166073047117703149633254042222113353336826457596595886262541689378779674347236930349487403583695555798683646665470242259429388364592574848407960095057714084594694071344242721629044675951139626922618529292104496811345776087015022978061717787411651107100785603074079244531447626311517998040631964122035703207115098296659200798145162264227564876245986002518314753521859201141686667285701298929813525646683012288252277291564915240956720513143807187745503, 2921603479091378050986201588160719307224719615647168872730247005239371150834765330544273068041259403540507837732016833730869367348928254672154322207666773202096692260092081146696908883890878480169120837382216315960275292795096395209666883182962120708156104941064935088814989549868365512481645050022483338138179393967951816266171392303632442843725325540187833746777999765029075480014721739055398002524382018856520165672822093466274704322192558458434053538650192151890601661521453770426389539726602961933981996012755945779767263819556817748286978986383907117728696315171384569471498500842481669397142603415835127974160, 11650167350441317668928716653943615150685627037537500446571783633463603119417451006417914667164706509118951375309897914467292876802306258391739957237039397365710888631925991301309927391453349258336102981835957525193174145319455480103780553088806989266124548271153814649978628933697498219773057876232986065291667016972261127205402559661016303763154657212052549819563940237587630835464934587032769892249538366505631415917841125652382631397168856692110213076419134754071843420832194013244726825196043194791014217387818334516187527302901214585246367314658073367456095277794209459224031127107895730137300571239695569079724, 8021039383604751844614216724436477247011217170367153569208025319515730230482856729914258082822824006452846685450723959850903196066919228156189795637102149958079662336538064235529240538358806017335662105472683860395160991521693115465883192286215395768099339338323949299299362829155984673025881767344120132600914572039560619376388801668440500876487281979889281363017997726548832397284458801669644514491877362352503242766061458648031139390982154513682140742833230599629458385718639115273802389305395519673841871289974081595201525288567319853715914828443124342251255175765884989735605726927412713009724340335449974633514, 4477416761384710794203596978575324653274590383796301254792410928289990401145534168971258007875843044339403745866881434566382629367310734356480893035286174425028510657382391378617193120964905656491279602315047794760731960205688200074728582077318876161713320092968715915094114238083273556118669320657012258036843280272164178280988756447428345753513498417597011257223342645265699727006343852950461893480338004676626644264558178354478847975115795471179578161929247580986857150123507112409001580100455212502752531485108233879248197247713348415965267531952063070148676356144156803685917894597971846841383828089709876286736, 7206708692979071065159904400616961722593507836537900372654226352786504402579734053203163760146383313528238170682451024185263551885577415755261496324119785572821146117304473078761870643239961781272908632631503074383879197347740304186320165324722094288765539109961122480671343685061749545752322281338528592810716584360488106710590057545348501326778207966008134102248610103452517387810006626168888860750330198019524961559754939236547102704688402400242837790161275345368089788151080067008343475522115042327684176044321207351612203517077779280310473916393719841290997846034314283393278990299747253287259707744910932539408, 1406540507967677161705225090169976104564245394108254054047004709970985103394199356556066906255223915874645192382694814704234006839795363931808611097384205472752739243764787203529988381617177266142286640765922381790105277376972801136385414770701862620322481959783032276172764707810736247064053214250445093834894366232148406317565498718853251497270312872587973274234590601200663519261638482166732911407189692160419566967502286408406238651690052532002491976533144388490818988098941324131755913010369204114872713267589773463760505155143113122292080203877817019049020008019773876253366843203793909507017947491102137648355, 9310494543900908934600341922423248773201063423074782237830898147106348926911457148898171190393007887588715888441423801549265412246994926111286542091708764738087508665649450752933313796099761307430733808467540019269564146362619045166278876623913620546176757207752172943861126598087495010429482084621931439220849311205935192277310344710148352165706240820459291138527191754885925681629533544841071589388954231634029726216273034042710159614377879982956995774771363211361653171538699046016034068461455865227330410742724695416996120081822493726324193962366069372767629773959700090420726280903503347144785621449091199698439, 3278034746557838216148747361042690395117260457269069556753145494940212901279971015035154048826617048262529572095211723156244488635699113995343804470719660062087464587837821630583394921657080163595714738198537602950769897574500246587126718759426989839149792776412454182790795492085113933269863756059391958041684740383423512851571530521985584220450404275092477363347693232003361647047832912928215039755287765113900329017753913735640486787943783964003020901478925734835150061178093485582634318220462290024209425636521816124223744595646264346602512925710205678505440600208465870720766418740440896422083697081371390248497, 12343407036688480280091218619067409894190981300330095107619100682949004592277107937537193254319723934236408889442364246283274047590311505318394324640161478379310376117149562575637502832027780837360944321024400116681774315002957716153817688130719630886849540762315007802379001702799763232907348958986642453586397484393948391508691046783295420662839546289420811837979589835832956187124903239003068054551028608163386560964012838447407073187474484065777852863494475161232356165559505758099191831208136183748229302420542137334902581376649229824753064404813730109022286273413798853804057665795615638020687765019828392669145, 2770526812086431176255398098812350744464057417754123359108018739501487160362189919596881058466335189473785889222561332269204184057852254786419031075297597983604530053404269795796457838765616558266062808100370260455413783925258231424400074854336431994120509026158266095716672776977005562906822863950350093963316794376721496650128399100394397980271380510072076218781803383368016528947558420852494540768520826184359179891262513149961198753342327936351166038330735336139828995305915420784050489338274910121835129488810376396482946557121482073812055426957717839033826299446591097908277527069429166847715663726357676492531, 14096458189230156146953952978136043503853280271435268994283727135983678047935107246890306753759146439086190386633111394139095834469712447441048327783351784744492349935263720959908244629152166482290667858029725195300767779990104422338047845925477749836618692401667545047365806196919368247379562850020982757025275434324592417874377031621859643583990859162143552160167215722558277429880478756113404598754410422477564111129393544275934121777254350558711389339620976023409735766816417156275024773371310575878324513901593157558740255989145673835460872668639352397020155834611075162316200135765077506836204168024352287364576, 1712168203779135470528292044598749024173719112506966121687728620984155833591542091657084914450190304558486865496250661115279844013609437992998517958065323911479174242740826960690060104760309359869598616987730346809031987907057172572960711921650986763178297831593646131532131746687744549504535815736026309126945970092215244986266544450052200795631905135037517754659369104751620977227121355542911094937006914253255763879957664807808697004846250370529098646161792003731117948757759955921977489091964365286181308761748158210065032229768929689726319038565734332532736464578706513765956223590981266026725197495819426924436, 13761215552618140671364805581836948225801377829856577875070754262879412740034419843388550644836563653516020903385906556450907236512748136254619139719652108885336290476336092613429462507858326792278511505682598394770456591767240779910672538967685132613789322873368190515749360502080080499151240194281717629749208348220125364257946870010951180551485096533635462089623961965498224867142801485141982776389959167062851782725559338064109311131278642644378215729238671475496730774767408362531202046690113774189795124255068261067832220459970996239888011310834244444517690929409664950278257262819542417404446258127903564569341, 7558582488229051837332539188307360097069978956965416411219466524276052075963179996252345334428822579389833494260759145282050293117022833592761075541351765760549276653843815168813624345025270238336582927104290310667218597120735925130162277466237347421661235744334399122756068577962631966896455856876969562329358779339102658138990043079795171548841787227537473092656005967563639809780407309095757745232189047442467319145873548222606282427687900518518236257301628782375814253559759745769120836525998229890747817352593684237101392183605411867137208545064100070473089291402656194713695553527188242266586667835779086805228, 3547542725376026370540033325405696146406260099661226360537994064117264097529655106479687164505614087152750518121277951399014623077218293339712685778188559735769183114619734263341361416486872015229411809501106708425276235036824108508130213267140971251811791338799212021427235457014273240598763135577405433694550632481622969175291100195876646029196538843785795093499967503420706118502260864250434057818567638274215885381602359693514928190693738940666795849370355337751512738079529664638048902704043049895015267808094731366946760063082188400639247322478886706877934127852839875206066586573676506821832679141210202116892, 12448734425402865799777453080811659487659130140747975798410709255238174664908611202987859655966575890660026426892433861410944676586449405759738406142058310998580490765822963735559634207628454671630012230105807922839072494114738735192835644139388341017326101415479294840801789875091881349889038586462813779139348948106520671808237635738739461093846445886998707663774493738052985241253195505492072771098920478708784457870301225296505109455105367642800772644108916282562310064666267909920175215179308834918136129037848058653609298873202689149912593922900339745161971758665131073942948844190162813386640670031422346314079, 9707049501926945847610789143910211076942624758568289322848500798374357995476947455605337845818284328249035847091294671461588897143865663373155229888712120410830596196613866361780874130530121709852769174236709362861349895084652924902991625028620868721547096779011757197752751149459717557248067408358895814928382664811294836351085935948642814572062995471295573677688713111211265995185252681778675606720482436519317448736207906260048359594586019752731985207260644020524474411859294588135467481504395226342385583873471815672758457248568104671300533597696799416164932852740011702561723040351673569819080182626620027799160, 5997859100053191858873883284317503344885216952219401290137414511728329792348861664001620421765351349016842096297007973732845665422397761548060845150070294143140932182813956161264094176662853120684982897596484556374634501659247106618452641826922410727951217809059801035349500151467949757089730110615275631842430146411395636854048524885953926565552566518033112023547181353098155683441799730243495565973777085736996523744800755366069898336644236835546478758561899183904313036410975326408627437687950466379233450415679754644631286437654373601245025504773302265999255130982876751709032824525058322476614743456789952670691, 2594426081824688468483901666578948937662785307268869330950954684436104993117692626026513919210329353605100113866759879767626329862322968875706939522926813344391055102238112923196013678792518571326815112240470396151182915819662977623574546490770710004517673439082147261429032455723695799337662683147884731475368544788679337235050217465938680540334323077978645691329931035903717407975179749469634088584355333889022629767729256232841328112726313556893164081782859928316146653709160272346236468091744182130203655050557041532515717562615804964277798294595214811259219416076397660094310332940986805005667856868508012775091, 4915469893210558064866173577613646679891389969808644368885794019869280383707910359216156542107417769524946049192646138656280969878706156935331827750782984796852694052607436430581378526906211397201323186249213711241449576880830200306070092389866829163755644003286087277586617346692674065426872717596445988381683588161070796139646988133571419426331585258833416159573181210963742577641584288413086859407058725133419670445998711061356863954173753302224553276783471558981627052053865201689833338063386690171988150624256619081193017898866171556299107233088680633955182396746097356800139979084696251220378697777099774917488, 14019248849969844673941349783442299840228647687821448313671465086544037575808658490029768180390178463142724041516997749176256777989941632119364874668639357503474436472795201415535514400893482656763358072760437698477657963949086036785056280976621499672712933098359184213868076262615871441965671453464763907573363115315321771997192473130527693328806235949548431653138742658566846271462205851184472134531116356592425014108965715127148069024950395272635702893943679829910425651237359721766862189661298853136243177699567812561868209056917377089724878550762924443102419280127210202148001068825994194775989262340286542954512, 8810315116357539992065165677008632947747872570193457415050316861430891332873367324397762386412692872839544009647875893208764137704827800757807415324764289920057914996826371541801013355130986469478668367708547355203504704148024187922274556009386676137468678532210803282601372423982788052194071701817915979042097974119422502771529653117376188233254683421970582959327168390618575806565657146580253796149321742774627227960987049552667360847536890622191017309639644429891572522588290194168395801531082133941276986015650075188255994723360386747869495454536281108494899019039395029504943467012968504321625648985749636242606, 13566232565927369447482829466066912458193479299374735715590529671276916916738152188498001451642299741339644716756693193929842191348686266382787878874261180150395198290545471198652247285121673427736379543398656936272726596584780905519069993171798960576210882146406380783070515574688327023597874327541558849184967902697304064979664395105113968967073808480395086944136441146369272907407412592249594750136817042836274017828652943851999975369742438496733183322513416947890518669387256048133435564552896602866928059916948793089480529304261673054147665320883540379423277038662253497561792706676031694875606069965313871021416, 8590921492906678896378420445351560926713957227235538265053303414637623106519316654858858680388567830357664016415076257134804156130563429717920101507029698114059204165065273707432915635246065210277830039845269775627979911051125405744916197098223489496209021770075494541663478261542816375437774633343494450499133211459407722180761806842476265953434065668224752490629180106246485805540777333260100385531830644539401536908161979087070185905273659584851355449083167196113725470070737894996856362343071759001984592265624880693320408861793780641188239219274092706122785333051271329826143776161781288436631722888934524712143, 8845252466616023879448678251562690798307329340790009403446289300428734948299486367974550804903303672803167315323793175517758107699690177542501460405470047925123289284821805548152764327132162938391297601486280124848829871635835226472850797258248484073614030862908180838665316447181775740068860205152303550776258476314449140396099917434488427784579685227672506088074676008008967426444977276431590245995757215902606273799733785103437128677746687835350950515120114439340578176985677978256130436741773449219681045728728955574588702125891036121586626887082920925427369782497578178536890902267158850606592265390865506669673, 1137291165032930263575543027422156939837541641547601760507322210788099249341393114804540475367565126297874372891394011262926032276507568362116041682906791123145963860747782780434853842463936395157517070582970141279851534734962006939017072929363013631599269342506763623208732096416259297718731400694820391635210104908594712802565934881456579895732802599800540636985415210241460189685085603437447571954509193317692485780785798564345530792768813986636809515572987678982486439698066166831441999557091648731249772813511700207392362426456879951072103800762849947930632836160871543681598410709922765452424345873142672266761, 13513807767221454962774765606799569477565617628797563912809798593793473406135664131936547232620224430610282821344483248505605078512656744567449743723678273285531981075631642729094345810811866090141147792047218571849337364726734729429055247719307380263753026740376842451566543861673563644948160144096970352503896388126112320971757785001231461505909797512610045271976200884424014399960505295234790475748395461970766584652942853007498227903733002061388463784848395026828319663949794486867351390469923713806579693493206285468341592628076399551484413083768779249301842099707969260635312935994500672232026066629544842561615, 1948173350373496741215028660780290545121514771666541429917214725389316516099704744675632030441982822048851471807242405077599493350468418243427175247112653693915364808986778291656831984952566832325369705328032701504808067748311315064576551844868622482806366199957953171785405751200403310222590133437462295047893406190658477172918489972788121602667475649200076472546741904907484381891362823762384549097066508901259699930842316143643920135338765011124427125035747121883045917528485256451642127282286432893144575196768052567166517051717119451092655584293158442695122635656563251551369324183388470755160900676889480516123, 3694379847580160611039484203604963835660815577208780146903607949016820301620455307554832098942049250220635827911567826077693631718369015931725158112022767639502401874238604575031054177437045164765611903236258004417594153719365770710448571596542798606004024686475997196663532850471968909521236218907049458255602816549703537446544375095785792848265474730141466688398831809233902146574662791809469706632432806574148439574004693509302717992998560834518126233290875236632494106268258222013605982691185318113673694528293186309488161106261037163626234874478104369474484793646963142312815857167880583154486897160702881783846, 13100710038542426656805076583687419632164662210545055587586737592310789510706302980620569264405360783248277996436146249115702798167955338955333171955392531672001238189514159298774905523553466342463867238918665852032567282134445151077686285421387791100175828117648344224276797822761123590891367579977648505787925172188700165152181711978479188803372382907124058265977868889302166458741425948623658657877794190304076049155895831078270339873829950967766017593828839707912214416972988262048443603583138939265185229104590333938863002633838898868175987402605265883284902740138017202465186038130073550038246010089896603725663, 3852652095822933778046931362644792467475824249936194071992637202696953764275937441277762654667214777690762208114969306581617521800729551998278398574402176003791391499256914310115672760000843705383731986117277642758850882810355767623252637387731481560395505912441813322993671475388814217476674556743472358938701965064413072884659051875760208196906937165575704341807700014804803838470804048651835572006887453120194602339851305565842770834144518789626855360453559616773550460338935135006398722235997124414678750736476504222316254087925756976395641535485434842907110189421731153061525831032708635644300664148210177301899, 12218212292555031547835220140121412464480708257422782553925231134369891943675767028453349535235845504946120458046949499186630221360908373098157344794716844167834796809242968300259859127326203629455442283192213729287881944801076151024158388298356736282178151885464382237605861076067430175912978814749738700955268171220745971180552595649565151466791025887069684021909595988591402706034234661782128769661377483754300601254937194594498452147898805698824765175568533810260146861201279508280547884607541280927691487674487066527311084845790997627666917393787232292294853237534105142562523090298337925617953336382244853752156, 2896785408539675548762728186954553064625555260594597496483215013779182425141679539276525994546526733026872776352493630290006129976480646399840212533092124655542014559467083615157785322073224886356616160266940654491266148507179710840379332033941096884956113201045305429741797926747173407243011050376917364885268193132382549375521197573595599907206875566368916510104820300985545364809233900524588350980968931452949729987917173828548392848659623205552703380962067591196034366037954964360630556952338386795758504508551601840861307828529037576771028918637862900826733051998148235254057176472218330330542051600289559575897, 4495214777104206154002530437474094268471277925222137381371536617146457310482279765513980173550446360598876649316227696557406548143603913421374364361063610474715008961404594966508667237635129178131351833481485010497018867746599052317793997473234460587534251190348065986081141459492732515137295209456934190611757636902123709461016061714356412413273948964326490306870133671246364317671243109642500307879843011279543764710847996925583379703383959543938208333235542236273305015713908444768889942221054292710264184043776812173569578002813602054202917870703910841410711507103553724047925021917002039921756046159888890242343, 5529844141894489844254713132328534957893455394146870381956030559690949307210022357762297743046411917454423382726841931258021598036218413956087240641403304784892150704501610653950162200496671190581234617520418780867840187257266376752917058798716388117989018362837863463646549984829858277851522339991753548773077412825204870946064236649347063984059459248604144327987059120732967246970879466050849997423221488498958998022596146739964376649533271893578633685987893363626780911970270796449409294393117570269554002816733489864019268355073109153801825119316622844904957496279684265904320613407282563631194950599321678554061, 7657120011593963475946234623666818180150961650519952898501728691120557955892745752375264929128113959868100946943714011955565958282126911025102655379200591993662103348293440973715073161628485200332761042547041328733567593604673037669433440663463341579391246652347207071124906384532734024570225933751304023025185754759520213532405042166476618173109991699562490019902979197149651867592793719646127934032256819020659021546070547620991514823448630448275672919447588368582427780359911165401715420526099720759990169336527218825816427599139815418919246745162492106819492298023950847447819932572883260255007894466674329361344, 7835961057263767274626348904955520141645979185947389774269597306809207190775736505642348312684394821344823461140830983808500621643342216042457275017803283991450679342713116864299640611452068690928845633025856512926165365432838156477435563612081555322873080944079915413399911270733026092278436238086963557109392673786993705368957556239605612735538671271826473004961692976438291167300367566932341740612645899969043640819289099089397355843884111614614215048650990844491199723349579805965527705442331349306541289746502898037431655892065491880713269018903996580510701591196253261102716942871446508193647037933334732964997, 11353314051483515551936821503808408238917055051903545023385176875084703551185642277274491393259077228767015423411422895545612938760410140931726216437555341695608783339442760329444053899335372103209133599680877521674602945910141554992545106225892908856917778992959308472715114250833961304535595573009941072248124379685113266284993666385963999176103504284892574508213956742303409090941635268668421005285679798220364234297855905686714654509693459202560872442211131177119111435437721347500959086853032250422784767654803369781417169390270151379541441103777007520967443810986726820653961823695262854029921638404102255837164, 11300348163305588274160436547736333822436038866940587285270441275614883284754283320370750755709719245887699367454997730295274109011039215723919851775724441780200988412837161079112304869844550997305826213526953804022989207469182380814744988487884010567692234634922061173308127004484122429884803927323682178308751205177734801549961508262272107340988822886855775589298642332495534703816669972689483902294731218076230271070352864707092010569575760655120073022420539618287925845479797673381713679165744928107426516279668714852362467481388011002164751932727927919142608616718594258408124871026789188723747022229157766627443, 5317190057185651676864655116193900175661763244958534732953359731572079314524983049850401656789617187417787771870221219056088862989571373026556313098099819298777822609414381859307262738166982542667808093700955630804174749255834411470144685601052874799546197267678142560679394576126742611410003931380249016492977821065715811530654813580269646139782731134295477672629745945991295821444488040223233184958860664786682821891554183706111918817287636264013525344373939534799865409160747080395802331258059560623539475444446225576048693022987972518801389657445288699430859371358934782526846715229174686326090248641441165875234, 1351569408956943907077681510659154696810675040858254191737287684344586639808748013554976975315699678508039390004710684970126992915073819300605817348337891646968976472751425631550615903539712595666404511832012777418584776759248226672826196055836363873821886408897037359543975538767623182623977172237539183729287404239021668169131175456354147253682981126254083212560811557636523384973513712006207797352328894847773433068606087660515915702028369887878622559276250117597373477548645223727125970141178069279030801782167387483388010418464128784411222628352130698190127998209646586643490939906954959363611428483829556433028, 10921155881652869609665933205671338224356780472897304063083088889395938285473820135966825870739261787168715605583849488620086560521961625404698735302670052577374871946299656040125481805780330940049722259711244723584068771100116710170731990243981993378859663422180581706072432914386888707243294246638229194615133543656672796733259502081107035172937898893369702232471711720189378730075176225250768457999947917575898270643612924009871627593078484876879812770142959826121397131788658652681736663772835841868529004318753648242818500239546459789717929162306194223109470499921811566277847442692055143552423960982671888751379, 13502945544330121506245173092042602719766206930773452523150924564875332958597945215168133510321391092767356545971586755777243297952469106049447764137047728608506233546106677064440830448398774366226182093845650781903349402158336953063244875660026259278665460828212275544396722181934080603274687359335988287104668239561438071241811193042264856959037549464090624061616317805072700627614621547894381935040497487576398167244146890516899127945701243310632155239187420953687229548788471547600759423390594893411750051114456891765383337505833298108837399234279913223551265194595125141315662675975358154242531260810721091168130, 14231650934919609121953109270370708872555201995443515127998942284850419568858465731536071394998977616471427697545958117273946536860632592760071037733341384321908948852879109346827396361633907260415165475853757137767266547391778389552184779811336915969108013908616580478836785403185633675530106122097763124256213583685689491805064349288059916736673212167503613852350404518261269779138480954340609063427290939762568933735620800882480424824832949022528597626971347503462509338793239732692453078099553812041792853850650141998738223246428431372094314584688540719081949201342911364450505320979057654482934300452734551599338, 13837418302454084892522797335103882033427895032680730811213223862487574120639067406241863974270233990519761211692078291210782441478777105356669102380326379603233539331122513856676968070547716034121504737702105976261900851239795172134868824500380419500319519941262076160352363616137856110414836765515890435816622916246814377743475863404845936430220297072299322330323625455428505061897461790631930565298547689424901493108544592089288871735792929202103888379697690511946647925404395932180911628150445627209175764441185475737967001489490786039614683936324389623415872291668667341635078533245875450271469849901629204612704, 4826606825742745183613669724307005114089938063034771868288853536223347861442719319224101398198873985321317884008393305616897848682687125840863827531269029496553663250412034525235773350647383821293995868411863930150465605483040282959445663334461574122725051490758020523941723739367003223720386011777882377375593170199823885699392875000437591841495139451356083342813957838532671891265715389443814035896328280156649153637111376957900077511951721068701851956389385809790287728109415651819920032339081196549030990744868444508030312005305322277216079326253284788009856168829965267354792549688471625749195952767851237888322, 14577251763730872959322025543586865626024589400647174959053809475344583855789168067375055135137378725494678299944918789660016165154800312109195052355388621693789524470456596034747697643944759529342335502182492484834506613840472404959962975311042052061666534519259264699145847155034791815840344028433462094795962999513019646479230743789951043280178270194109274382138393863442700458004815721185699070772279337797880053457400118793144040808280622982958659775285783233740387583635993137157139209929188410216207595048167634117973473902740296576844540305991658168281822663668641165492783220189994969123953846621227660070012, 7927656852448914019029988246629498679715834491056307307191234184794128103888816458196244326858496301629158932084428740110413350512112605067846727547727816234775333495220525913438818963301152668799257762039399506422391741752900919697727557914953602299946994881871869901590151374381698988415122380710230574780363435968271944980739001099085126644303864974242000106365746821670856713633261355487025271652221280881321577804639587244700806182770134811608816852744072804911532871960961250872581559875369556450249509627662381155468434999727348506035646982224697868190104727881259222186245308925675604700795863253835392083091, 620267600204153619789913807069167972459624845017553194754290581805039245569964870154616681838572640748903084224563886870256005657735878377138304137414743654138255294249907263090403392260981339752190194701898198761549769667021159967332693229580963785394015818663518471703792050149942287773314998975243045503064784286825990459893539709579960716309697354806647785917842237864578653598802120539014404019516063097343545542456756805063374142033550173121659779905417114395576371650563849639028946798975830840532889487882495816135233756810107804205685897554912972877620416717655595471019604445655214282074628749889791010212, 1876943923808353166443581356525290571102727135983759794091988352777520439430021288068363525771487664630679210158670943127184093293933666992201491936752376767318101818596057505575574647863942012923102457834542708922712464619871850746398126866884197445501403695717432968230536523409125842896173805647175173867517793507330840615918464318859952675563299324852165192048093834793508355204862219252055844472606290065921721101751322565362790378071976944390410775454096478071519378386836689902627147870474322694362268190070933716754662263569229449636358587181594918792321240332665421132131015390358202920354015102863093042570, 7816938508321678362339733437997629634768395580897485874009796669382990813724915718170590762406061730871423236515614597910082661744284433537071540306936411790345785031504146659345977150049441384547974766738958003383784327854196431639822426431790929672920085485598626222154773024153105510307906924683427152750009013785096270540026251477494199927808222541688107954382428764977629578868478745910807865295699852333143727702904721880943045067549338706358419092691746715008435496375260291090039835422606736364900019708671387881059506090796280008249598328994431901241994966560976472709885106949228840289620238728498820701028, 9381419320085926353657420008698841512971503473905218866008775187092477854627867083679092112014289346743550661714177825411964449494668006051549025749305394008472976634548150288097034642196974071195674514354193546807323212690152582815305876911239511783147739711708374644188548751287759010557736296423900710102781444844323066741911134324379267727902289373434450988412065822142731230646521039587645079083070916426619802881027580448274917113850218645247464301506815941111911350708523543353162473303473480679409582131072197914795747691772717732609521478154429335418745111075347509187950511780656649168304663582914227601858, 14589425329804367196377949705629747274814891050597512278986570239696565260482695052935875286037575810067731845542890411179041784202125002477821774025633172972643176721169592746506762705944229980948496815539746464657961229153842759614544401114447581468006411006507546408865865467186141008775030864379746995594162447611881229292827542625600330698570038047643095497036228556426981614464675853644275271372370022698317935486251627081669433742324307720383052436597336108548757455392736660860945566189395073611140650791219088600140743378366775098197925483635128815883227449110735609844753017306712918725490620586658156506920, 7638932262546943160382012150762474443490330224797410115006526616212732560776674766863188274450789399781159095928933339188053911917648370210631373888475375730791521566505692721183697918167224130890467697198572392238845867732367628119931765311341466807633986197845789521585443263148374109945159143958649586824908495581718696702860899364712475019905503426351159637646588179244245544925797163424300190536765884938448388240874977348719016431562431287284892218473247913920489687260575076841033925380875545540753217443659287176653308753081302902543624834743144754553614564742479100096602045980008761218548693887208850847358, 5573162790461938911256326571551089048835924784711152773479398060043252770534616955072221062550672045640366084539155835577120551419676941501624144036547986404818061247612944468577034879556759542670111087395289539456578207374797247228875141617254675730245913746525829584752492129184940835767437520993868125711052439604778800481870710546124783589359069908767219090037274040882233588866061138879189978383426720524326969044031180365386323600338273861296373430538486341285778907150765038834490958789670503907777871427990359414353773311334096739477799191052557491730927704843822028940227271978585948884055361256508978404658, 6316989328179454287926947791936442104657384107224109801362070607417193232159011157938475782206392290081128330998210277107800922524078921251053626340119190603997513636971902641271057303272594828645241990147902212213085402268790475875361301153951109462664705891022098824861141729771714967279129245896495677639642395437380836585586506963423508262822246581947484224202697871588143693747345262640022096022735797052817071349963152291390760527780424713128850429740414120686131735874605803334505474698683080782887991502550241423809893608712391603846386528486255923824737060449813927199792098970478971281199454801298311723346, 15169537484966814509575612733481798158754527049470245280839385822863057232298800961021105733875949545327020153892790791962669727562787724265909068925074610112044015107429166921510816972263389761468600154954950586673418065736367480879751590513123780805028665758058723184815380213822174995737365818448337846889751344762144354146055097839319587140978363242598404389657459367707428645594337217906655774220870147286105403244794531630632730204528597527209561073227068752015840085463798179002702124719392591205376718565003771669481600980492503383677029953821606261000556817344592572070467939385222906571989628102977041849993, 5947593166577364067359008003762446409468299168106893257045139526125692496633332614149966463386254771703902406475943285117899074740237093496861166392407741426698478874705803152064094973847007740596658716313720991658881452573261540267297932676920999050387180386660288547498933954229699792634750080810467597647931613586692444314446628718513435688160430846129138818679239139046523291289820137665093990570323449045644385574598452088838555446847085627765507404261594462513019538754477136919625761915714830185126275060015513857182897659979081896524524048163573916254048216075706792821675071885843851946803121640673632324959, 11377205506539563915983491650452022972872521196892589677191194260942374676469409473620646648018418341118355187991400998528615474082650284069025006559284422003291425760985298287978678092753754556207801186968445777658396711299465345658445050414993138336124035663319130102368938598222399419847969615678113890875023809014542844328689758553531859366329506023439385670738698110934976148421488833153972680280833027746973987933676057416015100520640122270004871449535176192678030314724463276458632330960583518025079732002231708356515969697094896221608046151798342472231592689213650455163045489302277352664936603799473037171028, 3067977817696661677415228507782430971721019126520663151902677657453674389847032503292137480212135798109203592140880362423499673414069537987516086542526022276824959493053960717106599496331820903492710360730873460305342950427378740560338687428924344388534591105670803945873128815263573345158205061131667140576353687264989736125614597240700365344847086802098423652159952879298066091846053275694416001758877210174119916495877835528060119258365983302675668351877364801590528417114159152650516002776508163150956125637238621843517207119296182658085857168384288561101637190751291008584303890685546113436333215955640252227265, 5744067068969497658843411627844598730440164945514574976220753524342999318226678139958499226226139889955728181400303932559928894797395772522655622280554922836832123047145860879608009762356295099371646596444623528540713796692598948149849613099140301866262343669578444096542870678391789363745552874250971282391308514597390785723706393998021553235965540364470176056135884330700114907337197140871073039697807291758898583928990394134368952431643318117512213097357124651810145781072260340011499623163023369647891390437826039023659642692307074831676787248948927172585803689800692799330692890530479934480800096292571821266038, 3728013926543126688351786139913117272019172100201251541493625902467267361319322392246476112481477712239677919152589385973277868390170656320700777782394012255082253352988640934461620526573375158851950428085182023803190799750686288302229863419494406196009088644723761771104502008482808054128084963090020910939807751362720378743438771185755244414851340614475705766206978173067044066824960602032609609605865884927087523450593790603174231475805204574876728307375579867618029736136424028138242771922953386426893273035376267399736944742518495516758531464958711014928753257047050886099338585048756267128856163378312055863300, 6386543051846906069316411939619818474700112510026718846210736801894291572975950393443398430550327450073831373592910851141819281890553083067488544518976119219798965474991444478395257462203479880306667656501512596509833246546654134192958717882506145623138540040810173742865255127744893123164118959892588978356837745843349796686892563879662884844737740307817160214750706073095364614877227522228152233208047373175993555969640771669189465212220970037725171499193598860631796397544923428490353241486544527338245796316802854155142040107026911480593831160061645752260923098178483757305941231517659873049596645667851210560663, 12810054833044488599994030592725767479471644635209917557294327535820424039565282830818401148163021009453145281382263269016465472076077570794405119395660978616327120612304144149062733931579517936699819521488270828771083039188018567432770854279053126941694719685509557356153320872633156168917804779870820806255075217895948655028342272243709463256186480784902573012267098198781616279706411836413710518707032425703222517382232793049148183910088016981397827583087625659284764260751772939842006336991839053437836279248649756882525183715232259815591179259046327395571253782033183525635405420333996279872236030648379476766652, 9790861894178265138649329957975634097004074085609830164719287008550575324660355068828859842461927950485013538348281063808609091900888650504159020131299724939490680445278083990146020460986668072743823037787979054203545372281478036875112066978495243276276848502702351824832483267450587584148314219936466464595820889646540790610171404552612649566885011482824160582569956437449968554437751076495940547429716550219674616042803918176460107673822704177600034220927583982607928434690394336185271285066667863383571505565319676047286936690527488055878794043818821491720029450560136183322496274566147648326263098740876535276226, 14941928582815067425974841172190574444378239822879338173338529260995627110434568877639861590590054943779607255385077210838082025087159368814341551968261996455810115010305194881702969563856839888616117528076294208230476328244525725711451130713475807878941722207580830194267012587346846221365590101243826576266414119248754405195132400233696710187319451958829752315275085866563135642628406846838588411688752577422480982252484661298424116136737484631241981602956131376781197322193303158443968527005443683561826196117528135260067611984882324014003917219138211001641448927103817684481070094094312702971771963261417991597129, 8933941832943017774683760646724508907623488386232262221607013288054572556813776780153217640078669875258137020067228202217056367975764654249354514924648225836561085285058301123641841401430543499351852636063650545231333543938933601359921971539861391300480017844386840212860750146278957403029099461377549646187649849626604094799234287495908914067451661116637174857305934937242289725790521548213794680997519700870878304639389736411222025671455280701740545209723805600882955359665255810420494789178019840670932016226648021594077995146011383621442225715071796671077500864299691672137015425758710688263148976286208742262026, 7189531691622164883663509960181025858001028375280861439878680235525305787870080796042295254315145269383918327594206202552179996171515179605428484916075922713182971786851277134555861370984545083669895591514463050399485841684193344210697147684738962974497987841410850183336125554346866419938469564581022460590835273087019913861526168692366943084274915423319915776882689704745380953526045417912822776241201905331045806468125000892722875855774206528891957680476619452424783749131897935438670356985924178757994905405043577777127814373285763420993526142269793013694362731021567336384732544481565852640390672715358542809537, 6064552638802125806427451167589199521889900865354204125678997956711139492800749589314218614351469251844919098563755809578414211752138055138605265545669041699917824030021079067848795894867547448915492546654151699179563869074024043484553677101518155583619787991865231413975929960385270642023230607248186500606941332522981406294848203752212684946308815631554104600364896252127457478614107222383719185125162890368509317752263574066985639169451449376089169187856689369444588091946263358180271376940612902211771059112415603631270736667411360365153432511846498195215815173264347324606427284468915133236650362977545442455852, 3757672169445264107971423071814182131286130661397989225341545237995405450632725345668027136571542345590762577806221650654440813495584710638745014412429710851373424305084991948468850468108434785766418588531770782872101548942403538716532574928038534558321701788527663676502191260908172493136215409032761553895601511343263713635309830572671984903006985325600402720527475932658255467488213990237822064945848005468719912465872148999423080152087011892439228331043780727161279337197729038247510658738147934424545004369009303555100707166604122283802538534419252949325022633255873513181883152614985949590898984093998647145101, 7932455482274849843856157373454039138379926112646091062461473879083725905937313647324600380583326087481913244603563704633383358340388710872803906662240438983902137177138130072365465362910571561699547260362911924118694970696694270013978038868433262235687643165491418213006433193198931513526352665462217397612407014196565462082268595520498079619361864807339282832715085812975782031986461499566087134476693937597656767303493461606062836333466963564390635712516027271045400640760434116765833634778851636669957160030537847948784324897314979961601315370212303077453007997291016299947132405718353297358905824255008681861155, 9643055526998971723550136917345820148408543416998860032745612724628548867044560219596393254094190952074352612222895431521931683954942378758887921276127363349921967622249056182308898597826254757140529220611698885141373840347934664114563429746094308393425380970188775152045908627628205872142493047220330353863435462580164896929029103159191720337770427661149456927984023689170926019260487654653486169259046619471976701651137658851891431670548992838484919486390630400394688398919941591580218963552241515606018292491179497674927125233215719232894406668298041893377130568935915747724926618867327795385631024828666992247290, 11991291936384249369299698960518452849197236702705046670797230536490646232574266823011882047771871263563958928292883359281150433470733364761531682307281015423233797307425849390952418769772954627375847688808019097402958253279005305321654839119431551961191267150730556191454563985326459151647722217475140922045123105154751577287911472133757954746059443387035699642090684900338481407677643564521515154732780059546256650900748321637805701916685766926209830275004462112351935656979999855501616137571087167047200300961123034119495151020236218531255368763429034677260560791839745496161699745648261310859430418928259838821877, 535432114057863526721782434773060476314783390601088957460181851546342640883254127412123051617696298084533237135258831964495787908557481727452476303462875525899468898542147490380334856449499058330928205011270209234685730723864472225095065307769448521963694951880858407717685485624188152301124295278231651350481300454923440559384718572957516483393533015119553955205313334306421947123551979954996730191124604715274005878039845010985536421909520112125609958397202341572239768413481386022216928426614920006657747275803129737848798924377678218828129407956211537817653888774942399161098139151280345135324439924390647578447, 3220011893134401371685402508709570472954321680147572400748655907736116236949239232471865184735935060986427421735874400382323708661778420607205643397120625212149915957123206704115218408307357635163567836539740291889649945922083575544531026407704564852193567430337899525651882563251489935659434862239585931445386182900475111383035782777110957999260469336596351264088257604776954552644350647123373029487309225329173370793391298008274549644140586551594364452972663976771502258875569895740603464426584624196673298237363374673926922455688177544649002555892994236167532271023243983655761171318293792377113542858566178496099, 600122127467611861535587750203240963722874764507701038574617649105517093473305023944722040981050907794894905212292005560707125161493982695124762995975561806023413711807655068751569919597884466936104514030246037470131236752735283648245689269062142040919305342933627639120706635587037744802907827081604673022771273538534733872678332193744014523171816720033663200154852989866810664528898786921579631462648683949136354120240536506040625155114361126304505311924724932810624031883431945425014700535632983003379206542396676369759375253708692839310942501083016757146084672651607696245154073463556817920222804497847164148919, 50339512756553218623275380521558565448522193507925069318597771693335727558645505269279849795689316025903371638062876838537481809174578837000746975150264636295515544549565932864086631224480476618397606098787650961842917904322124283224278003752654627557489493925252640851312485394751458689570792104787835243865990881912516716525586110492203669174057562631787289272078652486184361913997429327414173045545135047551050613272877244505569286519089174641129008448747456868547415740807138821776024579954821689809965762676749324884212104363300094487322179875649780580332349914589317935624904109987599308152755760109143998751, 2224052005319063310384833424571934114400672558432404242381905814511179810742030560350177349071409363750758241338680395569734118269781584440271895990245604848943806635157416514113258827374454952809970271386110087207508607390430297238397541176592036684563957770694483227502809589049390218716580287319602904576531353794449649752291506567150970839094403827770723675015315212078408652075616795416368705882795103845032693417192286782410109366855505313733288028208468270805685771032485770634904973630137084989377953129799398695697242170165528481764660518305154014425898879629342906389549414591962229397062951169181957613772, 14275670029178714903570161767731192958220334072487644021135501546154111018394507711784102560675898728703551625745188968783353245055200924545127266579966009234810166523868529387643082883396920063132158864801583422164786381216921410297796749913731310404282342028039015946530818270526086443576375122234693984977205437699084929093584215611860806604287366917946728372311689443012961954819905719979378291190426781986119706110863100933299963179506166416418054362453691479338228849129764521228492880521802440955679378275011329235311197539812660608180724223253704604510134527835590821059331109458744742818858846356253593919531, 15185267432573639872076451132381569108753197506130696653478204442671128758434601622689459772629495431846087048936093224045313962183756777493423781016880600479033189411448283857759357851994434290310594725722879282332643289647226135888077467069738865968248849760032499611636818992667031741275200673818274894399046858443812683901145769338502611405193937143715627051494420688437190439484530572665252784950524954193813471431595615326555357362633515516288947994386712464157832892920276023462983548902705721189213696133154874467828534425941602843750295170291794415853195885281848637800437396343242095744915839066120343669835, 4879612428754295937996584844091512342716460204385686317553157289975002514620577593461029415861271197762441172875278234911205482000756498339763036950624564472636257514773519763666991573860894276474054415661963387082148717148767197550421064139240397093639320406464471250749794667740342232727466890999631793412317216638922742472659285972540106866101582942494555088578850040519435163083990211708703743270478476125112243254909428357352375797466497456095306901543973138659960199424970345513286107351069292703979769192976611096956001669308704595069094064027759052255441962743707680906571973207705878800116890860845938365313, 13435769058792763769626800085331577749241311952820804865145669377919625981581930666008825328077571148346388301555592609695394682396961076513311737816689884586045473971108663893952535731310042327943385167931931292074040099579338736066141894121948781791059561614055815752555628118995199961572248091297363156939872455241328696005013936781034371134327057601448521193269957794508387807195379773273424271775456314422342642329396116104834938471386558748037037194676893299569297051408737690766559250385415762912771492157370721855236609757206633273674544752588311049273127701476107995180392366776959962073751358804453934264822, 5542391033984572544309028531389422971749386287310398650064759146056388139061239743350966248739512828662896288019520288789169620634070690325846524902738247390553179708695348999655663004248286927459903589852764109482892918049412370269451893429328376067510710716929724521128037362408634829718638989649378574944664300430926714090821349770630009233952908142218164609020667984529215493287562346124317275409239431987965976823163648426455033785427976663404454759315964366873174968697119869398126678051558414223741447774769077630031896415254462323850019653881007037612035431997632863402935959031120710934676652292745987552564, 7803771781604746567978670142366176211984105434265577521767049566379964787078616070698680678168611174665429405417360935498034238714028357563441325981892258003864290346670241911746376332239643594850716369803549246294442214035293785034621922255220635836077225479352277029220291866614319421647173230321410480286886004486084632842728845734298495565712055426737629190015118447709093852567572090746746050779709718275402339813672109898743347121206272493894060986200601346893915910976840657529593720977557535780309071909928945656096643035960534235851024503316616061477903387540114187195071552617153258585962762789075414254915, 14550724562704244944703001094464708866118583220140784805885627719365556627988376278754707689093972969349178721660857614321368932723144628948795449510718735413720101787664412941833526358101398817245437043857540957492731059840934120463645319480246514699946076556700094958280111962658342779338550641756163208113946017431633955439422681536586526992494477394950159923043083987374929069647572056298076586571294730893656686542747475962224078283620769820190726515470370511343368135142558003358091412606728280151913025167789010638083795849306759853030145372320263447336943700553613116285561830879718369554705010982278703015146, 905755239615698046917022704401444719058830696106792105613543070490366423294837441201806258289017784280371737165348249248540854504265831516849018277416932866299336239106708674975914941807666993305750374858829476210791273122096544472833319114105444370634112455342146414479012688814172547960236061374911624282061363046783557923827320816913212999080823079317544299850365273998799406681848162954685240532278613419809460514237902043544840643860358949307003764990315636348667272914654500775652364776790508549048920659618418289189390271348289806007639874838125860129786731187213522265469446766099215974758176006605295618767, 7915090956224022374584153035329677930760602324913366274914099616372530014821669872922029199280579673718360049211187283454036357627703010146787272540387836186310970471921562263287618743609546828045818758877660800866975304702304781145943396854041288746412787575424739458089628221000536116492000890424249362235871273868021938168254811377658319199786374987384702895144976889493294593285522270424742879586162359966454589990688111496105717457074774054811268352170360883117172702503937008625176386334487901762750645956269186658184576645311174520095229077940637672105837937568215335574573338945448208463183181650200574319521, 14763393385290026733197984451938251764500304950949477862517410602831207505119757773656807829542172390446444010290762471320179908128187311008089883939249276413552270059861673891348215695607497457666677564123060846133272837927596708127198103339476850512330365278945869327209254061050089506436848446321763438343975374446912256970106369447492988471712481144621850019093302619134925684479372890232199060516056309301691572273855120229597177989013483276068808539109370117444484829090496984477819390567872497246027312176918926335452602762312180977819584817205669476385354295783330428298399415009867697107464325775483795517013, 2150968155803335913363944655799048711177756024031497208561219369184651823411896398206103053008309258010856227320307405212398634256897082660711172072445776859641396686863798236121046149607393813988895924478736961764232731564685259899357186507477452666842292679644633002246889962808183301328196650745647952049360117868327788634205413595767393904381245184639956811757179108236180682995963146514385252570925670308261918433799298249053395672766651837667338857997840793025021032238040620474800360217807228451120850980707687140925278309225341530944521350999129746122709712685871266335998732036361963871209292594802524064101, 1621247785994414577096336196647521349817049804990384617464952973203230306307857922207468761232737599901164753791285580679538889344111919552515408202260470616459201407453582942612182465243477573071487434446380140259238805756369920645142256679935674418413360056180189060733418103577103670612138756542234369027316020275787436503010486414069881051181338543909351746458728413404815831543169362161966148295895116811244087835995649375765604294021158802779625502233442241495631937176464502661240716265459140132115036716519930252160167771008304418744537536306813506291748023693113555720799359629144460150230687796932042872788, 12653661263933313158010445295827911078052091969010093241210145578155754878979217485399410281534812100929813010419860352532224967167431622421039500495670810206747776677024105707782070259562367678861613287932741930632463012385574522104482010838696309575292850982449178115041161849285350620692016969038794022625011172869473379878596332964200046446381652122309043885596860473594957796503920623875922190031007438114222058453968936876256694011647084188329681792420409742872685859056145064002905732635272179892966593625002291375760264116889957423750594473358096935392700461707675903098779964480706150298843472016713620048481, 14868722585432620007939501680935571162388681421829578513050545259008979163047733359580356950992297756162145479919874655543450474972783321515837325514292960384800177141171434665364085523932526547918297799064135332986896875066234825475731881219999577248008180494593013499536466162681794510605863748906242245161867234483003972786162175485163654352303622782325270691241062282845984054224234236940136336914114004334651661957510036702642949240274854106258897602782749325959157882539520944440616382180589134596567236254739911284646573457452256101251961529913173624227884785142791559516096027018563613676698997529068628822733, 2904894244506373336700029430295136170411787536172583592934412543067342684987464336340696718350799815451180187771580284274606287155951795828004750429529935433611907342655713466726831094359657043862784742242155071480001583543128061449385899856663521440050916449392455867135588784009666418641011960669211873711582367082203767946431279485891981969382775078654508040570714070407148618123618606714381513626301740190610436677744321114469663101719306727782964486133073639902742507110277175711469720548065188912746589626340332959672786629839002745179577537221513924970149632442104756092464692305083515620327704751641094385712, 2311496682794141631393420771709374663788213994503027855766651012581376335568105719704931207071834360591533363344618424911627157460583965571525701960142929716584817402580657054549277944994182188715943759153621765610865466204024604777534919347801110823949525986038782321751457918114396449189991652197873390916863434743323122586527929217668867770082227439982318755730818586524576788420303869223274094565266573748173259299969551921482979793337870335831853130918886855205947289802728270019087116034410999353521654557806069182995651685981262466235295952900547714612846442390404213099933951734500758673006253643940947086008, 10117897844328142554868011629224408328585879959397771398504408610738842585832539484663480981437647194604214719909992685051999939838608686081084682835419220976398827848486553357549292079257306403769048998196611196561240954606770601361727287883238401093766508916929317946918613324823317362092034591318445144066546042427273019549300258380921594913902001986306589011965666788178679331145858966700881551785133817763571902505550341846611179695195498270739226440723926356944662002221523572560249339565306465693000039318230644995458965366961356285492950000214489533646952111481794205036614639206002533823601587340295828370994, 4587235939987152175190427622584103868490891054186671469570586151463960185396121234316968296966658157649490438346603705741652328121958970674137717691454750135392903767115604161170135271543963021530930855146085192790012307386121668276002640011779029154138658580327036934616621082855150383642924499744251880745845698583828788678539041126320664372702103274435926243115370424243252889712645839115101399022698426928357971647869985872493436862410636864183762039651239072627781733745709849370970612899905680068907832445824298091930170205048445061695862130970435293211407006758107672795911793737491509504926456944309881982063, 9734243771507223400094729866441249064234301630037137864752355688924381135451313546830773230943980367164348995891412212472580314086822048980792893434887515259768178572523325855034106928532755025161856955313795107129638991679291563737375919707924222328928077876871539786925901609947248420009157216012585857479775638683738435966114050922884170065985793065933136009517888090205235993284455287104589783414595864852228393012276776801125825410251453177409914255568146312776814719830324106891608165166295787305704926397123654471021855824974937129922447149099718848275610677870680266085883741199452851548669728989224343773899, 9524751900640364479498012309668638994370791138615820974704530977866085132715519345925617494448306574688110083533886745499679597773380168634659545344892684471115029107448937323479819452236047288512404519536913021005805700886162005889705833019328032574096034116927149229382109650209107438127718273416332819082241516461246218171832411347554172464171271404922397966941970036412217244448896270633582359944514721065762586825788974097178203233796669379273528649226152448864312976163859241159421272655047597802459138931863223442413969604232069832565562247016042938436024799287903457545760076019985848859749690917845223646772, 6536915891592978945445369842251656498817857264239331442302402420830049783465718638399738625250702336033555266286659420999658949721040058295705470936793472139728282523463093820651530965374114159399673584545608457695240826571324097122201509456482155547042374032378324715223783186052973928587715806499358745492990058522318345804530601506883208009167959005089483148880434858261422179323896484164697984638156491187655636416396929931051337507799269484921436422842504413949274990535494507570031977133420340615831153297111063761288062839360540272292814673668750360915516864560166129454693186822091335182502264904371159907778, 8763858311153858089091251038913957850703267839149826476795030913273996626470115696111847365469625965769187125066842162573743556870147225348750632232589385832850469901157234182162636472802018846126743882969651303207454919676503869442938104055296302254346374346068521381054011081656169104186107189142968206691320767308294152956198039626042980846365912306582669367631060557963086678191807496485935313252293213351419798785368621926603678401877114710179488096702539792495997898049561883173993589662730552278310429749628719178776133541261696625011729689561072557382224732997323017903939823849599038253861922570822322820276, 10304055861959903628564746443884079658351658243993068573334889760638463424891184889804452600302018788263977157330137399626142471493238810579422444893878535949408833748921231931032995043898521179338062501479622906064161406382177363491168948613310101548224936388979895595210747899639710435519855324578874416098445986110190998007657658033137332895083663322339462689653087716220505926783192851034210001478545953953772290490457886936536262123353395710736192964692912144297136701462808928618872742872081662561345888211317808837383489883198622178140403249909951015310658469409501964637033684844744097419380495978652378530590, 14726340382389201981076355990454933749444735863353274018300226923350606166798930510338215744409551071236213258959785941777543461416888515060553450080546945226599930884021760578146826190380243514334898926029752256996514817331888223212619376148871600388912836046683943461422881130821982347868218020075045505488203309838213572747025496047530186362804836482205802581206392014251998733184109739252212944535175617536446089111640943152520037225509511544609062905792894323389603110920435919909102123651652804588698116132704777230659415759240970896638436469245429551782628368860017693353785302248876758620465407470376132883291, 5599860591487561964716668210709891276819258051334913329818114435055876802859146828098080759330153387653100119476058042742333340356224138052040431412674919105182622428202100791247156749801060922968286951288889779970763601729018054408835615249352231256072020958589483732431247365364610622216980952118970314513316676713926958581047757755493384012279702207656487266731989010905367063579901512845112407021906532052363064361920080023604157294412015045566167604691002342575520496164358789503582587448492627476170094790170749377500688934897762307400705306084636357255443809776613633544032895760971886930192529742051400685987, 7284681863487265391975348919356990710834427830336211658438794920413778371087625936301280861476846527447690148243948914904749064651294882224202880958189781601006957746218002224828496942001862919753723795185985913946073098029587410312298432251663639205394865772717411252791851102137070740003594281594955971942314927045536689407992538538908768583435958187052292896998345905135095318114341622140226234431469947234761309607949627578172259127738392293739648665322872160581489980676455114901454740866994466438467703214080056327294705089107758941278308992503990002210564727054321740584996808616669732313919614946481462835844, 4218644104851503674908335618324190458918353640979450709174985494086644772693888285345167522531276904407777923519727833040474760645218964665353871865271436639445357690968793378067696265886339698761047867574581351892753525140266203868699974425144098602963165461350432213438525620306578396107551746424702245896304916951306022323518517263675997918680052333918993848772489417782953820606330445707231081343337061105927736500164328434626392964708808370826632373594538269317810596383026952685342820735431957139112915830275509992720289836507740847425382215602427538451767264337906889870491464577704813919216902353508958675657, 3672490596511566765203546014934906368981891296242298837341664823952197542718959857623660644000502506879446337926287940783604560248421940124883120304322804336373919042114401423441194422550605353143138286904783074470904252416656295042859735444846506089150768814937568090874160884780625373473660653610401924120876477675798543697640619115545437655461201340595931043277002471886509228395808759370374265056026024599676247165157846709075227706409801838730206264031201772589426254176886587455834782467084855973474182708429093173554162692807917064547205153992896789225045606490073915230867234814142192039039186977582623541991, 1280207537632386354095168594645745139800033256199572667391263331571431259341050067911945186686482088984279507592101929090568530563742757379154439484391303366642876649942104475779358854097707219003659617824423032733996209532412339358588307580458613840803495726952195629346638462860734997635900255432451049953558399424955070784426905987448831573109818364575601864657778702125662281705821672639181050096970500037835145175609289872368106026963689041126796876022753001062422368000963690325758995290294034719103020941655230530849890614499072659200706945379797175180592819900448774517610011420350291882830962683544583361379, 1712852887288208728850263360102828405532867981117990676104988275083835100154395762305155676788845488123596618035049120063817401470764810516234363195711980024295294614580706542069215574499299259546748778488278187721616589927510040339680492857783746131516806864166248748174814753552178483515357540746014581911497410907664268197848854948390102048396788624390841066138941548581656449991597764113606784331561791669241168463770037794548948337528295591533262303994768702090891638163379564489208107657803500264384269033874779467352375563064216555703447802999052946344733781030854695768291023706244504481654025894705160680367, 4431355620488982649161592962565317592196074246840668689829552685975571072898550308441496420304760549363267267015708985131070769668873215698645508024032418557499365274661957102501603200191497007292017973265519129480232872076410729880412556049422997162707500159504193181621350637358277536523148862096467158234995065716025432547078048958330780122712083214706241445610546030345699525776977421932192560015568960275308076897252086297013105798511322845558782544907676153848356707540415892940997174646395180426720560282342215294174764345782226301366466949655945763440960802301845483963562699501549284665051559641116730271064, 151880862766790267548931295384178655780310339535162671301084454000351564148877387201522010524511060176936135824065717736524998485756807491787511598453859426876046152155609330734232088716456827747028098827416498908259339363197706889262333376164123757801863624888709948235034878100934110696685851061820438712409402136344081182176180861748936207257413301575039067291144999442588261090044098295904832386037051479211241831251993693133979390359677388164592536832362964085108253933527515566044108717185372569625990349924960150872967742369156278005696911801367754186267082039740015781598286019935335260230154588146194474570, 9484034931276031132531963944651896350789895896461790715546579215176264719586629759948604137860443744326010201227145091634385183753289444978389776884964629188781090430214095938329292803406669876372175186495894744319714804810337368997181185087019639005033503349417399678480994901307634080924618023009074231824044105422013232607329336801445993122319744348742586696709304431718981737020319710085023839524741523002295255110491665519227510455524421206461155186367979774733323367247057775210143794465781289220390567563119466936158692159460076442310614834206342665950603105627872425864298849858951309156808082002452439252375, 7571925654760390482758163502785570636415340074376395512511566382090898408093888172845542299305123480557092551728329622043703281862222797484472838001769316090333655971518390269044280128908985547295175688556076050994514503756419730377240772442932139894970565925755864398733207809526221895028302743654815358965700847416420156786060644227496789803454837651514842218394209521547888532830641764547720707062808483281932421750470631335122609774959367466533836079919921467710939774592164364039670117932503074903125902581093889602927004143379512533035382317879349531360523514706795998894620784432184964950988980909595752363891, 6407242458564458605989587511182718985516094933911484897577359717780776739986097352338695025318316928131020600227581257631946183306976157385836796808768757437700457318945886155356522094058824299350704019049355567347950163298841776910197772237827631473999655276984027656436342326224553937882149508139691242015084311118170763529246433945081402134207122136801590156411201768445377350965027810905600921023414736267008464560948603367869469615355754125562183214690346459023615799680037125096284762140484819908754476021025094042209800734064256465008427694884056306700228286842316616273574024985156127411412421276908819046325, 1582973058630839374201016845587895187514184456338711562603058389464647564354857518185777707067534352738422221243872621546790913024035141210308751808035033403508675800690418168791480677811439800763140381805978683017343728549585793044134326450180108362717333856096542671222448578734360169509953605279750835886609990527940475390984025731644580342531087058939615733750763498609323959035000197342557541691877906461534234845751849332481544519994911904816124667302855836989182149196400290405533457661829694605590638144618216311896644287846360917369054788425992163463639937794227562814960298002860709306544428349686311404972, 8388015083753817396404634498682833124836683671660485453889705362279160874113976096738153723449169481885447222156217427509343858332778149307460784057788816852773238473735797196152562925262109386268377005832211979197341745235152950815021307336600058594016692701569536560183900809315167001507909905778241359207806264218465274232258300488042841612249765945741085272980647205313951530101418826813096576267892094467521521388407855400694081878769903840814458560849614556706982030343107427070128171143229655593040437235274621132018338475980754222081676543951773645671723305719447701663871222424115036651254625522300007239701, 10360941377589999022884694845551237952313651488092752234649767575644201444852340084975112554641538017252967970972957403469841755927828786235277889366377352903779354009188274474957839495808036815048488352099199171067353370582233123062854270327278611899110567041211285835664193384275654396217606545976221188607145656891324513369162209324704100876407219674076329493105327684033551137582360182876805940184081838609222513710457511996697851978083979112522791428711457760414078438660045777781768019100868178746924945090206469745588225371455309918653370882043866832570514299530747286071108672487459805604889856610219366804014, 8161901277931264917118321806438891982202459388170964941292783162817780535249918112011362767977501016796186950982925784123055737546728140139002974376577736078814455520715324277366410323589568459000202785717062704689299805792262230045704532890430228890170828537204236829122606564459083180369744253692448209028566213795360522127608792223090436338427386950676480928525972254897349872989084292693044025672191209560017949683042024981585613220102151330914603710629813105622440218241644321683880490890195924490483901102869498497598949099879463304286519916279176791887333598605029626783283403707240923608501706742364927375755, 3782934195580492970180553866690449168010554186676222377418642624082619622859185723632805913731884871238511062871897434982104311875969090082587357096919684332126026810464696214804435658699124624221912695831411261021231266007249592961038454862818925502558482993002316735563151406299564849453648995738323003174425196603882980739318361661030203486760444364981054604720894314579655693051996596948056646567854867442593477678298818302489675363637454575898939148670286200131667117694840159071023352805842073218091565232974675345213769255012314089478053043859999354934245816908321254655470259685403484121721732410179071909610, 4114288597820022391125749188593027331026351039891222488536665213535380955042348711292928818299649797254047980414924488507472673794895383345342755166338719529629024257899708879765175623019868958302420946489389732849538793053839443691183813115596740255056419155265900578687105616665757027809606575582356555742146088792494391267341885803290264524421594020107904982737546075821190809550246387205502119648498927900788485223892423569470562773532097508386244730162864877944588432760249428477514334185668405238153761731850875748256603557178354672438459988042032562814329971608812515437635295411468449565452675942774316206013, 2468727754756925819726861736190593621570046070871578606388696474245120115522326636693130800754080546162785192842832459057836867341368082934906260069239112961361692674650208597082199887350150839030058646994785607426625727970227499607119891164624551142853858271042540511609618146084904175770636709162032909941429219734872961413193822705315842015365285572086085647286208340120868212089861253380516987189869290785143340973734685089531458054028129325141655075320282438433328071745815943438030050163239166494145939144788889434940446857879823966791075081816156226809238767119154957534729526282707918484809620959504025510233, 5041583120384178574754510543688981082040786059980378870869528517432482880646412362035353568647325910788836773038302206401235636240338444958835100646705735328715604610231176333303643765405591811730634011257239004081881887737235628184117405520828122129872518662873327501243198817273583721212234131948724805119027093899639285588119846447228534563699931022861687089824617389295935458023549482716471562995496035039971509002778768230183266163952750352979536005821487905338801933287628096411437854970267226157338195424655395101974161257085648280057846927918950024081038726269481291665731476455018934720255596968609432126352, 3629978873963365713741293889261126305566884657878540878807380681141546011975570214362542948053419920414211144704219306412388357870720062302195338375316408028635651420973098109381976668448344851960334653995430945714115093796939197394543028081942953296541913643405709442447842078969949410043830044362615696580259777410007066198762944292291103029467510065924722224906549577127621285748840752548745135992723308600452185065036513480583509838475010347800214539512382370509794246452027711110224397889694036954365109376074293882446509512060824628361627195391124064476003663926265210359146847719930722568319452002284036846095, 7465884946864808816280400983921745652219229053919294972054563236224428084190170532445027972732697684793483179410804714564309726525353029932194842972851055112308571160969547308519376170012231811908010956339028345397423670664169287743638878450295116145909956614915931329721502899329483097078852781221245827712109449889486791334663673535144850500434760842655687896533350254346795876458494274878983729112135056763392168367015761802196298757300377011202516526172245534298113864704724948443444040718818888904140779015377662182720446432451484939660097067723388289241439328930611237639471279028828354169293414805986615310310, 1896910503688876953851471739495515353616939763519846984235526999312399689704270907725479920101085014190640303842672895668870303047421243574875601258804726531297952143528558019763378508736919158794601838339326290559343520786726493370550654638242868555375944685955808937052985027827276567300966879391153835453735899337934408695318353937022427261586766741412834930980512461948246300668891525818750373781239103216659049912060640276786074091742421383051496962688122891703418558216856523195689253840489810912141843001096981004337323881864785544633182926762250336752052350749110334631434144787663360833417650963944585434582]
y = 136437248584749771882310599149278388531535057166399265926387706469408766646754256272579824944594286947565201090386154252642859489386692473805411897253949013507330688499956189228793511815053892879974238599863038816313198964134947169977378713887483007849103288310288698573564963610808423262228756458677190730145
N = 15208002172852064705513549049156125156229213752159018163825621612365155017442357321243997240694068589814280403280924059115680689958405528673283969584726875025903837971544565855345730100919461985993701827484692130096087415066915297046298354141978649627535608324891962634115164448150854962245168416609362554295547467846154568712738134639516660184864893586000423886731114509172379025554849606702807764604046562890333894888196970691461892191718079065215120535321387122435702257687877333759869565354852332910433540118176537491958544695956496612702255403127864825597702515541366203734967406176296928067151309367243599261047

# =============================================
# Solution
# =============================================

max_flag = 400
lower_mask = 496
known_upper = (1024 - max_flag - lower_mask)
upper_mask = (1024 - known_upper)
known_bits = lower_mask+known_upper

MSB = y & (((1 << upper_mask) - 1) << upper_mask)
LSB = y & ((1 << lower_mask) - 1)

print(f'known number of bits = {known_bits}')
print('Finding roots..')

PR.<x> = PolynomialRing(Zmod(N))

r = 1 << (lower_mask)
ir = inverse_mod(r, N)

f = x + (MSB + LSB) * ir
roots = f.small_roots(X=2^(1024 - known_bits), beta=0.45, epsilon=1/64)
if roots:
root = int(roots[0])
kalpha = root + (msb_part + lsb_part) * ir
alpha = gcd(N, kalpha)
assert alpha != 1, "Fail"
assert alpha != N, "Fail"
print(alpha)

# alpha = 136437248584749771882310599149278388531535057166399265926387706469408766646754256272579824337507311270141846388413460068357591608585943215991636909883491826121544218636098300792976192313647146944748229438407801334865956608317244973051161890353895660399085055691697783021603089766899505767068206163163800347041

flag_second = long_to_bytes(alpha ^^ y).decode()

bin_flag = ''
for e in encrypted:
if kronecker(e,alpha) == 1:
bin_flag += '0'
else:
bin_flag += '1'

flag_first = long_to_bytes(int(bin_flag,2)).decode()
print(flag_first + flag_second)

# flag{y0u_f0und_m0re_th4n_s3cr3ts.....th3_fl4g_1ts3lf!!!!}
```

Original writeup (https://jack4818.github.io/redpwn/#seekrypt).