160215

Ruby

パスカルの三角形におけるp^4 を法とする合同(1)

「ラマヌジャンの遺した関数」の2.6 において、

以下のようなことが載っていた。

（誤植は訂正しています。）

定理（G. Kuperberg）

2p C p ≡ 2 C 1 mod p^4
ならば、あらゆるm, n に対して
pn C pm ≡ n C m mod p^4

これが成り立つ最小の素数は16843 である。

このことを少しだけ確認してみました。

def C(n, r)
  r = [r, n - r].min
  return 1 if r == 0
  return n if r == 1
  numerator = (n - r + 1..n).to_a
  denominator = (1..r).to_a
  (2..r).each{|p|
    pivot = denominator[p - 1]
    if pivot > 1
      offset = (n - r) % p
      (p - 1).step(r - 1, p){|k|
        numerator[k - offset] /= pivot
        denominator[k] /= pivot
      }
    end
  }
  result = 1
  (0..r - 1).each{|k|
    result *= numerator[k] if numerator[k] > 1
  }
  return result
end

n = 16843
n4 = n ** 4
(1..3).each{|i|
  ary = []
  (0..i).each{|j|
    # 定理より、k % n4 ≡ i C j mod n4 となるはず
    ary << [k = C(i * n, j * n), k % n4]
  }
  p ary
}

