Rubyで階乗
なんとなく、Rubyで階乗の計算をしてみた。
その1 再帰
階乗の計算は再帰の例題としてよく出てくるので、まずはそれで。
$ time ruby -e 'def fact(n) n==1 ? n : fact(n-1)*n; end; fact(10000)' -e::n `fact': stack level too deep (SystemStackError) from -e:1:in `fact' from -e: real 0m0.080s user 0m0.012s sys 0m0.008s
さすがに10000のスタックは無理だったか・・・
じゃ1000で
honda@endor:/ruby$ time ruby -e 'def fact(n) n==1 ? n : fact(n-1)*n; end; fact(1000)' real 0m0.026s user 0m0.016s sys 0m0.004s
26ms也。
その２ forループ
honda@endor:/ruby$ time ruby -e 'a=1;for i in 2..10000 do a*=i end' real 0m0.649s user 0m0.560s sys 0m0.028s
10000の階乗もちゃんと計算できます。
次は1000の階乗。
$ time ruby -e 'a=1;for i in 2..1000 do a*=i end' real 0m0.017s user 0m0.012s sys 0m0.000s
その３ inject
injectメソッドを使って、次のように書くこともできる。
honda@endor:/ruby$ time ruby -e '(1..10000).to_a.inject{|r,a| r*a}'
real 0m0.679s
user 0m0.572s
sys 0m0.016s
<||
>||
honda@endor:/ruby$ time ruby -e '(1..1000).to_a.inject{|r,a| r*a}'
real 0m0.018s
user 0m0.012s
sys 0m0.000s時間はforループの場合とほとんど変わらない。
最後に
ちなみに、計算結果を表示してみると、こうなる。
$ time ruby -e 'r=(1..1000).to_a.inject{|r,a| r*a}.to_s; for i in 0..(r.length/80).ceil do puts r[i*80, 80] end'
40238726007709377354370243392300398571937486421071463254379991042993851239862902
05920442084869694048004799886101971960586316668729948085589013238296699445909974
24504087073759918823627727188732519779505950995276120874975462497043601418278094
64649629105639388743788648733711918104582578364784997701247663288983595573543251
31853239584630755574091142624174743493475534286465766116677973966688202912073791
43853719588249808126867838374559731746136085379534524221586593201928090878297308
43139284440328123155861103697680135730421616874760967587134831202547858932076716
91324484262361314125087802080002616831510273418279777047846358681701643650241536
91398281264810213092761244896359928705114964975419909342221566832572080821333186
11681155361583654698404670897560290095053761647584772842188967964624494516076535
34081989013854424879849599533191017233555566021394503997362807501378376153071277
61926849034352625200015888535147331611702103968175921510907788019393178114194545
25722386554146106289218796022383897147608850627686296714667469756291123408243920
81601537808898939645182632436716167621791689097799119037540312746222899880051954
44414282012187361745992642956581746628302955570299024324153181617210465832036786
90611726015878352075151628422554026517048330422614397428693306169089796848259012
54583271682264580665267699586526822728070757813918581788896522081643483448259932
66043367660176999612831860788386150279465955131156552036093988180612138558600301
43569452722420634463179746059468257310379008402443243846565724501440282188525247
09351906209290231364932734975655139587205596542287497740114133469627154228458623
77387538230483865688976461927383814900140767310446640259899490222221765904339901
88601856652648506179970235619389701786004081188972991831102117122984590164192106
88843871218556461249607987229085192968193723886426148396573822911231250241866493
53143970137428531926649875337218940694281434118520158014123344828015051399694290
15348307764456909907315243327828826986460278986432113908350621709500259738986355
42771967428222487575867657523442202075736305694988250879689281627538488633969099
59826280956121450994871701244516461260379029309120889086942028510640182154399457
15680594187274899809425474217358240106367740459574178516082923013535808184009699
63725242305608559037006242712434169090041536901059339838357779394109700277534720
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000
real 0m0.054s
user 0m0.012s
sys 0m0.012s$ time ruby -e 'r=(1..10000).to_a.inject{|r,a| r*a}.to_s; for i in 0..(r.length/80).ceil do puts r[i*80, 80] end'
28462596809170545189064132121198688901480514017027992307941799942744113400037644
43772990786757784775815884062142317528830042339940153518739052421161382716174819
82419982759241828925978789812425312059465996259867065601615720360323979263287367
17055741975962099479720346153698119897092611277500484198845410475544642442136573
30307670362882580354896746111709736957860367019107151273058728104115864056128116
53853259684258259955846881464304255898366493170592517172042765974074461334000541
94052462303436869154059404066227828248371512038322178644627183822923899638992827
22187970245938769380309462733229257055545969002787528224254434802112755901916942
54290289169072190970836905398737474524833728995218023632827412170402680867692104
51555840567172555372015852132829034279989818449313610640381489304499621599999359
67089298019033699848440466541923625842494716317896119204123310826865107135451684
55409360330096072103469443779823494307806260694223026818852275920570292308431261
88497606560742586279448827155956831533440534425446648416894580425709461673613187
60523498228632645292152942347987060334429073715868849917893258069148316885425195
60061723726363239744207869246429560123062887201226529529640915083013366309827338
06353972901506581822574295475894399765113865541208125788683704239208764484761569
00126488927159070630640966162803878404448519164379080718611237062213341541506599
18438759610239267132765469861636577066264386380298480519527695361952592409309086
14471907390768585755934786981720734372093104825475628567777694081564074962275254
99338411280928963751699021987049240561753178634693979802461973707904186832993101
65541507423083931768783669236948490259996077296842939774275362631198254166815318
91763234839190821000147178932184227805135181734921901146246875769835373441456013
12261522139117875968836736408720793700299203827919803870237207803914031236899760
81528403060511167094847222248703891999934420713958369830639622320791156240442508
08919914319837120445598344047556759489212101498152454543594285414390843564419984
22485547853216362403009844285533182925315420655123707970581639346029624769701038
87422064415366267337154287007891227493406843364428898471008406416000936239352612
48037975293343928764398316390312776450722479267851700826669598389526150759007349
21519759265919270887320259406638211880198885474826604834225645770574397312225970
06719360617635135795298217942907977053272832675014880244435286816450261656628375
46519006171873442260438919298506071515390031106684727360135816706437861756757439
18437647965813610059963868955233464878174614324357322486432679848198145843270303
58955084205347884933645824825920332880890257823882332657702052489709370472102142
48413342465268206806732314214483854074182139621846870108359582946965235632764870
47571835161687923506836627174371191572336114307012112076760869785155972184648598
59186436417168508996255168209107935702311185181747750108046225855213147648974906
60752877082897667514951009682329689732000622392888056658036140311285465929084078
03397490066495320587316494809388381619865885082738246803489786475711667989042356
80183035041338757319726308979094357106877973016339180878684749436335338933735869
06405848417828065196275826434429258058422212947649402948622670761832988229004072
39040373316820741741325165668844307933944701920890562078838758534251282095735930
70181977083401638176382785625395168254266446149410447115795332623728154687940804
23718587423026200264221822694188626212107297776657401018376182280136857586442185
86301153984371229910701009406192941322320277319395946700671369537709789777811828
82424429208648161341795620174718316096876610431404979581982364458073682094040222
11181530051433387076607063149616107771117448059552764348333385744040212757031851
52729837743592187855855279559102866445791736200722185814330997729477892372071794
28577562713009239823979219575811972647426428782666823539156878572716201461922442
66266708400765665625807109474398740110772811669918806268726626565583345665007890
30905065607463307802715853081769122377281351058452732659162621964762057143488021
56308152590053437211410003030392428664572073284734817120341681863289688650482873
67933398443971236735084527340196309427697652684170174990756947982757825835229994
31563332210743913155012445900532470268031291239229797903041758782339862237353505
46426469135025039510092392865851086820880706627347332003549957203970864880660409
29854607006339409885836349865466136727880748764700702458790118046518296111277090
60901615202211146154315831766995706097461808535939040006789287854882785093863735
37039040494126846189912728715626550012708330399502578799317054318827526592258149
48950746639976007316927310831735883056612614782997663188070063044632429112260691
93127888156622159152327045769586751282199093894268660196390448971891859747292531
03224802105438410443258284728305842978041624051081103269140019005687843963415026
96521048920272140232160234898588827371428695339681755106287470907473718188014223
48724849855819843909465170836436899430618965024328835327966719018452762055108570
76262042445096233232047447078311904344993514426255017017710173795511247461594717
31862701565571266295855125077711738338208419705893367323724453280456537178514960
30880258028406784780941464183865922665280686797884325066053794304625028710510492
93472674712674998926346273581671469350604951103407554046581703934810467584856259
67767959768299409334026387269378365320912287718077451152622642548771835461108886
36084327280622777664309728387905672861803604863346489337143941525025945965250152
09595361579771355957949657297756509026944280884797612766648470036196489060437619
34694270444070215317943583831051404915462608728486678750541674146731648999356381
31286693142761686353730563458662695789456827506581023595081488877895507393936534
19373657008483185044756822154440675992031380770735399780363392673345495492966687
59922530893898086430606532961793164029612492673080638031873912596151131890359351
26648081856836677028653774239074658239091095551717977058079778928975249023073780
17531426803639142447202577288917849500781178893366297504368042146681978242729806
97579391742229456683185815676816288797870624531246651727622758295493421483658868
91929958740209569600024356030528982986638689207699283403054971026651432230612523
19151318438769038237062053992069339437168804664297114767435644863750268476981488
53105354063328845062012173302630676481322931561043551941761050712449024873277273
11209194586513749319096516249769165755381219856643220797866630039893866023860735
78581143947158728008933741650337929658326184360731333275260236051155242272284472
51463863269369763762510196714380125691227784428426999440829152215904694437282498
65808520518657629299277550883312867263841871327778087444664387535264473356244113
94476287809746506839529821081749679588364522733446948737934717907100649782364660
16680572034297929207446822322848665839522211446859572858403863377278030227591530
49786587391951365024627419589908837438733159428737202977062020712021303857217593
32111624133304227737424163535535879770653096476858860773014327782903288947958184
04378858567772932094476778669357537460048142376741194182671636870481056911156215
61435751629052735122435008060465366891745819654948260861226075029306276147881326
89552807361490225258196828150510333181321296596649581590304212387756459909732967
28066683849166257949747922905361845563741034791430771561168650484292490281102992
52967873529876782926904078877848026247922275073594840581743908625187794689004594
20601686051427722444862724699111462001498806627235388378093806285443847630532350
70132028029488392008132135446450056134987017834271106158177289819290656498688081
04556223370306725425127727733028349843359577257595622470370779338714659303308862
96994403183326657975146765027173462988837773978482187007180267412659971587280354
40478432478674907127921672898523588486943546692255101337606377915164597254257116
96847733995115899834908188828126398440050554621006698879261455821456531969690982
72539345157604086134762587781658672944107753588241623157790825380547469335405824
69717674324523451498483027170396543887737637358191736582454273347490424262946011
29988191656371384711184915691505476814041174980145426571239420442544102807580600
13881986506137592885390389226443229479902864828400995986759635809991126953676015
27173086852756572147583507122298296529564917835071750835741362282545055620270969
41747679925922977488862741131458767614753145689532809311705269648641018740767329
69866492364373825654750228164719268155598831966298483077766668406223143158843849
10519058281816740764463033300119710293036455866594651869074475250837841987622990
41591179368279976065418608872162665488649234439103092325691063377596973905178112
27646684867917360494043937033393519006093872683972992464784837272747709774666935
99784857120156789000241947269220974984127323147401549980920381459821416481176357
14780155423159966783853485448640693641055691353133523118405358134894093819182189
86948253839609899428220275993396352062177053435720733962505742167694651016084956
01439303244304271576099527308684609204422226103154229984444802110098161333824827
37521899873820531516492713449810595015997480057159191220215448774875010347324619
06339413030308923994119850062259021841644099881732143244221085542486208962502606
04398180189026317781146617454999771440665232863846363847001655618153861098188111
18173419130550502486034585675558563751172977429932907494423657966833270091836733
89773479017592488856603799527715405690830173117238941403261596122929122251910959
48743805673381278538616491842786938417556898047100859868372033615175158097022566
27520016095619222992540175987852203854591377178397638981119848580329104875166692
11951045148966777615982494687274206634375932078526189226872855276713248832677941
52912839165407968344190239094803676688707838011367042753971396201424784935196735
30144440403782352667443755674088302522574527380620998045123318810272901204299798
90054231262179681352377580411625114591759932791341765072928267622368972919605282
89675223521425234217247841869317397460411877634604625637135309801590617736758715
33680395855905482736187611215138467343288432509004564535818668190510873179134621
57303395405809871720138443770992795327976755310993813658404035567957318941419765
11436325526270639743146526348120032720096755667701926242585057770617893798231096
98678844854665952732706167030891827720643255191939367359134603775708319318084592
95651588752445976017294557205055950859291755065101156650755216351423181535481768
84196032085050871496270494017684183980582594038182593986461260275954247433376226
25628715391606902509898507079866062173220016359393861147539456140663567571852661
70314714535167530074992138652077685238248846006237358966080549516524064805472958
69918694358811197833680141488078321213457152360124065922208508912956907835370576
73467166786378090881128345039578481221210111725071838335908388618757466120131729
82171310729447376562651723106948844254983695141473838924777423209402078312008072
35326288053906266018186050424938788677872495503255424284226596271050692646071767
46750233780567189345011073737703411934611337403386536467513673366139473155021145
71046711614452533248501979010834316419899984140450449011301637595206757155675094
85243580269104077637210998671624254795385312852889930956570729218673523216666097
87498963536261052982147256948279999622082577584098845848425039118944760872968518
49839763679182422665711671665801579145008116571922002337597653174959223978849828
14705506190689275625210462185661305800255607974609726715033327032310025274640428
75555654688376583880254322740350743168427862063769705479172648437817444636152057
09332285872843156907562555693055588188226035900067393399525043798874709350792761
81116276309771257983975996526612120317495882059435754883862282508401408885720583
99240097121921254807409775297427877591256602644348271364723184912518086627870862
61166999896348124058036847945873648201246536632288890116365722708877577361520034
50102268890189101673572058661410011723664762657835396364297819011647056170279631
92233229422873930923333074825893762619899759653008413538324112589963962944512908
28020232254989366275064995308389256322467946959606690469066862926450062197401217
82899872979704859021775060092893328957272392019589994471945147360850770400725717
43931814846190940626954528503052634100056502222615230936488288712204645426770057
71489943351471625042523651737102660686472534581201866832739536825474565365535975
46685788700056988360286686450740256993087483441094086086303707908295240576731684
94185581048247530475892339280157130282410623499994593239052140985655956566134600
33961505151647588527422147325179995489779928495227460298556667008118712008561550
16457400484170210303038996339253337466556817824410737409336919294104632307731994
75982630738349960077037241044628541464870411627389564983455516216568511455138382
20470054839966717062464675661012913820489091211172293862442531589130669874620455
87244806052829378148302622164542280421757760762365459828223070815503469404938317
75505330509469899947611941923128072180721696437843331360676067696518713839433877
24854936890618457005720436966664650807344958144959663062466986798328725863000642
15220210171813917325275173672262621454945468506006334692713838311715849753092643
25248696022005909980266376538622546326516841496330636954808655110125675771789061
66947583440434862184853695916021720304561834975241620399264413316518847686068306
42004858557924473340290142588876403712518642229016333691585063273727199596362912
78334478621888787100953375355105468898023637826371492691328956433944089947012145
21345721177156575914517348951950168006213539271754198438761635434798069208866662
27099512371706241924914282576453125769939735341673046864585181979668232015693792
68492699998399241357194149688227370402282080517180800340048061526179201397894518
62952905584407037383005335524211539033851858293667791906101163062336731444192028
93857201855569596330833615450290424822309297087124788002017383072060482680156675
39759378993179351579995892956215630733841629459990027673083282771659506421796652
31904392505432267537318117553154767807394703389311851072977243183789726749574557
78183345495942317353558291046967315391275975687281861691161083156337232639968881
49054394326119718227499679117662855340186019831580962998179110720880499229201606
20590672712735994618716349457749958053379471871054564525793960242102591364155283
98395201773012712514892051061708228008339985665786646920737114269682301770416324
82947940955869469908937916519100630518535210234518979812761914306186436270308197
71249927510567329094812020577471006877033797089342292071839037441675034938188363
42229284946790660285674293251642569044363473087656797056595677285291081242733154
40658019980271157912625417279745286257486592193329380591523952473551888711986039
13196542875762901905039640835602462775343144091556421817294599415960619796226332
42715863425977947348682074802021538734729707999753332987785531053820162169791880
38075300633435076614773713593936265190522224252814108474704529568864775791350216
09220403484491499507787431071896557254926512826934895157950754861723413946103651
76616750329948642244039659511882264981315925080185126386635308622223491094629059
31782940819564048470245653830543205650692442267186325530764076187208678039171135
63635012695250912910204960428232326289965027589510528443681774157309418748944280
65427561430975828127698124936993313028946670560414084308942231140912722238148470
36434101963041363073677106003815959082974641011442135832104257435835022073717321
97450890355731873504458272387707282714061629979196293572241044771550516525358675
44109395079218369015261138440382680054150924346511711436477899444553993653667727
58956571398750554299082458560951003693466310067371470802992765693343550092718985
40501099174749799915543920319089619676154446860481754006956894714639282453838070
10444181045506171305160584355817521032338465829201071030061124283407458607006060
19483055136486702102036470847080742270437189370696568879561792871304522451684202
74020219664156052803350612935587390793935244040925842483806071774446099640352218
91022961909032569042381374492494906892314330884224399631396391545854065286326468
80758114874837140828417645522638631352026489401626249480238856823159910295262033
71264492799019382111345184463875445163912393779741905766499117642376377222828023
18465738050121277809680315691477264910257503508758792248110223544524410872448565
70075518713214659209354850455282917074959677540445077949483637175606232692575741
28131102419103733380804343253108846948315557294022653949729138175813386194570577
99561808755951413644907613109617155928376585840036489374076822257523935988731081
68966768828740383719282769043151410699767830381908569071309193134084601951114748
27663507246765349220400586266776329355166319396224989799127080044659822648991252
26813124300528104995058595676527123591494442612554437618645029202881358582871789
57722411638081516183160312972879698748013982862164562919615309635833731361972477
33323530254665711969026112373806290302429042757945490300226608474465131617416919
16851746464945459696005330885252792083472495235473110674109099223541055506299687
64215395124935598631134666172511689078563332893556915044948518911348830187636510
06385025659164330219285655962639143828950683248387271656165601115315170552229557
65944972454788815532316417453267167978861141165355597588331979638070962998880767
30361694031773644814042786778425123244997469342134821717959519069820460299717200
11748573038897192055974147424530111358697662566077709702256332617011084637847955
55258504578058879440756064974127974530918418405207558526462208821483646754652237
60921078753919045468485234975998604494332282807312067992240247750751410589077462
73343190912554513522253292759138420473846030561631542365529353122783897594465157
87337343463172280001031380425481404022090580405056003860937403435068863081434683
84890070893856505002756905967806940469843518453513414103161513368304371478664292
53897171659786290107284007589397003883177426481637251132773699268277094653425835
96111881955092462062153978121197244762623771534452048069819082524943963962251113
83117742897853582559083249048049751604710425756975344255151577981560037084723060
34847539775136883904043160174862488713393118185230294254256762024856883939708367
48788453789172574145155917919035398535077200900594979352939459631213445503368260
69005982871772353337522194191554730374206234326289296839701505889219111204924986
47920534108723491154309871821600557622090757323046261065977449476583463130255986
36315029959672352476943975462530206788193304372284800209305354155640664838569378
14460313869756345920023346260699595551348475414789118083032981642158745292295267
89379256477520290526753493566737442931826733745716424654077482679010467787590854
08130531447176455869894169668940436489952465247443988349583871206296485413357553
81341950049874381336906270397387458660429687159582071576659982660731700562446554
17630245013491595672889426197461444969086716558597827292287027237748350973629010
19130417812735773037781804081589136005207315806941034305003184349342360269244733
06001386111978177447266960892832105254311649603342010203260386367253288964833340
58622048436165753620014684054766496664735669795729533948091382637033242209308393
66954980688240491622063147911494642042500022450413425558561937442905257252436320
05448744152430730521507049102043407657247686509575117412541372953164452176557723
53486018215668333525205328300001083440087622668438170232356056451582569541773591
97813649975559601912567744942717986360045847405209290089397315276024304951653864
43138814787697754147875743261015987970975885562580676619797309847246076948482112
79484279765366070550516391044150225544203297212920330093533566872945959123279658
86376486894188433640548494009574965791657687213927330153555097865114767947399690
62318487837751546261382365166595633720934570820830184048279700572807143292572757
74362295870473616416097318172415942042703660664040897402455215307252273886372418
59646455223673260411164598464020010216920823315155388821071527191267876531795071
90820452510044782129131854405481449415186711420710369389112912501275085346633771
77493760165434546963900427111298292550968304206657253642794722000208353138837087
81649957189717629338794854271276882652003766325924561614868744897471519366219275
66585246211445740701067538042756418444083480520383826505260169858406008478842242
18878569278977518104428054744272294551674203356864606099779731249504333214252050
53675790499520783597650415379001132579536040655172654879022173595444151139429231
64895066317781303905746208244917192131186412963370466140645690017894235673877552
31309527859127745332418554424844844936642107313488191806401892223173021566458134
73186449997905781662091469870718039388885781280740226363602294114354869871402143
57205594773089280865367892020193510260536156792448327674947611785831607186571031
08422005602595451151913913091195444478443610327418761023388433916875892334237908
59841968266525610628751237572318491474951945985728897934981791761822652480408237
12810979077263886428606791708228857585270347083971456161992624784479469279499684
59456323827022973641735034307831941156982478200132908512028784748058601889600459
01745974055630732714487679085288867978809970695240681006625611440014983413580889
73724684406494885707416768791641322420537365406733018639249791091547478595916386
55975070905811759248995022147992509456355825143158144640601342834904227983579396
59258985200763845646681640732681928346007767285876284900068874564639274964415904
03403367233781449159703294178729415506105412951540015939385166392932567742955754
94800466582735796539909402335436446493768272725418736275475329768081903253361410
86433084237771738995221536763095302045902438694632702895293994483013577589081214
88455849381987450592091406720952246909626307694175334098369885936370031497372897
79963600186265001749292900879311899978229637123066422979961635825726001122889836
47651418045975770042120833949364659647336464289044499325396227091907373705772051
32281595786322759191278605429786295318861555980472816071086413280358540016005557
56868557917859778991979026565926212830072253514015259735693007290153922111168685
04740402172174442051738000251361000494534119324331668344243125963098812396962202
35885839558783168519483312665357735324437993568321526917704224903457453485891381
25826813669089294768090526355606381196613060639369384118177135459298843172329122
36262458868394202889981693561169865429884776513118227662526739978808816010470651
54233501567135374481708623431466253119029104015226292710409928507241884332900727
77947541116375521765635893163266360493812184018375128188847711689754794837676640
84842753623074019542183217985496260666590347925816342392670947839907062923166535
03728501975132481380383707089463892547088703908572358100613062864666471000610435
21157789266134322146553114118825969429262845221090266884149757633415549211355812
54616558078273470115814006008345762133130389987843270653719956709570847385786092
64918885837873923916555426357730129224364160406255173689233563656885436585164620
78218757417243645258141434876327613417527073767549222762877822647651543153415857
13773522730335403376364204258034257264749686217823666951353410677378421131371131
98737322289180527506281227771641249441240120712595431999174657474589258261371282
55555350804041439445572959945546356084872513394629363589408320989648016195831304
29720964794128539388996265368928263807677168759588502216464582430940165009688797
36615773356031683671038689522827094150954522274400273549925367021471599405654481
38421863801287999008209335763207363694059914242637182940006137419005795130962985
45330748197802568301089672873802234820488862973130369689882640657904781562389778
48536502569106423179573602533090876327178491118974843224686808634038396417612760
57886465744722848249326874430625512205069551684646694771836819114328735448158363
50548146411099960143390595799766290646881295025039150923633011076070632863317393
37814969338024758003505278978275575092860403942050634293932706463616103182287924
81526793068627492372756318522256542660085568494977202859091509304954259674736483
31437236349555448901598668408362176913559656039519670425368863482369587129462524
75903177681318497758827657674048255813650210364958550570325921995767533426422378
37235860585094035839771034766706447886408311096503025652156074640196527169997323
73465237173456595514559493098166644006211599349133180135150528651842178828026343
32593475585076116869770912558005618568371054085608124951940314806461871940257766
32852670196983875675615246967590281068648968692933159543520976875271372016161609
31174250199709289684940034696242325688410665113304377412256176258658941236728171
14552642389451263171783479027692117145288735295501933675921890800604863373778672
81806102547825704367884495035189257874998366947859086129755430841226770609543476
12133717433156783790162012337237023338316414706428592185977610158232721997915062
87186818675098166553774501302088033390435363977026336380909852649453262814655806
55465048234864294953906132574004969128883405182229336444766838550379679758096199
83575807027759535968788226194659612223044549275600274955168583542582295336042834
42631847806882539545074669187789776540603843251284381281131685620460861728940822
96586261744207669202974279300881295198546787135486232366104132165812792671515459
61594352593456757445992307889205519540082316409719591250025455237503106735639748
83554248044968138303067185193149133578920212360530819995202058450342349993215096
26349778124566583046805818245635248146258493319261954068848184464452484294860630
16169476663242625231476322371109695369483824482316410396224507675405614287468267
83572370489560699065279268845584451204665485337853402664664504233963848825771987
49536113004942155937355452119261867214782654168856040949282900566168838076376566
90510740892510549165222968878676968631652514917701499900066637344546120262780701
92569870622554092894519471877800430613002182828742586704874848082694857344477824
40787341027108248702695238308049109604820139012940246312448001593366702126583176
77879752965963472576894326540435889267293950687860830626266263287392087327302547
91009993211338897780781433672879144876837368646774852877773740354747287164421776
78207129645062708809786379281440711925051411480049070556080972292997924414710628
52247029870699869227676341773513258602908903875707454368077876422385333700692089
61635100923358730398654390607188095255755338036472589500730677212252807817947105
64811713785574510576910443229254290241494335883960936793213616969542512997310310
32804436954501929843820842383121265825740594509426942777307124802176915781835720
08717053877325601798713300550591137782384179164028084140962382084763739301393077
84285545452223675598246662506087542848761041456613622276424059143044555808563181
80935230407793891614902116292400515074914068443203230365609954878620999194306564
45533254713555736531851601170032155069078771675206288152788589714941032098698408
30489665243510305024446799317791476591034289491290541203616016956712221408063694
05940304552186212879933092856231022418446365289097444640151986623183881962444822
59078358591404368619301904145896269387890703498216986869693444808621399053459179
28266543047982072196341347556465254831437711566784590777971965107724680002935815
46267646310224279007313631352522067062951125935874473134186492497282784796644585
44896293290526205806524858870702087938913447608334465317093924240824932800891573
13195413483118209277524868805487339433158675626661221793550511906099929113794456
34995627391898459029021713155706096267881673302940198464237390445098028030948975
98125925205585097353743655682578031368190200715167569382728181882458754171072118
08065564480391225045370894226953583821925350756928340956398592655997403913167092
90043996275976830375217503360879028295673068862263077729733533853682668734519035
70970968732232373830049409012323927431875904652632709517840626726482889364689659
32191695211063617297570743761480616013311049116922713186094041450148428664236347
16982892418180484365230538864559809839273836490685480823014267803143937440431807
82267877949400620648915124895251654300563444837504675175420704331337248687063323
75616452323604819320243775968909147833721795536769926032357151855133910984027390
63753280702313301755754269396202629423910945323537910125948964941812563672992967
08425066759980345627345559855962851228141458255602484178330564524050845006598875
59875186013358606249327844877720068422965919455165395629829605916100465789072148
42054861830418175604559815168088031783080261445994444677918012432146400983610678
68341297487259672925878680622308011582202628901436445900230164582366670926557126
45599257906223047452356255751117707915120027893809757754685461210173075227992414
07026308137792971909461413145802081087738121624539858769697371425881836152605069
38092691771208732191500583197711332279357238507194061276129187257209940493025027
77481566140213274347438819664133300526342290829064009279449248085561311834401618
04801357032507836323938921567643159620442612809700944107776130638909071294456394
05660155924602545420477118614042015523337127050137712103457000957800938926532938
57204785765087771496634030035623805957571916093821713122228104658583889435071764
31939973012661591423837170284400120399485880996231859472474858776584355077006934
09922034037877219272837030138083814439411498497173076616296134205910501481428394
97006959516769390415579028563569110555473126845714974496353205546779407751840566
67637222969090346128706829887104278761090090999160443821794511763620835379716161
83312436443126785543555080050798612466439772413550212823802672671991498972724851
29812872836974892764207928686669701772597944078581559093325085541312999465811185
27691652464790819119384233275897699573012098103009171001695718791616942270079528
91519191252105389183853895931516740050572381740103062100438024301118797770425232
80732365751296093724560536800375165961642361477093303912244097528717320679761281
20428026739256557305675931512645750047875756531854825821411574030473147492511910
83561576573200254610968670189030764853137383291268248174118135903282662508254931
32114314789533523170439890539285349466428860742683718249024980924794872266336868
23799580875637040808655649321905489637785549531167397935270799470452399153297534
35869051410586409653451418289647443936718285271184356079928589597817654395011308
88484191635166732136928608309567445028018003737164580091680829727087156091850386
54053436660045504985624687376022557041595800250174095361839287643458003670864954
05794172008513635712716376832349313423070382127448450144052954169537438194545945
65331651409909937227228010196546527262278315121034676861668261314718436100255178
63247950150022953695466317739589344131481485834694374523981159954666071205997794
36344018507836089910894807341963393925931897394094311004211672912019972262660987
19270140241058055153151001098049960441472910394510303126641147267368399733150350
36742741546992633165270432940675237449075056739508929674779115800864399992564817
20884742925082154627985607912776861194608621034940553585013447219024454382452108
92844094981327170106739664711149318967899776615954881861931769001750279017838246
24387873831483279500879026433992577026588005849778984624295660321276945810824348
12969084097255067105473247131725499719190103955330584704072808169315862609388601
91476899441376736214320836073751315743763167546664791867538965715551008506268100
05119827486807780592667765654100834778571024250133253391587384761024129794736751
00116349897780374593002545760987067109215359711517825201428121664754303407512860
02402970384286159842898166021434298490889173596821922844691230359043298772318433
09914187264674607558318725713138832356015809009594182530207799397648462597901883
34179383092096584146357441198587829647585094305300814834182174782660377376225299
77034687529035173107920832200380808092121643465868179898105042743753857867891863
50517717501606531826406928883250135919517178537687865881752366421534010961295763
07476264807031275736578776235285905715393248457650394439049666808771189919249893
38965248523955367958275306141671317579157563866060048399941795487058682092011951
54952031294562451315422506574858629161606523796643010172693950282294667489681746
82116399679495029428401309923590127825043742819255763453321757616229275111059836
82715672297786200537229323140828870587494440601162365216277175585030134514714527
65841864277071769968435499620257547431811994883385806759692359580622165832464092
09535064835793581774290301831535129001432149551817745690838871932069776969565777
17544991499114313689508361606925396064698933748709429332191856012991085644702562
57163505508620689240297589684714283678684735455533583477652536156578189996983068
65467173644599634313646819542742049047243306467500144269750832236901308389549263
70667784065313286648860801295137717208475811577194910123451417749414827735800414
32667332379617716965698582785832300505265883502247868050648201444570593197343382
92386007260169651090325898090991283765227538149352984509941496693386281556803130
69810645251927038185158726486917625632394414252161184277691450677184117357143966
81005615483952443154944864238384298900399826113322468963346522104692545137969276
00971964533895533210558424564018744861105095911176682894271164005401050377042034
60525213182280458929986379035723506651087823500433499423912852363088965109892466
41056331584171142885304143772286629832318970869030400301325951476774237516158840
91583805915167350451913117819394342848292227230406142258207802782914807042676162
93025392283210849177599842005951053121647318184094931398004440728473259026091697
30998153853939031280878823902948001579008000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
real 0m1.902s
user 0m1.744s
sys 0m0.032sさすがBigNum。