出力結果
[[1, 1], [1, 1]]
[[1, 1], [13634714641176262901354456011438079440751956940137509909301874081659507665896227815449413465967428214280630425039072984286393041076249535300232866081429007094682331358254791280372476755202471244097567527914494204486988385659008873614423042392079340272095580540111525960295861970617065242478969793798019747057645623972206934507726393273245261157363823878677625782019890917148547070735689350550884374096600320204501982534626515314393952520483081684732210406523256366708927536021175941208120326364130273731574173764590701989047028753226877717748078221783340112460939775792622029507434483025899851968413415421327179385035456678583020393227827362640312784331307679733703484482404291848646007942047593013454351126685955482285716907605631598978929893063301671913725096818392629449963743405486355074567501440819364876304178325716269978645218042908531570599217519433781749797994712531187893530057931912807277578024249153302004224818717468427077301543100703397704406215024571654887324125274954788978083231769662566261177696510275393231177096937321386070433489257483780399651556377625499506628704443166020506829419518148275004526153041938608106836295183662495673531582009256728012687445790025602598009771770276011280195521949845281413124061888673516227951564191966722868161534455567641123286082112170169899909480165187806041557749482850508197122974179885031572538059127882466321638876686125399579308868273135324502914819068595678062861241548606960778924437692166525508830797979403835348376499765123548528219489673480721311773956885535397466879268802881066232572903583883084702587887412897693226575193463417535588592329308974929989651171088769467833178776332546953698070035104118529477912888899825016936987844429293715176209859391628162335109803820678758086490086839391108183952389198423372480242619367508057913279882737876011793464802620051087711895803823929498698280197162839235251082628662981295278826460366318434329643340172006508385384890919888881126799263563104854363717713356572423893282497064579009274550486761229119620117918672772045522515689037242653154237321180051349716170289709457836806167931880293050983129344209269921251168827394500775936294848373344319517329684826410109898854300360706540034707155378474377979516105010877686573326021991782952307948454410157103044789230475951269267290388085614367038760143008203609025696708894371555209490459566168526107125177680613366077185155821557823791835915976824622941678545810766783211744363256818443584381602204870429417464998363345049354695171079890974947565226627287646808422450428635027086692859109572695798537606818088018804724121594347013751928175490567877914680309221874642468608895941048946602425827686842048507968516171641216935911797547132543503920696605406707690509209433669341822440631931911082449980001256173657941558729826809223192055681295793205033218764151601265145547456258793704637906928968243696009959398878360805709289730215387941183468614474556420160493780254839290701919228847396438991840833812781438742717063767645253423828504273890230214532042565386181252881741598168706520946480651510800703046248697766140502491423968994333523516574564957288740184932948068065217626863147489795403690212089571803574221811562743015516592344115611845253974083717210871700769367078283144524979523367609234654947536215463373910949464933463797083630641398281545625775934573955202226673248753072227144169132014982101730867764221327141536208814406419816602558184615127787768817978767335988216987990346255348584088006600764452355383635751168598187437101271643659472033712883342829084461487585771571724254871625674124310002940081104818757236584540299319343203957672994038671237394996027505027018535038403861996987257696116765287184150819757854690240339991915374971695492164204423784915730154184160926158198054699506260553422907910093659812275806600232361782947333355525933496942772750277148609198169512153251514498622776921853012668850942174740870211571334489676305857286458236950831055052978536122127106977173690356809238827919403994723827341299905862678995772454234232082110700029695615053493970971063464561394378121223148534898510950146280471628460456133391348810418605562359885896912357138956383359870930603970955950505020072519603218265806273824625361106708149604612043436226582646831390049636158957937025510592104278354783793911223895891848542935947427677345406716787743525517700263725170729494573113348135494627278767421671987957119112648719079111737642739947042298089787823635170390894252437412379008002744599559332068703757741338996383290894669842491715518136451957294093140541317847003647797917963003243667173825048778756505166786476578580677212248573121287001004776656944001684099764641040692621636464123919015890077405689568901192630484755907591807001389459615205722987933615598801143051330291969445200829004694859185558117542555392002377862866901070411855128434793695494264756859714453091428399701108867365200745203566922604499345635400784999419598182077919887607910313143214223208804134432930309808046114040828675184772450687997508570582214274929720140961900147880290818120369047051285839150958568390709822585875807747327530183848555573453469678735096207031111743844638539437883378334960079688870175768267541829628487892042888058353707024942429680281603654386735130753466362486892191251756886136658857204506738942609444799428568991832046765941702832616896954357168019049054186228001034671069573186426195079481118801699509321402851706467771909079524213588824663242165075293824436855848974016925459089736070949399129083656404971842985788458924408575673668621114358979974769141042119638247301669861757178879429975402548709147948147127648476722339150021218291166252301155232011690870441188044384884241281511295926323407962026081712733415043314418049135580443415607771671043943320625687300884586404289102261524778616668023235255012406627045699217726354532592414965377130427473000079982756821240413581291382995760768922817376042663117270669149922639935670924227169692997128794323366491142516580431986081570054932547318779538420579357119944185473105423404079702680469768554726363193657970681124283065492490214612230457822933168529106595391989334039709030965824059900173129615688100311069849472228716555384881963240552819560937648771600917681940286291052592535644051720676745672428961551991036609294767451268992971111358742880222282604089883615341786548163048742333329320420504610431114353512557834738141026757833532195827560573186816241306452595949626621627414237131628297751746246376619829844060922583455853511125814032301007810556669751341713882358960590148157138513279600665505170086481315954945132853932210874523918048824371102138927884568112590537645510137929195895815989942573761593298142127037421851986561822692466663124841927127593571900337305891798452293617665120432916766030641812784355834746786253941930312527947292866491855237286190719530663697528641438516595211581193231456895199952107742849665610697238698473992886058529939272142531619418018994657859457053826089774130009256762271595497713384564873208401781276578836508609793221409595224730072899074392946678165257378487568931200445963194001938816035054590584510817255341222969018092644785333196776403272306059078533015172270505680724339293806847173511775939867318614401683906342098638324099270939097095034341389804712217184128504987297110501891929171902408017624894305124453785254006243399355673992191883876488677651662592260138560292764393658366973151699598851353610470232691314924504328037807151532547694121439989851140685265677031105386431546882968426804043764002612507907051792604956790489892853979119567420347521221628233618516208027370869879347428826315773379739088956106954382335155507697719447102163179622115755626539010449811955697375697890171275552161210361547033375671868606564413882595599689401903332675547531569712245279515489628450588984719185427658164226624020806719446401006254372520150100499328901062085429162513350496226185760706202751510694873811092299618536120520011464996559960990080576325233209340917645629940584012581206783525478104609511509482737864459021343472983538882508933064024800091036269185208573164502376246079558133513775602254638274321641543195071053632779742329926439076614489715181474323207191323800095517805718852807130034720882953493188692959371764209874749568846756627856929423681298926973428432954696707891160927212986009455833716306751528422018230954406320583455986392922524179662837791176246688522918547886397330478922826064440816025622360617455552162711506182245766432523083266944341574066692670428533503814126236795967846543494223529161237457880305213804650323917362208746289187802911979087611576098243922304488855215169256505602818934984411966504236344711674264874359521691943227277913932409089948737856515873900762005834812599940685043001721446724125356091969887595612363612175780615818120926108411467904653245659827916399150874171316274477245069848908033425901190758500590836284297661099275251472049165177162552937500943395223468165788260248755680514098918573378944178660897270030875389449216752800940413855072221351024612562001494216853043380522866848705652676646139624709468552915261057088243512287087941568425845743702742827315019346682246613090281453759395076531441608371489629047041030866376381749872138300380110683993359105145840299627146883598312456745591768606252748405154154194271116698039373529383927159494178632299951545339770264458305446931277709683627429344143889637214619558142854327530258629379863042312532898376166965763888447775722274091073491581799901455354791315127193312972003397511722807858250280119766056755751240697548328455997176247364401548960212664166815632696656157308202518797381065748361030083010586023796598526867468613424231239409259619657469082177444823652072977311334636781750373366677983045774779214203482775743556167815846588326142441634146852539669459024311536307480440978755028275647886724979400490323912029305962640689861783730928159107061171634795300125480227150404344044050064558045167912743343904328626018053725595184243498512072278149152436419544352383826824228542794689752936501226411500146825308527819087822763271603741502927932717183173720282975181877421770827550663407114254255409667749020981848230198136236731795604564229868720000, 2], [1, 1]]
[[1, 1], [3460901643526357024636678186273356775097564195810881002239530834914623692355426745941266218640841767272082104486299957472656952596178316922998336011297760712057953043668452329373867060316206345724439912019107309205313983619064342726483810164168860114565103225955670410691291259793875635342213051835741737286502356169184994871894491947794112478433559236388424640976525389813481822658971205504366810573963961885206151108142211012440303021338114271868277783130131635196017016850165008417274206991918452893440031982152259870600727141208745180539249746878121680338754015659683610630326034828370347978120816481036718983015725758112463353337985414300412826486477116720128037520362189177353703044745400466670897492261143484470049056641989967890636470071661384947011366492430956135300570911611936838735325847426050294470334382345259936776109454418880012524896415964455776096047472305766461374154285277899369687701070747212072130640520781714867780842635430014571322554527985952250778270263061589767818853925407848633634680430806378888381949029511980571494769111394998832960662854210585833648751308145002874350377579248436881031311729723772477427189383419966556313998454147649985945019188914490982956581548560585971377864666837279893874145276680066652313204216627350493884880385350433087161884966018509107467198276647252338745985100113565611988324675773696640216152921945085069880882557217365857712700632674698308728742008943607360387367350050761618883362253020784000421517163748882673866034778824359857139942936738212275591567672782383864288276185174845685092082233856505358048310145947080638336027538756871384961993565069332551735734675404521416801702227610257270729472071876172216110181183816327653260884803899323840070360383442800154906614343619030836372940420770885525301222703495398928420407548793522865370348105415988945494239543539470220323270258660816898354264261827431393705215642218711600032537264755764429204901892763282192285012590496125879654696377987530190403294767353048796271740520538333564531372752251602807456604264826527059787842798675426355746455873393841527758472713104878706622460453803420441488759981619016216315190571107409335983010249159619702192556637378047360967969177532250408422009954393696548122056411683812331380177767298375359428935984696860396783865036726437791119599605238036692424094172732010039683793260070796066521367213544926671590503582722217500608400101158613686232821111055558657367508066965646794823387348588960062772475172740234372895995214049317500031251370036165278164485712717522557984339325885010885021660619173464911600777896210294823032028427966587333958020270889246521885058890925862971603827535191627324394222979433964733630328617193750973541993258146726193496511300535883951422555980031559732888707770569866259208989227309063534711719388446885655302195231374803762278817151062676240540254773639027663451596959497364298081947885296347168071367664016538071652165547161168986190576827249371075492791063871912926751411519932805152447774582515258272152394527394424078288301306078933396412271356415198301166634194691306747830356325198282491886423635899793748948901868302398590693392081765651346177957045684603536338852451118227984427580143376128191313222120083665170388702844704783705707196820817387496006838375566515356870877104827391772170259570506596898518974701509903524016429446722614636250164633234432155019701942025440453663561872591726110268392582093267346138049422824859601158761734451747455612641767373386221072725445391718812132654979556500539275120415542993229500803976319866775012312817719312285492903551884111331941978229199109850003191589332302830857100271627632062798560944723370538830822952009842259715035285802590850189168520303880457472772191788856353474956075821140057694101875575228930450073494442294964574741571503270833265012716258651740081443776013391173457914826012722531274482779179232568176195232112559160625564239755635234966482381290130659374401022836497069721244596370012359037109578653109627389585295753415419839932663219914976898424191612218055598594859999412122135040291678807784892340365868452570882591608723847575199956306737356280883942253065953416251191845364288683838884932924106857229164299563519446236723664000044355642484297573519627619467202123203358760756553978806255337388383393756375309055070558522021476100490644676465923260738246276278903887843820209120215227368837504812742631741174288319677465461395669207466908315522202890588740230136591434912471612409474895965762580177314679281705876615186152214129711295773188589823254183739287868514117106899223454720450150911414343175329950537122291460403667728842142083782844494779240504700714078275091174533228496018051800364318465299778312363107992899887684565086244691171214296298179546222878680645391561593552794224544404333193030082107833235330461377575510359038551611522236735827331376929609684690607861179582028529000752148790909260409366758892364329195350854737286958992925424500397671310869074282738897490868291311202607001550585968771478053714893536573825326877765672319478085637485524875659059234634371885358526306413948380105284557478971045825182304165225090573477237333700592054092408344074888688276990665659577342091848067453426673933805108861556232452030804356133548976601280082138013549603264653761177055431384967413116389311349550940346558410278091519791937406286756903543309278440575640572167239383611588019488352701113893592559681089336235190988350601927618008790337280374715663604024223553845699244318732133191376348878789698125997433607218502172609437683736592967469923680509155644707059581999296683356326400998473283107985846401757371699731434173791489840770979785631817696914348538987980202579423534877673858886332896748942347628466834582094988581137229936625697184635045436856632606754943045921721303726258337402006123211900789890165280293458811625335397798061792274213632912350357788426450693393394358385296696759180482936136000210948031151799017541363316290785575643162739934616103071766185477885506256883897098627842874866930277519672823919660457382052528552072996264625846114183317607609975973489493657256344798367013932778285222332750734694427286602138606341985190199276496963770209673705019759463864737813499116826668518644980748646253364707347841404092638008435580757138114965459861806761310868564936589333176363289450015843238519852820270948150942489157344457992211563774557544601450109537757903321241876714839232166573293119951738998985025945719525192426187550907820309692055855212281903021033151094415020045758055237460627130545211251702270415066919368038699525850477145474525572045334107209853452529129247040861079666403404167467581383005024901539723784527581046209796885471161297551325301149893053320414705026816420874664321305570985431378514464201421131121287166451391581206680880970071606771325772328071621110148254601939896180522963998058980022404751804038456379715907972975775564797095921678728326447841286143574936976323429009325364523849477578895325873210693562528924250158251703074561428981544473172010431144013675535199619746628042066182053711667855569205437566655594464079707249999045646005474516030106699843548603129091461948153931075770668632768741217716434498754845125594953318384862695783660266575027190592378075951056793236214652276780471962628067586879416053782508768685223183625733813102581346567097721484696853220430262560549426075999923353298283322709738654132018236850396666913575116412273927173014846345416408024570213965675435387864737564056028674753416498648601792879398854278137622643222477164356507090258496496146900283594012948444665730775281419889288508765525764751071590433621451814031301113330334941366112323390612360049562183379506070705323055192127909499825568002678685229124205595503299118108263223285437833402755201819033766269367490045639990502224741430869034185846162325092510577670950779986974222749172654481173030662825868568724936151621660806008837523016130258060922361993355790622941586569069728639602935304085329812100883872204715651231290163411109914346556261925823573900528180709617075866689269118279470104132110701188594217242425673587453894198670648684697771106116561351746913905199243555396141767130617813279509852605599737708543673115490596711333765306550659167438796361138229386277833868627753325574267288462274163538158045227413203775802412820739556773196126978626629319802762994576394658681748910915272719862308654726558965721523828071633861436964999164932089955712681972462232447114347213759683395061185854997352459681316842608225160801502671656694424318388027362164199427463748604824650236021828157724780281888255224658113530059543990860334977423484394374525523061174793836995267914330804671795478449893090500904272946380412123828583011973016861254693813197832557694917416496054046808932535045138828790826561628236268632010903696543093158669646279854062657341463826784789507017416484209086719555268502838485569535852476975557043971021023809611015181981292898178050259789648435914574176907024542175535883949918378841760448764730783012488084804392033498633244373412022820631486413180920664718832935626952852034856963356476610824792663991349902248720252222901597768368648860939439963477482509259211894704961982409007541737360566581094888083355881099324960332630828476831713704948509917764288275913546765217469383301104865046781213273597857434550122442145794791528691236532979717899561219256114934022682822667651751761629132399900746153427162117165149059045612341331789629456356479684850531575871786253098774773376798557723272602158394056575050684332649340060400666382329010353907970490181769506723963994079316546129888962123698994840059820728027028284295120085372890622979552216883727566818913826349406655809096974134418778043758374833834716378132291437465553976483563352772495790381209481859969299538975857342931836260771023250849478748138768818971861716657687486871740440181519607124593512414050898811105509162337251180249236252515122375030893926911213076256021144485025206861732777765635417971366941146274038887498691743638582393494496328381463927833482381081621731776306808549241315726193736066669927052554141193046130124143228731079830206410016420070608414331475990021027625848253728692474439160425631306196318305543074878284206232614965818078160831046945098083934830158640313137876378318280013132764204325549335397367916525466546133009104009137231035935045418210287028148069823736255262348356844414031614516022664500657761466160466535505850739163084683399928804407833944687406195697320983837508148918973121442489990472066444678410832591557487670466655841599091984658692401980701656768642742583041235553973464304366997107515787934934946645898110405376447591125993796701301634216274052562911769296279712596321239829513624646831887956375856705915833910868641992912625227383966578551532937872393890295487466070977041351550636900777102141890017426382478504357328960422053219896753222975009402581007691350416236357596528654751499047667237374414205538282488851753536411084766517151501122466693945407202354403246306707202685317209418427653755640193425138640237830747987692186712731100501480088846864267637041298604319824522107461383525926191661746918157933318947218083294286099204462736969211506182173660957979746914196382909653458107295818409492135985952260092190003844817041569287643586421603981397971773279672297758349712916284394903647942848370249818134309947225764929226070777316809801900651681477560282234105589794569348356914221218993744196685889821746330398307970847427522031467161810786890916846438230733816913216125086350435464698427988747918938350683116056918794877845598008519223141555718416379294567818158176809329479311009765457511705458228446952176513400971930040959551183436437255663248552833506030971823777193541948283279449389217943429475815843331850436751072760937094918430954280094472942602202085911694795305405649790788285520350197414539079047269090100127050258039385608318411672115514658511932036988258618592985990325166765530204757568111077971121250256486062810531758916615370754014165440320413943755779983869555835749141301587245151686654050828233529124538891184125455316952145435978839669493055646054833549824028265958007733970159971347237872663329242042080137390801589642806694822268093283436214515774773429629128552881998802740294077548909094693623076273398137878154732783456112451324600376966791235334605422333990568479661715268777804179476682788700729822815200241823897918794514041941984801426063944017511820050621171954702338377819778054677405634485276071353695525916272048381526186890664770206392575270362645166693572311612723212704652005554298442128494299821686124219970734408648075509928253444312036194312370177775788795275753982038599226877743556515061068832958156267003110882874584263727267082462406914709568261131703658079475411411148605617568478131538341997152943615577948652158250381266590356564416347506460630416450469761559489684189531211873904552345797268696443690644880482437193769749103612458700457073486166515301851654418250583218535083902139401404141472743413737363278167934427196906406580578290363496338403893690195059325221280705564043589016098929454395761704869957286332744872085778163960530779946908810280237370630941165067408235033654842689777897611961190669923130578052037283518782861809526521223009662248707877820151696859011873394500273025840293305112811953161751647320821474394386424131826369623726948102283248134868743595680782718095436248985570360987970793582203285856432819404052144147052266099418000386795171541864360349538993883453969030023403338215923735307021404036131399158659956877801411413120310353108287436018716183091894494462227240873053160521496854411597518669423044881542754304857320124312554167385609642634978155762151107696529360002760426124370308558317677174839130751068445354965282324054339755246106594142200251779614071465490648839182397959234577229436819607964527749795104602916573604415812393111762782389434284122134665448703221571656002806616244515413660686660176061113463149161308475756506177579576847954120822232157623530258149320345605231020446342286855012922895571222993372720000, 3], [3460901643526357024636678186273356775097564195810881002239530834914623692355426745941266218640841767272082104486299957472656952596178316922998336011297760712057953043668452329373867060316206345724439912019107309205313983619064342726483810164168860114565103225955670410691291259793875635342213051835741737286502356169184994871894491947794112478433559236388424640976525389813481822658971205504366810573963961885206151108142211012440303021338114271868277783130131635196017016850165008417274206991918452893440031982152259870600727141208745180539249746878121680338754015659683610630326034828370347978120816481036718983015725758112463353337985414300412826486477116720128037520362189177353703044745400466670897492261143484470049056641989967890636470071661384947011366492430956135300570911611936838735325847426050294470334382345259936776109454418880012524896415964455776096047472305766461374154285277899369687701070747212072130640520781714867780842635430014571322554527985952250778270263061589767818853925407848633634680430806378888381949029511980571494769111394998832960662854210585833648751308145002874350377579248436881031311729723772477427189383419966556313998454147649985945019188914490982956581548560585971377864666837279893874145276680066652313204216627350493884880385350433087161884966018509107467198276647252338745985100113565611988324675773696640216152921945085069880882557217365857712700632674698308728742008943607360387367350050761618883362253020784000421517163748882673866034778824359857139942936738212275591567672782383864288276185174845685092082233856505358048310145947080638336027538756871384961993565069332551735734675404521416801702227610257270729472071876172216110181183816327653260884803899323840070360383442800154906614343619030836372940420770885525301222703495398928420407548793522865370348105415988945494239543539470220323270258660816898354264261827431393705215642218711600032537264755764429204901892763282192285012590496125879654696377987530190403294767353048796271740520538333564531372752251602807456604264826527059787842798675426355746455873393841527758472713104878706622460453803420441488759981619016216315190571107409335983010249159619702192556637378047360967969177532250408422009954393696548122056411683812331380177767298375359428935984696860396783865036726437791119599605238036692424094172732010039683793260070796066521367213544926671590503582722217500608400101158613686232821111055558657367508066965646794823387348588960062772475172740234372895995214049317500031251370036165278164485712717522557984339325885010885021660619173464911600777896210294823032028427966587333958020270889246521885058890925862971603827535191627324394222979433964733630328617193750973541993258146726193496511300535883951422555980031559732888707770569866259208989227309063534711719388446885655302195231374803762278817151062676240540254773639027663451596959497364298081947885296347168071367664016538071652165547161168986190576827249371075492791063871912926751411519932805152447774582515258272152394527394424078288301306078933396412271356415198301166634194691306747830356325198282491886423635899793748948901868302398590693392081765651346177957045684603536338852451118227984427580143376128191313222120083665170388702844704783705707196820817387496006838375566515356870877104827391772170259570506596898518974701509903524016429446722614636250164633234432155019701942025440453663561872591726110268392582093267346138049422824859601158761734451747455612641767373386221072725445391718812132654979556500539275120415542993229500803976319866775012312817719312285492903551884111331941978229199109850003191589332302830857100271627632062798560944723370538830822952009842259715035285802590850189168520303880457472772191788856353474956075821140057694101875575228930450073494442294964574741571503270833265012716258651740081443776013391173457914826012722531274482779179232568176195232112559160625564239755635234966482381290130659374401022836497069721244596370012359037109578653109627389585295753415419839932663219914976898424191612218055598594859999412122135040291678807784892340365868452570882591608723847575199956306737356280883942253065953416251191845364288683838884932924106857229164299563519446236723664000044355642484297573519627619467202123203358760756553978806255337388383393756375309055070558522021476100490644676465923260738246276278903887843820209120215227368837504812742631741174288319677465461395669207466908315522202890588740230136591434912471612409474895965762580177314679281705876615186152214129711295773188589823254183739287868514117106899223454720450150911414343175329950537122291460403667728842142083782844494779240504700714078275091174533228496018051800364318465299778312363107992899887684565086244691171214296298179546222878680645391561593552794224544404333193030082107833235330461377575510359038551611522236735827331376929609684690607861179582028529000752148790909260409366758892364329195350854737286958992925424500397671310869074282738897490868291311202607001550585968771478053714893536573825326877765672319478085637485524875659059234634371885358526306413948380105284557478971045825182304165225090573477237333700592054092408344074888688276990665659577342091848067453426673933805108861556232452030804356133548976601280082138013549603264653761177055431384967413116389311349550940346558410278091519791937406286756903543309278440575640572167239383611588019488352701113893592559681089336235190988350601927618008790337280374715663604024223553845699244318732133191376348878789698125997433607218502172609437683736592967469923680509155644707059581999296683356326400998473283107985846401757371699731434173791489840770979785631817696914348538987980202579423534877673858886332896748942347628466834582094988581137229936625697184635045436856632606754943045921721303726258337402006123211900789890165280293458811625335397798061792274213632912350357788426450693393394358385296696759180482936136000210948031151799017541363316290785575643162739934616103071766185477885506256883897098627842874866930277519672823919660457382052528552072996264625846114183317607609975973489493657256344798367013932778285222332750734694427286602138606341985190199276496963770209673705019759463864737813499116826668518644980748646253364707347841404092638008435580757138114965459861806761310868564936589333176363289450015843238519852820270948150942489157344457992211563774557544601450109537757903321241876714839232166573293119951738998985025945719525192426187550907820309692055855212281903021033151094415020045758055237460627130545211251702270415066919368038699525850477145474525572045334107209853452529129247040861079666403404167467581383005024901539723784527581046209796885471161297551325301149893053320414705026816420874664321305570985431378514464201421131121287166451391581206680880970071606771325772328071621110148254601939896180522963998058980022404751804038456379715907972975775564797095921678728326447841286143574936976323429009325364523849477578895325873210693562528924250158251703074561428981544473172010431144013675535199619746628042066182053711667855569205437566655594464079707249999045646005474516030106699843548603129091461948153931075770668632768741217716434498754845125594953318384862695783660266575027190592378075951056793236214652276780471962628067586879416053782508768685223183625733813102581346567097721484696853220430262560549426075999923353298283322709738654132018236850396666913575116412273927173014846345416408024570213965675435387864737564056028674753416498648601792879398854278137622643222477164356507090258496496146900283594012948444665730775281419889288508765525764751071590433621451814031301113330334941366112323390612360049562183379506070705323055192127909499825568002678685229124205595503299118108263223285437833402755201819033766269367490045639990502224741430869034185846162325092510577670950779986974222749172654481173030662825868568724936151621660806008837523016130258060922361993355790622941586569069728639602935304085329812100883872204715651231290163411109914346556261925823573900528180709617075866689269118279470104132110701188594217242425673587453894198670648684697771106116561351746913905199243555396141767130617813279509852605599737708543673115490596711333765306550659167438796361138229386277833868627753325574267288462274163538158045227413203775802412820739556773196126978626629319802762994576394658681748910915272719862308654726558965721523828071633861436964999164932089955712681972462232447114347213759683395061185854997352459681316842608225160801502671656694424318388027362164199427463748604824650236021828157724780281888255224658113530059543990860334977423484394374525523061174793836995267914330804671795478449893090500904272946380412123828583011973016861254693813197832557694917416496054046808932535045138828790826561628236268632010903696543093158669646279854062657341463826784789507017416484209086719555268502838485569535852476975557043971021023809611015181981292898178050259789648435914574176907024542175535883949918378841760448764730783012488084804392033498633244373412022820631486413180920664718832935626952852034856963356476610824792663991349902248720252222901597768368648860939439963477482509259211894704961982409007541737360566581094888083355881099324960332630828476831713704948509917764288275913546765217469383301104865046781213273597857434550122442145794791528691236532979717899561219256114934022682822667651751761629132399900746153427162117165149059045612341331789629456356479684850531575871786253098774773376798557723272602158394056575050684332649340060400666382329010353907970490181769506723963994079316546129888962123698994840059820728027028284295120085372890622979552216883727566818913826349406655809096974134418778043758374833834716378132291437465553976483563352772495790381209481859969299538975857342931836260771023250849478748138768818971861716657687486871740440181519607124593512414050898811105509162337251180249236252515122375030893926911213076256021144485025206861732777765635417971366941146274038887498691743638582393494496328381463927833482381081621731776306808549241315726193736066669927052554141193046130124143228731079830206410016420070608414331475990021027625848253728692474439160425631306196318305543074878284206232614965818078160831046945098083934830158640313137876378318280013132764204325549335397367916525466546133009104009137231035935045418210287028148069823736255262348356844414031614516022664500657761466160466535505850739163084683399928804407833944687406195697320983837508148918973121442489990472066444678410832591557487670466655841599091984658692401980701656768642742583041235553973464304366997107515787934934946645898110405376447591125993796701301634216274052562911769296279712596321239829513624646831887956375856705915833910868641992912625227383966578551532937872393890295487466070977041351550636900777102141890017426382478504357328960422053219896753222975009402581007691350416236357596528654751499047667237374414205538282488851753536411084766517151501122466693945407202354403246306707202685317209418427653755640193425138640237830747987692186712731100501480088846864267637041298604319824522107461383525926191661746918157933318947218083294286099204462736969211506182173660957979746914196382909653458107295818409492135985952260092190003844817041569287643586421603981397971773279672297758349712916284394903647942848370249818134309947225764929226070777316809801900651681477560282234105589794569348356914221218993744196685889821746330398307970847427522031467161810786890916846438230733816913216125086350435464698427988747918938350683116056918794877845598008519223141555718416379294567818158176809329479311009765457511705458228446952176513400971930040959551183436437255663248552833506030971823777193541948283279449389217943429475815843331850436751072760937094918430954280094472942602202085911694795305405649790788285520350197414539079047269090100127050258039385608318411672115514658511932036988258618592985990325166765530204757568111077971121250256486062810531758916615370754014165440320413943755779983869555835749141301587245151686654050828233529124538891184125455316952145435978839669493055646054833549824028265958007733970159971347237872663329242042080137390801589642806694822268093283436214515774773429629128552881998802740294077548909094693623076273398137878154732783456112451324600376966791235334605422333990568479661715268777804179476682788700729822815200241823897918794514041941984801426063944017511820050621171954702338377819778054677405634485276071353695525916272048381526186890664770206392575270362645166693572311612723212704652005554298442128494299821686124219970734408648075509928253444312036194312370177775788795275753982038599226877743556515061068832958156267003110882874584263727267082462406914709568261131703658079475411411148605617568478131538341997152943615577948652158250381266590356564416347506460630416450469761559489684189531211873904552345797268696443690644880482437193769749103612458700457073486166515301851654418250583218535083902139401404141472743413737363278167934427196906406580578290363496338403893690195059325221280705564043589016098929454395761704869957286332744872085778163960530779946908810280237370630941165067408235033654842689777897611961190669923130578052037283518782861809526521223009662248707877820151696859011873394500273025840293305112811953161751647320821474394386424131826369623726948102283248134868743595680782718095436248985570360987970793582203285856432819404052144147052266099418000386795171541864360349538993883453969030023403338215923735307021404036131399158659956877801411413120310353108287436018716183091894494462227240873053160521496854411597518669423044881542754304857320124312554167385609642634978155762151107696529360002760426124370308558317677174839130751068445354965282324054339755246106594142200251779614071465490648839182397959234577229436819607964527749795104602916573604415812393111762782389434284122134665448703221571656002806616244515413660686660176061113463149161308475756506177579576847954120822232157623530258149320345605231020446342286855012922895571222993372720000, 3], [1, 1]]