160220(2)

Ruby


Number of smooth weakly unimodal compositions of n into positive parts such that the first and last part are 1(3)

さらに速くし、もっと調べてみた。
（実行時間は35分くらい。）

def A001522(n)
  ary = [1]
  a = []
  (n + 1).times{a << Array.new(n + 1){0}}
  a[0][0] = 1
  (1..n).each{|x|
    b = Marshal.load(Marshal.dump(a))
    (1..n).each{|i| (0..n - x).each{|j| b[i][j + x] += a[i - 1][j]}}
    a = b
    # 1, 1, … , 1の真っ平らなもの
    s = 1
    # 山型
    (1..x - 1).each{|i|
      (1..i).each{|k|
        s += a[k][i] * a[k + 1][x - i]
        break if a[k][x] == 0
      }
    }
    ary << s
  }
  ary
end

p A001522(2000)

出力結果
[1, 1, 1, 1, 2, 3, 5, 7, 10, 14, 19, 26, 35, 47, 62, 82, 107, 139, 179, 230, 293, 372, 470, 591, 740, 924, 1148, 1422, 1756, 2161, 2651, 3244, 3957, 4815, 5844, 7075, 8545, 10299, 12383, 14859, 17794, 21267, 25368, 30207, 35902, 42600, 50462, 59678, 70465, 83079, 97800, 114967, 134956, 158205, 185209, 216546, 252859, 294902, 343518, 399680, 464487, 539205, 625246, 724247, 838042, 968726, 1118660, 1290541, 1487389, 1712659, 1970221, 2264473, 2600357, 2983481, 3420118, 3917392, 4483279, 5126785, 5858008, 6688344, 7630529, 8698935, 9909619, 11280641, 12832196, 14586967, 16570260, 18810493, 21339363, 24192369, 27409105, 31033879, 35116025, 39710717, 44879358, 50690487, 57220370, 64554052, 72786034, 82021639, 92377832, 103984768, 116986932, 131544972, 147837027, 166061023, 186436302, 209206271, 234640552, 263038106, 294729764, 330082125, 369500620, 413434038, 462378446, 516882557, 577552386, 645057814, 720138225, 803610203, 896374566, 999425489, 1113858868, 1240883427, 1381830778, 1538168452, 1711512298, 1903641945, 2116515550, 2352288440, 2613330788, 2902249590, 3221910173, 3575462224, 3966365363, 4398420368, 4875799726, 5403084414, 5985300779, 6627964097, 7337122322, 8119408068, 8982090692, 9933137585, 10981276611, 12136068505, 13407980851, 14808474162, 16350089673, 18046550696, 19912867307, 21965455962, 24222263215, 26702907394, 29428825009, 32423437435, 35712324713, 39323421809, 43287223612, 47637016715, 52409121310, 57643163457, 63382361133, 69673844302, 76568991529, 84123806825, 92399315881, 101462008094, 111384303557, 122245071599, 134130179128, 147133099710, 161355557401, 176908239895, 193911555100, 212496466196, 232805378126, 254993115975, 279227963489, 305692806742, 334586351164, 366124458109, 400541567901, 438092262433, 479052928555, 523723581303, 572429808511, 625524897652, 683392105041, 746447136977, 815140796679, 889961874362, 971440234557, 1060150181193, 1156714053255, 1261806142717, 1376156880379, 1500557391432, 1635864367436, 1783005361285, 1942984450651, 2116888391019, 2305893196147, 2511271280479, 2734399102923, 2976765453900, 3239980324902, 3525784521090, 3836059948141, 4172840751685, 4538325243851, 4934888806335, 5365097705219, 5831724031676, 6337761696275, 6886443714745, 7481260718503, 8125980944068, 8824671638261, 9581722165709, 10401868749151, 11290221161267, 12252291308167, 13294024047247, 14421830186724, 15642622052899, 16963851569589, 18393551279148, 19940378265174, 21613661441237, 23423452179922, 25380578804722, 27496704921371, 29784392170791, 32257167405782, 34929594924193, 37817353785002, 40937320918825, 44307660072067, 47947917377861, 51879123632893, 56123904146670, 60706596283009, 65653375667880, 70992391211653, 76753910032966, 82970472495100, 89677058547376, 96911265647600, 104713499605793, 113127178679475, 122198952417857, 131978935680652, 142520959480878, 153882839180063, 166126661889154, 179319093696670, 193531708796403, 208841341282340, 225330461900753, 243087580684818, 262207678045233, 282792665395260, 304951878190333, 328802602679322, 354470639559798, 382090906075091, 411808080140060, 443777288275252, 478164841366785, 515149020358757, 554920916341908, 597685327505713, 643661717970053, 693085241338216, 746207834592411, 803299385657065, 864648980888417, 930566236353322, 1001382719929531, 1077453468658140, 1159158609233039, 1246905086769652, 1341128510646583, 1442295123354393, 1550903902232083, 1667488800877179, 1792621141310599, 1926912164721806, 2071015753168879, 2225631331220775, 2391506961444324, 2569442643982646, 2760293835821165, 2964975201500249, 3184464612708230, 3419807410204551, 3672120947655828, 3942599432684810, 4232519087101609, 4543243643803942, 4876230204923081, 5233035481151493, 5615322439852124, 6024867384578153, 6463567496966674, 6933448866786347, 7436675044793324, 7975556147703767, 8552558554189085, 9170315225100529, 9831636691565035, 10539522748676155, 11297174903639833, 12108009621161388, 12975672420908876, 13904052875446815, 14897300570137024, 15959842079856624, 17096399031390158, 18312007313576263, 19612037512457879, 21002216641545844, 22488651253804652, 24077852014657585, 25776759832985125, 27592773639706129, 29533779922685526, 31608184119001144, 33824943986446450, 36193605068337595, 38724338388068883, 41427980502077499, 44316076064151547, 47400923045987928, 50695620785333705, 54214121025048904, 57971282134858504, 61982926699760053, 66265902689920836, 70838148419005258, 75718761531505770, 80928072252003522, 86487721165540037, 92420741791088628, 98751648249525285, 105506528320473303, 112713142225364960, 120401027467619768, 128601610107256145, 137348322841668104, 146676730314810844, 156624662072025765, 167232353632860160, 178542596150315081, 190600895184620517, 203455639117172036, 217158277795271169, 231763511997046108, 247329494376930102, 263918042552656895, 281594865071737557, 300429800998301009, 320497073945177823, 341875561381149834, 364649080135118266, 388906689026941187, 414743009654466977, 442258566377895289, 471560146651562643, 502761182868342610, 535982157001081924, 571351029345129768, 609003692795803573, 649084454119694381, 691746543820610756, 737152656231466413, 785475521618824263, 836898512124131937, 891616283535120982, 949835454926160386, 1011775328391808037, 1077668651151363403, 1147762422505509142, 1222318748189705166, 1301615744890981095, 1385948497769966870, 1475630074073202042, 1570992596008144778, 1672388376320107345, 1780191120112238511, 1894797196741418860, 2016626985741495945, 2146126301045224898, 2283767897912557181, 2430053067324169045, 2585513322756169435, 2750712184636493112, 2926247067964226699, 3112751278995185495, 3310896127103212290, 3521393158390366257, 3744996517854771479, 3982505447433130037, 4234766927503896464, 4502678469995333094, 4787191071547729099, 5089312335792697135, 5410109774158938220, 5750714295287087604, 6112323893529478500, 6496207547750562628, 6903709342087696492, 7336252821145776396, 7795345592601023624, 8282584191082747184, 8799659217768776156, 9348360771112819169, 9930584184759766185, 10548336089786062490, 11203740819120373216, 11899047173187652075, 12636635566627863054, 13419025577247450081, 14248883919268193076, 15129032864376519663, 16062459135093881853, 17052323296570185872, 18101969674043886815, 19214936824952717261, 20394968595956542314, 21646025797049925208, 22972298526372177019, 24378219181430134869, 25868476194049395455, 27448028528689682390, 29122120985547297703, 30896300352422317045, 32776432451324628913, 34768720128603736122, 36879722239616529185, 39116373682042052102, 41486006534437268435, 43996372360036217381, 46655665738565469715, 49472549092599806450, 52456178878069908087, 55616233212664298344, 58962941019304389060, 62507112766420701786, 66260172890583483222, 70234193992048265203, 74441932898033226650, 78896868694059367675, 83613242828414887217, 88606101400878342648, 93891339752092669094, 99485749476667460089, 105407067988928614198, 111674030777596326485, 118306426492156624259, 125325155011799454345, 132752288654993736393, 140611136696694945381, 148926313368167673525, 157723809524233373550, 167031068171608808765, 176877064062823141003, 187292387570019401621, 198309333064858981468, 209961992041629934719, 222286351233776046396, 235320395986116559117, 249104219159468025812, 263680135857728587819, 279092804283380160219, 295389353042144475174, 312619515235026940981, 330835769692337461484, 350093489723540066693, 370451099774879292083, 391970240407929857614, 414715942032233877213, 438756807848521607334, 464165206481142718447, 491017474804014455974, 519394131488857914143, 549380101832748684324, 581064954449047018664, 614543150436864070089, 649914305674089880645, 687283466913220322201, 726761402392211939348, 768464907710228599781, 812517127754576978577, 859047895506530556839, 908194088593957858986, 960100004504216158393, 1014917755415158088329, 1072807683652189499069, 1133938798828295684041, 1198489237779043800590, 1266646748458594999043, 1338609199023345719696, 1414585113389402376669, 1494794234616708303274, 1579468117538344775022, 1668850752126770396425, 1763199219161187329845, 1862784379840746897728, 1967891601068129185656, 2078821518216542607592, 2195890837281148341366, 2319433178413202525532, 2449799962932103923897, 2587361346017461034926, 2732507197390016150267, 2885648132407760647920, 3047216596121103462476, 3217668002960060893239, 3397481934855824342731, 3587163400740912807944, 3787244160514542896069, 3998284116715672882158, 4220872777302926562814, 4455630793111766153107, 4703211573731751057972, 4964302985734714748388, 5239629137374426898749, 5529952254084754691032, 5836074649312032204682, 6158840795444039622206, 6499139499827487844440, 6857906191114803506510, 7236125321433338735687, 7634832890143365905409, 8055119095228608091259, 8498131118662983704591, 8965076052402115312420, 9457223971977345152398, 9975911165005026957155, 10522543522285118759320, 11098600099531206636239, 11705636858170494704551, 12345290594056660235656, 13019283063373401398428, 13729425315450635048727, 14477622242692424050071, 15265877358303442923696, 16096297813024149977224, 16971099662620335898290, 17892613398446732309184, 18863289753992234055200, 19885705800943765297736, 20962571348951079258990, 22096735663965010781127, 23291194520729818785908, 24549097605767015744942, 25873756287965071558971, 27268651774718962212449, 28737443672415965466747, 30283978970973425494526, 31912301473069238812078, 33626661689702419470814, 35431527224746591448308, 37331593672251371653031, 39331796051371141234435, 41437320804997353820165, 43653618389403462199537, 45986416483522585018374, 48441733847829629743374, 51025894864235752928868, 53745544789884500725419, 56607665759312032497365, 59619593571057370708700, 62789035296531422522463, 66124087750732521440137, 69633256866282780391990, 73325478014208622604635, 77210137316954473951860, 81297094001253668363180, 85596703840742042104064, 90119843740538188502497, 94877937518489807637931, 99882982940346534965033, 105147580068829089014685, 110684960989368714639091, 116509020978256117015129, 122634351182009091243756, 129076272880012752944756, 135850873405846907884482, 142975043806265221795194, 150466518320469075516887, 158343915766202829049943, 166626782923222521064755, 175335640008938408030417, 184492028345436289160078, 194118560321729168276330, 204238971759909623658209, 214878176798954821203344, 226062325415207490435164, 237818863704112719937555, 250176597053556121273639, 263165756345224124174533, 276818067326712639996410, 291166823303751860454102, 306246961308809872290804, 322095141909597501540284, 338749832828535280089197, 356251396552178003127516, 374642182117833341553157, 393966621273282114329051, 414271329214515676189607, 435605210115880794919133, 458019567676867204444373, 481568220920125046670654, 506307625486057529267560, 532297000680643147805925, 559598462544896510447094, 588277163226729794087019, 618401436948818837183231, 650042952879569677996029, 683276875228309365269409, 718182030900558776873178, 754841085064566911908513, 793340724996374568176157, 833771852587408009246803, 876229785916168755131609, 920814470303856903622566, 967630699292941425041145, 1016788346007639799775373, 1068402605376201104568790, 1122594247716664634954598, 1179489884210611772317326, 1239222244813200588493119, 1301930469172704357706591, 1367760411158720188192791, 1436864957625419035734790, 1509404362064521965333172, 1585546593832369936070062, 1665467703666349015440401, 1749352206238314654557266, 1837393480526365648644317, 1929794188821640869441492, 2026766715223582897619482, 2128533624515638679721738, 2235328142353476156233142, 2347394657739811200715883, 2464989248803683733436836, 2588380232947837512590126, 2717848742475562362930889, 2853689326858311727538404, 2996210582857424737402727, 3145735813767742422397691, 3302603719107619351729334, 3467169116139198583208731, 3639803694664641590860637, 3820896806608712523410848, 4010856291965505091834933, 4210109342757621977238602, 4419103406729563437297708, 4638307132573931162492283, 4868211358569093602446988, 5109330146590694870156548, 5362201863546604856061187, 5627390312376137813654417, 5905485914849390244807771, 6197106948501932052770933, 6502900840143604051761437, 6823545518488428689736380, 7159750828565402429665614, 7512260010687841755032142, 7881851246881770537045401, 8269339277802236079849579, 8675577093300192905054120, 9101457699942408527906284, 9547915968932490905320206, 10015930568033366809631664, 10506525981250119938213555, 11020774620197826114783424, 11559799031251666553524546, 12124774202757005743205851, 12716929976765055054404110, 13337553569956104978236347, 13987992208616866798702250, 14669655882752171232794193, 15384020224633899402297313, 16132629517322581065218232, 16917099838939363057842676, 17739122348719100143627709, 18600466721138933472726376, 19502984734692037291806909, 20448614022163022865399732, 21439381989560998576641981, 22477409911178296765559292, 23564917208568675114668379, 24704225921578194548487611, 25897765379916330709300514, 27148077084124017456089786, 28457819805180697712355784, 29829774912393910988172961, 31266851939634018660972252, 32772094400413218148286420, 34348685862763663315000836, 35999956295344173872875301, 37729388696700422694852372, 39540626020119545456754504, 41437478407058674689862520, 43423930742687897855802167, 45504150547673547803776477, 47682496220937525418714400, 49963525648764626251308160, 52352005196292604835930691, 54852919098111195898695022, 57471479265416572842443139, 60213135527919139167806818, 63083586329485218767653281, 66088789897309669323048085, 69234975905266844602049684, 72528657652974375386330995, 75976644783028141009860859, 79586056559830440324456592, 83364335734437026898646289, 87319263020895414025821543, 91458972210637041239204863, 95791965952622794573316229, 100327132228125432717740427, 105073761550267176809771164, 110041564919716612391724117, 115240692569289846759011369, 120681753531597207310512855, 126375836065332625053807081, 132334528977318981135586627, 138569943879003338544796808, 145094738417742023322977784, 151922140524931480814830301, 159065973724827741147010015, 166540683549760012402140279, 174361365109383563682715762, 182543791863638820060131029, 191104445651188823242826995, 200060548027301424121119717, 209430092967427310885800017, 219231880995106125795807362, 229485554795312236887864008, 240211636376935499416736578, 251431565850782546294561335, 263167741892287512562205711, 275443563961039856931108570, 288283476352278285422739485, 301713014158666213174495003, 315758851223963411945418728, 330448850173643289283753817, 345812114611083857837115337, 361879043571686015700353428, 378681388331154074209279913, 396252311668214033936242793, 414626449686254343459577849, 433839976302755669271501966, 453930670519940641976904683, 474937986594825944718362866, 496903127231808269898608104, 519869119926067380527797681, 543880896591435332134535771, 568985376611966144974882528, 595231553462257243325108294, 622670585047628663587257002, 651355887921571636619027238, 681343235544441146728266839, 712690860754201667010794607, 745459562627148608942853972, 779712817913935325920436502, 815516897243944641147445368, 852940986299071145012015704, 892057312166334579731503184, 932941275087442987313430332, 975671585832476454353988644, 1020330408934286990991146214, 1067003512030017779132470491, 1115780421566355818808173849, 1166754585135757354162190450, 1220023540721946928737319536, 1275689093144501071731822412, 1333857498004309572049700825, 1394639653444174823554817977, 1458151300051787623427093222, 1524513229245821147145030373, 1593851500499940214478858950, 1666297667774146888907357795, 1741989015538104464404975442, 1821068804786918013059990996, 1903686529466331528314408953, 1989998183741448993154415525, 2080166540560932306746036580, 2174361441987194418630671190, 2272760101782426533317722414, 2375547420760397323844679265, 2482916315434877610520406220, 2595068060517301511352746876, 2712212645838915320007044518, 2834569148296216213898349477, 2962366119442988000914187131, 3095841989377730875810463607, 3235245487601803461067700764, 3380836081551181356441638585, 3532884433533437364763450179, 3691672876831400537723345646, 3857495911766008266198455353, 4030660722543167040163544053, 4211487715743041301605320093, 4400311081345138662953907914, 4597479377218916048034018402, 4803356138047441408939676987, 5018320509690976595376002174, 5242767910038249107235698997, 5477110717435725843087075936, 5721778987829445328321900135, 5977221201799983618897081771, 6243905042718982607430267133, 6522318207305440918126834352, 6812969249911721541584516500, 7116388461923056135631463879, 7433128787710293592078498970, 7763766778633846007846194187, 8108903586657304652655968852, 8469165999192135022605282833, 8845207516860296102145716919, 9237709475929675359892673570, 9647382217247977230410062632, 10074966303574268002560740835, 10521233787283861124593662945, 10986989530501751972951517049, 11473072579802485222719812714, 11980357597700298712302904780, 12509756353242748998199977475, 13062219274113933561035749191, 13638737062750006219910660032, 14240342379070094731772952855, 14868111592530106402605122884, 15523166606315419729744319522, 16206676756601252288818788484, 16919860789926751001288953185, 17663988921850727163544480977, 18440384980183652692131690096, 19250428636222215414944401874, 20095557727549612243283620008, 20977270676107023064885381913, 21897129005389583467260345934, 22856759960773859304033438518, 23857859237143566053192390300, 24902193818146285435010829500, 25991604931586474687224698883, 27128011125639372237737482285, 28313411470756760912760348927, 29549888892329207100952828209, 30839613639370656407356536438, 32184846894700404406533068135, 33587944532314802998801441295, 35051361027866901608651576718, 36577653528406910527216609942, 38169486087780227719016230303, 39829634074333169354558185245, 41560988757839830267236337311, 43366562082837080908474032291, 45249491635838951686904363259, 47213045814197001879570835090, 49260629204680117656992501351, 51395788180166003131049307854, 53622216723167850631661483097, 55943762485263807989572784403, 58364433091854366688146273971, 60888402702044219724300330262, 63520018833830984113383893795, 66263809465184035445116020738, 69124490422013102813580811416, 72106973064458851016577179809, 75216372283387018126821316407, 78458014819434456832946137660, 81837447917440278535675058817, 85360448329598947292494730396, 89033031681195297313408196104, 92861462213324834630362835832, 96852262917567065373632980403, 101012226078165810257071335389, 105348424237879309698298337038, 109868221604295299986774283218, 114579285914063002493840815803, 119489600773176086357413606477, 124607478492149061686370825690, 129941573435665279188082579143, 135500895907038746544647720441, 141294826588625444160680666795, 147333131560143803884054809461, 153625977917719710353057623467, 160183950017359949944254109013, 167018066367480763617949530266, 174139797196076301219000890032, 181561082719106719789087481125, 189294352137718757672459188527, 197352543392984347748673598364, 205749123707956651370132339602, 214498110947999409667569709895, 223614095831546276937683861725, 233112265024693552368256071759, 243008425154324137720972075506, 253319027775804479631908540186, 264061195332691511530005232397, 275252748147335190586105743886, 286912232482766074276694192848, 299058949717818647071026395859, 311712986679061884654654175581, 324895247174791139274108999331, 338627484778082100250434626147, 352932336907720808912275910371, 367833360257705915066653809651, 383355067627973218009023959503, 399522966211020652779302336371, 416363597391217125840269976424, 433904578115763787219182512301, 452174643898544525619540106168, 471203693520456717517979001294, 491022835492256857032562415674, 511664436348491899704320186254, 533162170843719522425920397144, 555551074124952541039541081471, 578867595957098252825472557722, 603149657081106257354136357381, 628436707787592455715233455800, 654769788791876495672970485956, 682191594499659322982005588416, 710746538755981085550016097539, 740480823173642148319994491123, 771442508140946112122277367528, 803681586612438571129024380519, 837250060790273945809086749950, 872202021807950549887635686953, 908593732532416527449942544836, 946483713604972292742282223387, 985932832845984467246749500110, 1027004398153188332944165688273, 1069764254028296794683945299071, 1114280881871760530741448005224, 1160625504190843169436359532860, 1208872192871694223501970214799, 1259097981671828411322499009153, 1311382983095360694081425737783, 1365810509819509674502225275391, 1422467200847276310859244771298, 1481443152567838599377921314444, 1542832054913084961507779061958, 1606731332805848568989595376330, 1673242293102811404581342222455, 1742470277242730194267135807902, 1814524819818606824535938676976, 1889519813300693905412642346586, 1967573679145802886358502325425, 2048809545537278785758372281189, 2133355432009234104311617214445, 2221344441218206901468934879652, 2312914958135337149406769731786, 2408210856942454280767378787317, 2507381715926151084177353091207, 2610583040674998677571842990419, 2717976495896548984120439641204, 2829730146182689883961811231142, 2946018706064279881841805902066, 3067023799708809759177920804130, 3192934230628135296869941372043, 3323946261777114994511500150874, 3460263906438288047688864665784, 3602099230302559185771612719595, 3749672665171237930901440165695, 3903213334720730291537239880109, 4062959392787721898395507998568, 4229158374649844472137589532430, 4402067561794604866542078854400, 4581954360687800678569069893828, 4769096696071772793109919020953, 4963783419343677845363702120272, 5166314732584528441856095608423, 5377002628831072504448385822416, 5596171349204693190816575441353, 5824157857534435865818361825564, 6061312333135038484609103869332, 6307998682425486950782919121748, 6564595070099169644542270139958, 6831494470583198062737203073748, 7109105240551927824466224697450, 7397851713288191255514962301291, 7698174815715276326807922584124, 8010532708953294539021983683156, 8335401453285312056838019068661, 8673275698451514410266745895070, 9024669400223777913869068626649, 9390116564248373969922798350658, 9770172018181181219502507529302, 10165412213177771615362299670623, 10576436055840118818444544102259, 11003865771762500789911380730963, 11448347801861485510776212587002, 11910553732718752974456751586469, 12391181262210974207406763517102, 12890955201748096542526538000415, 13410628516490234009867773617149, 13950983404963994162393381460516, 14512832419551552589502136779678, 15097019629380179910509237461156, 15704421827196302521508115829774, 16335949781866608715350871103367, 16992549538209270345175161768866, 17675203765921113024329310263104, 18384933159431614647711799116953, 19122797890582024360548797928490, 19889899116097757428985984874882, 20687380541894623267078020561196, 21516430046334475734409413235991, 22378281364623630549030444247460, 23274215836627972435650590320504, 24205564220462175038342295732455, 25173708574296984898906344168340, 26180084208918184786440432002715, 27226181713663764144495445461560, 28313549058462101026812888355920, 29443793774793721496440186540871, 30618585218502573023697681125939, 31839656917489857476579671064040, 33108809007434449732516174459654, 34427910758798918572446280699406, 35798903198499309782073715001240, 37223801829740296036035202959273, 38704699453645196846694992639366, 40243769096442884013709226942991, 41843267046110877239507653060539, 43505536002516171662704688101209, 45233008345242699365960043376215, 47028209523446993414371942359318, 48893761572241783598353993656468, 50832386760271103822955426897923, 52846911373310233378187886191496, 54940269638899638148540110815912, 57115507797204238949849235405447, 59375788323478037583299574103914, 61724394307709608061561286383097, 64164733997226451767808912177628, 66700345508245968749761198514172, 69334901712578071042267198035031, 72072215305909523213804694335427, 74916244064333216700398555675666, 77871096296027052193456171426770, 80941036495237214470933149605740, 84130491205979681109797068705896, 87444055103142127583154327634894, 90886497298946302491890073083712, 94462767883018787677879619839309, 98178004704616178056326949218765, 102037540405859478810944767800562, 106046909715152297263461104606291, 110211857010288592616525023432347, 114538344161098739563419161296300, 119032558661837878352552887838841, 123700922063888393375043233097220, 128550098719729331062348653466509, 133587004849520095308026304595887, 138818817942054322631298882853219, 144252986502262931858103808492524, 149897240157883475789465480438588, 155759600138366621912446569535707, 161848390139560403330929311300703, 168172247588199373710209899473907, 174740135320729557361118488930354, 181561353691521711390368187387251, 188645553126065538593449133316020, 196002747135296753786275746941573, 203643325807787984169171659092898, 211578069797134067942509322814408, 219818164822483123548076844149921, 228375216700807535139467313152091, 237261266930174507458606733284709, 246488808843964877836435251224070, 256070804356702257784045696569659, 266020701322893159910224235034822, 276352451531043428643231584913101, 287080529355807943316462981930508, 298219951092050142257305344046100, 309786294995436398143902856707901, 321795722055068666700650002852185, 334264997524568172426869571425551, 347211513238964265667969878614645, 360653310745717097380485239862749, 374609105279211565997312335367209, 389098310609104285134317453130982, 404141064793986336697538568434898, 419758256872943584724920108936725, 435971554528754652409479220685359, 452803432757665670623708223877090, 470277203581922004397327682567751, 488417046842521811695079846076747, 507248042110985998459429259484795, 526796201760315464359350776696679, 547088505236731102219414154655545, 568152934575266488455567342800409, 590018511203809311687127307252334, 612715334081767115890469917261247, 636274619221167732881197198782485, 660728740639696754498715573582602, 686111272796925525945026843653041, 712457034566795468837998155742736, 739802134801300181267036250048850, 768184019542247894723453296436087, 797641520939995756479754019509642, 828214907940126384461541953702553, 859945938801188628871223490632775, 892877915508850966219245730132737, 927055740154120033417304105442008, 962525973345661150483154627293096, 999336894728725045512148125856404, 1037538565685738237862808890730425, 1077182894296256611412565818554541, 1118323702636715669545132916027707, 1161016796503239967827385826640975, 1205320037643701530177599571315808, 1251293418588246048406086764264404, 1298999140170639829538740487400392, 1348501691836033401961423652912199, 1399867934834093146873150197923358, 1453167188399924146284710058044305, 1508471319028799616465259159715202, 1565854832954428952563204364015039, 1625394971944341804108593384899633, 1687171812529944142322244059409557, 1751268368792918519654416736371481, 1817770698833899372961367582864438, 1886768015053760148203300100878234, 1958352798382407263433005670514634, 2032620916594691676354721590677202, 2109671746857927465465651449144683, 2189608302660553924852838251762659, 2272537365276698963818242826665578, 2358569619926803029838631282535603, 2447819796800050482768300054076031, 2540406817110135682763294965877868, 2636453944361870580781718687610070, 2736088941012326096252143291734183, 2839444230716598047504102236259077, 2946657066354907108220388366601875, 3057869704044588693037798323959429, 3173229583347610564085484516491496, 3292889513891581305274768632162214, 3417007868629789897776301231414204, 3545748783973654002492108548074471, 3679282367039061043003711228364746, 3817784910256470923051979955699294, 3961439113603321638004098247246517, 4110434314726248910349705434944562, 4264966727229908369928400580936415, 4425239687418784135382913976639830, 4591463909788291695396199419659989, 4763857751571746871085748754979258, 4942647486660387858058586482277468, 5128067589224615789672096393088899, 5320361027375973207226905448601785, 5519779567221121967716881853016115, 5726584087671225574778871117699620, 5941044906382699245422673566356085, 6163442117218278223548008952675872, 6394065939630785403033048480853649, 6633217080385868177750878389482874, 6881207108054337056832725384214513, 7138358840719590933829689747022153, 7405006747360972489214814378356541, 7681497363389779081310162475551246, 7968189720831077269903555004162007, 8265455793661451017717851939647249, 8573680958830373448538039644858254, 8893264473511049236308371900664008, 9224619969145349349934022253343841, 9568175962866872726169885153340668, 9924376386906241937872932270380257, 10293681136603494210215915613484634, 10676566637673888110746951314363042, 11073526433395633537949351451612262, 11485071792410992698784475782661962, 11911732337855917830066130851233136, 12354056698557913569909623211244068, 12812613183067165055549554355211655, 13287990477312184857586702030840436, 13780798366698331503158635877239241, 14291668483495569310122779379931415, 14821255080390804229992536700166623, 15370235831110075095548940456256409, 15939312659046836831153288401540075, 16529212594864575656992144181873480, 17140688664075081043668763503884223, 17774520805627901270048176171987754, 18431516822581866191402859317788452, 19112513365966110778897528730144393, 19818376952975815932646098854164161, 20550005020686940124647282995745431, 21308327016514589048969122540784750, 22094305526681404524871989401137338, 22908937444005493711605011134852941, 23753255176362012068554350142075331, 24628327897218606760247871390564045, 25535262839692571310750476560789165, 26475206635626808817172745935575769, 27449346701232603223770243364680242, 28458912670899811042911476770769362, 29505177880829466331985385121260396, 30589460904199998375606194791728055, 31713127139636355018578543328150014, 32877590454811367541872743260104021, 34084314887070750053185121712462576, 35334816403037264343886747890974909, 36630664719215869037139695448582504, 37973485185690180834507271663859568, 39364960735071379346143215258451991, 40806833898933861320754372836627194, 42300908894047573557704020156646035, 43849053780795107396222922208806798, 45453202696242405135439148775607358, 47115358164415396440600106342464290, 48837593486421139996014044943611705, 50622055213141184509832815298449672, 52470965703316978846376691335201287, 54386625769942351810118970214312419, 56371417417976449433023088603076117, 58427806676492166292582930207034784, 60558346528480145641770871790610297, 62765679941636962677315263416866967, 65052543003578261509058317565634609, 67421768165033508432838249485650218, 69876287594698774991167001146281604, 72419136649547701025556388543748776, 75053457464528641659231430618682607, 77782502665708108293755355979368648, 80609639211057112106176705256047500, 83538352363218053537202304615747412, 86572249798735521951298443669290965, 89715065858384929901338554955025930, 92970665943388465169464780516026804, 96343051062468565011442494317875950, 99836362534855170212222832838327573, 103454886854534576511574137782099536, 107203060721204948254321594835707855, 111085476243586680127410793491795002, 115106886320924980032409464256053949, 119272210208717498146554186862736552, 123586539274901749181830748822405427, 128055142952945678469746832422129805, 132683474898500226404258251709786760, 137477179356495375597157974557048204, 142442097745791153831978383528232735, 147584275468732653999636550511649992, 152909968953203567955818530877811716, 158425652935026270899848805745138385, 164138027988818401026192393066739591, 170054028315686428898550417592180317, 176180829796416184182862088855672758, 182525858319108995007762379398044310, 189096798390510297715458240605309278, 195901602040585602143604580985878803, 202948498030216869928807645752653668, 210246001372221010962969599067722723, 217802923176231667100354105539710844, 225628380828336084434602185156264468, 233731808516721039277676653361695773, 242122968114955853313371397161148310, 250811960434926897345962486418915580, 259809236861837040050948097192121926, 269125611384095660515235755624584892, 278772273031350536636061771841878760, 288760798734352584894716309126660093, 299103166620798513899243440657669005, 309811769761765432306361430365138386, 320899430383835804102291741167270714, 332379414562511369141244390606948836, 344265447413031258577372310693904940, 356571728795243064230788905923333403, 369312949549726615747474184971521822, 382504308282939245038677156219257032, 396161528719738957297089337703780851, 410300877642248784040952053675493072, 424939183434652287436586634668123706, 440093855254157357878290905246272327, 455782902849033760126157325303159554, 472024957045320020141452617164065540, 488839290924507909732321710544635129, 506245841715248706467539615730655645, 524265233422885332358173927017921473, 542918800221399180940085812938496742, 562228610633170727579381426896826704, 582217492522789706640630537099288602, 602909058932014582325822300693048242, 624327734783873115475933516644068717, 646498784484816942219632135391958157, 669448340454794166831025085316434433, 693203432616085994908676726427908663, 717792018872767389232134704492509004, 743243016613698646120382354034645472, 769586335273035724338406478004269548, 796852909983363204630159955209937546, 825074736357706043744750418606690234, 854284906437865975986347627908355088, 884517645847756708587446743752118896, 915808352191680193263388085465318163, 948193634738795513311169065274036992, 981711355436383622103386056535914325, 1016400671295906665319727920068389177, 1052302078197301319230759098366416009, 1089457456158432928933330834995946920, 1127910116118172727461582716728795931, 1167704848283145600481687965867238404, 1208887972089832321751021764202567918, 1251507387835399562119444409857877766, 1295612630032374961713738728145218349, 1341254922544084896930201046290996638, 1388487235559631071816261783667700403, 1437364344469100575319820569821185630, 1487942890701684488190067915121732038, 1540281444591424473230009819420957019, 1594440570337417079546260650947228280, 1650482893127483839419229121307918078, 1708473168496563805594994889050606272, 1768478353993406206021228845857963319, 1830567683231536691520422554267731854, 1894812742402943601839441427269836968, 1961287549335483233987652516330680078, 2030068635177637798463283949097246363, 2101235128796979208126254456169885280, 2174868843981498757901250349154628118, 2251054369535859902593086948092269569, 2329879162367621594023241241442497395, 2411433643661565956572780297996578705, 2495811298243449514450605698847573731, 2583108777237784882659836669457112848, 2673426004127653043941600050313959781, 2766866284328048404867350831166341029, 2863536418387873210079980259883471013, 2963546818939428156925897685945388905, 3067011631518095867908669507438696623, 3174048859378887035010988027128538857, 3284780492440619456568024476467619076, 3399332640492731874821156918455215595, 3517835670804101647929182601725878894, 3640424350277742141355675822017367523, 3767237992299906722038551983886018842, 3898420608436925944513437281564161652, 4034121065138057634152684668672476268, 4174493245607740948613636959348027475, 4319696217015920136172567250409032531, 4469894403220546766565362879464029717, 4625257763181986005502039823042024045, 4785961975254848523215081132568905652, 4952188627548750526943735834110761405, 5124125414555676020069861984759928296, 5301966340247983732040821562651929901, 5485911927857672435856480812332877483, 5676169436554298970211831229058197369, 5872953085245939806851784844897763573, 6076484283734806251754839748053699081, 6286991871466572354363064619443802126, 6504712364120160554011347465424442975, 6729890208292660473521668166319587030, 6962778044542238765688280506007229028, 7203636979060340456973217855763627128, 7452736864253192989096579478195666898, 7710356588521611562034872038659468759, 7976784375537377122399703414708353317, 8252318093324025380040621730416379419, 8537265573459755812630851111170386065, 8831944940730353259041724579907019613, 9136684953570521229813231822670134945, 9451825355642865603646185691866687101, 9777717238914950373929223476557807782, 10114723418606384323549039370342097664, 10463218820389800038579087736864154108, 10823590880241865964345460039858778814, 11196239957353140058362178268318731951, 11581579760518642166124264096454385326, 11980037788444504077329387800266332879, 12392055784419964238946646912482556048, 12818090205818321635455630375994494329, 13258612708905264135041510336603905106, 13714110649448254808548765762788291974, 14185087599636409957870728810066506311, 14672063881836549896394583354865103227, 15175577119727863424820069807287542451, 15696182807374915439753313061411357692, 16234454896816560691891612928671581525, 16790986404766722377001142249812284518, 17366390039041969521816735195227787446, 17961298845350400085302935427945344236, 18576366875096525956667477230988258139, 19212269874877680793157776535044954196, 19869705998368951691941377960706126272, 20549396541315791430569088640455275693, 21252086700376320466432564348738377736, 21978546356578898732141095007672189403, 22729570884184858842065226922505760350, 23505981985771367664787497270172231344, 24308628554375246053758293524784476923, 25138387563565251331624696733335320725, 25996164986337839111295056364137808674, 26882896743759796203385221501281842041, 27799549684310401497495972683152256736, 28747122594905954429630199866988235708, 29726647244620639422713699149178765619, 30739189462149798848751470814346177682, 31785850248094796845896840869556800734, 32867766923182802896142825860148157364, 33986114313570039548550614898225297635, 35142105974413356163392339699427839580, 36336995452932444172173425306314193360, 37572077592223634261113021419445699217, 38848689877126048330974739037527335601, 40168213823481956414184310344547571691, 41532076412175549432941354326231988096, 42941751569378022430117029684156061516, 44398761694471910580897622371916245995, 45904679237174074031134376128779939812, 47461128325424630828608217934798394525, 49069786445658534664093798316283488676, 50732386177127431934069885927377479511, 52450716981991958299242442408954019852, 54226627052958797415283274134996876660, 56062025220292674322501802910630709766, 57958882920091045106109121668132041269, 59919236225768626472080352952586408510, 61945187944760139051829009134118999752, 64038909782512773462843404948653108922, 66202644575904987055650034915583219532, 68438708598295362300993892585064834297, 70749493938474467184737371129065142115, 73137470955864017948244991177075771995, 75605190814381221156736542109866142310, 78155288097462033527765274339677387156, 80790483506815294407637248788909292829, 83513586647560329581903902311712411764, 86327498902483770780723208583973597896, 89235216398237059590590106131377238667, 92239833066384486641544815494831870334, 95344543802302738438574259084450116939, 98552647725026869056036452280736175978, 101867551541234468673879265468207409429, 105292773016659654787757963732499488749, 108831944558331456761669127821638944237, 112488816911137294885376290091239080031, 116267262972321668794676202155158775359, 120171281727642967509161160266156385388, 124205002313027597984005954547731737375, 128372688205680507637412439193136531032, 132678741548734758712589814946913932971, 137127707613650211795583785040889269384, 141724279404702708998259812866001047262, 146473302410040534415879111649849904369, 151379779503924494303064105040890174494, 156448876004911829543061924216071193331, 161685924894892479831800253853967833292, 167096432204039097946557369438256091274, 172686082566889802995543384260907253364, 178460744954945107334007091906515731718, 184426478591327900907463934140997510292, 190589539053227981629586113428115323373, 196956384568030538108498486452760452037, 203533682509211383421952871079582792749, 210328316098270772409994412933676065192, 217347391319172481824861790406264775068, 224598244051955669548487660116333987439, 232088447432394038179175809142323677464, 239825819444790197309851385495565770604, 247818430755213041126399579087939835860, 256074612792712632721382991422045212146, 264602966086280718909238479266309084599, 273412368865565800678519769412832231361, 282511985933599872409286932124503244772, 291911277820049741847587484088343524433, 301620010223769483525554588835598457122, 311648263753702298745061353812768078619, 322006443977460100444694302168040797274, 332705291787197763640703506661841473698, 343755894092696441639239746961065522737, 355169694851876912626749288097285505495, 366958506449279866351273535161438932175, 379134521433375650473280426275310488951, 391710324623901563363916824580975370945, 404698905600770606002688162020555458836, 418113671586452000538947265002970794232, 431968460734091066691167826837346606387, 446277555834014548688423772713516100071, 461055698451657543987842131455903141646, 476318103510350149747811617333861892518, 492080474332816173663697141109110191909, 508359018155663122693983554848775564464, 525170462131582567907224446197576324124, 542532069834433279045407473038977051342, 560461658282846633047270370011451030565, 578977615498475143403853246670658971274, 598098918615500960968735857248080375848, 617845152558532303660212263720831033435, 638236529306542437503592615952522077918, 659293907761048523370424745455839550075, 681038814237286845257551345730276955113, 703493463597717144075356334835640475584, 726680781047782507559313752260824377770, 750624424614463039204060875930866457709, 775348808328791889868382066546208409393, 800879126134151743892521199458311823896, 827241376542839082826583159473639824369, 854462388064073096933060846001018494191, 882569845427336587875503141426465852964, 911592316625668233962198564595473808651, 941559280804279819190139106744373713948, 972501157020649125571237669106232232654, 1004449333903039841064641687770944869169, 1037436200235224749507765458709920819201, 1071495176496038371841631561018607090123, 1106660747383260868863009802765851172684, 1142968495352237166143159638893865127493, 1180455135200564715946974505474091959281, 1219158549731140886845037588314426542756, 1259117826526847511355574694255650850366, 1300373295871166492469536904648131233604, 1342966569850067464072676833732319415032, 1386940582671587237306930214706894124430, 1432339632240632091248379899082611097614, 1479209423027678856383453113607484284771, 1527597110271230196535619411918797613152, 1577551345555094552118722678692831071095, 1629122323802812928405080896233059372700, 1682361831732844191885666439713321042844, 1737323297819448903117702365836079344519, 1794061843805580126375398201947639200154, 1852634337815499309899860478507267361662, 1913099449116287455841305733088417942742, 1975517704578917662675765367556644041764, 2039951546891096028927557288436529288616, 2106465394575665197878030202652145371259, 2175125703869999880639892280657434989654, 2246001032523507942326428518927297709239, 2319162105572085537803462759429625014725, 2394681883150161847602419778719559726467, 2472635630402809743358449072443186071319, 2553100989562294803702773400693689339589, 2636158054255388151037027816161873669389, 2721889446109780280629491784825760876541, 2810380393730005149431762141818549616942, 2901718814115418077642227806453268672891, 2995995396594969338861611403470025056463, 3093303689355779576538341523416349935826, 3193740188644855343048133986286705009664, 3297404430725685128482124015261788626915, 3404399086673930303539518071496429829791, 3514830060098973580266673304778996643392, 3628806587880712093900412339769336942059, 3746441344013685291423184114599846309674, 3867850546653411806696251789348725649492, 3993154068462676805601345403344093368665, 4122475550358464365212715534215704541033, 4255942518763270848709556590531206808557, 4393686506467667567059233264190721046518, 4535843177214206970598691398681393155442, 4682552454116088958508922380116464059110, 4833958652027425482926281487659998537495, 4990210613985465391664502929321231407444, 5151461851848770419720213488609692432907, 5317870691259070513788029433804837025235, 5489600421058375455741499033185830675611, 5666819447296883333857876047620789158148, 5849701451971308184172552957587846324808, 6038425556637452577526170211685244584764, 6233176491045179651330502807082187942478, 6434144766948396774449459037207062225311, 6641526857247253492405414110504646142579, 6855525380624483542973752882352905235772, 7076349291842688587959614283326036450205, 7304214077874374021969908745161495325238, 7539341960041709060651527696101277895197, 7781962102348298670972877771447721635039, 8032310826190728304516571822103978332299, 8290631831643278483009707517300449315437, 8557176425515009850550598746923105596860, 8832203756384395275761268045887911134739, 9115981056822829029420518906751002031278, 9408783893024679196645894533469693609098, 9710896422068073676869726992681349557171, 10022611657037327905415964235590286962844, 10344231740244839483869467641422351233147, 10676068224797397084451913432054621356716, 11018442364759184318198633164916612795406, 11371685414171309924821168041783574325060, 11736138935195470030731341897105630032306, 12112155115657352893032110329997086832411, 12500097096273638254129364568406589402946, 12900339307854929122821196347797972490987, 13313267818785690623766047681407204767612, 13739280693091265876089987625935823710160, 14178788359411300244946035559369069520294, 14632213991208440548035777286427451434342, 15099993898550992909236348528998831042943, 15582577931818330182691709469339276599833, 16080429897688245711161722541990847187587, 16594027987776163366091018461520561195145, 17123865220307143330671096487476035675731, 17670449895212978178213806282037242462887, 18234306063058363981123104059405301355430, 18815974008212166250641815255817815646831, 19416010746692190527511745078214920881480, 20034990539124622783171174122950587268501, 20673505419272436114177280492632996639839, 21332165738600578491452964407091846638871, 22011600727359672849983371738442115750202, 22712459072684287189096957867362594028979, 23435409514216580549216768681043186492756, 24181141457781313033736709060684924399239, 24950365607653837105078820432150561913525, 25743814617978776217655279444067399027515, 26562243763913658848429735755295006551544, 27406431633088824925252542701175780449187, 28277180837992471708487055437712717352045, 29175318749907771935533688998238154899664, 30101698255047593493719018353250087892190, 31057198533551492479846827282772286526891, 32042725862029356114154254991939546568633, 33059214440356354939298084308255484473810, 34107627243444741858284340855851896810567, 35188956898739526139519661395680836241055, 36304226590207171330300936250672373177024, 37454490989609235371507738658545825445401, 38640837215876307921509562807791125952504, 39864385823421723342917322382785035095027, 41126291820259357904788932324436437797954, 42427745716815377000543767429142076613515, 43769974606350103661980441224565064256397, 45154243277933255051577181595961302673080, 46581855362943661250302574812481036293008, 48054154516093263478312214529343471041692, 49572525632004710501334374104559020188878, 51138396098402256673541054384635418234271, 52753237087006937831814272022904434024838, 54418564883259187786203275963851474098278, 56135942256025184883033675780848826845174, 57906979868477312243893664815333877800630, 59733337731374204777631081471702309003763, 61616726700001969696468737455137310898946, 63558910016075334637815377981815199417217, 65561704895935729043665912886512289642903, 67626984166422671493841473621547747890061, 69756677949835350437494776996882059609025, 71952775399442981349947854455835475358842, 74217326487045433836701325150566999246091, 76552443844129782664764169360591425415822, 78960304658213883176078895428261326581766, 81443152626014841111157818562607933339294, 84003299965128377684316640189885118056324, 86643129485954622034977750341592268435896, 89365096725656835281826697229948006980754, 92171732145992024828625219556511601293352, 95065643396906386996372681495200070409366, 98049517647844064387444182690661989722141, 101126123988774866775964711128543473621452, 104298315903005427204355863100123357131699, 107569033813898796111168829263890269121390, 110941307707689764842787967364432959922640, 114418259834647306332944079659796014677351, 118003107490901477028952044152573917598483, 121699165883319993740699402548587906985277, 125509851079889536946534334934079414850526, 129438683048128694731495030850946679101923, 133489288784133407087171903759440897228168, 137665405534931858550862408244356577093167, 141970884116904059585528307576933690738054, 146409692333101916929278382684538772852431, 150985918492388485397522905573328951615631, 155703775033400385173016327493921142804467, 160567602256425128237568670506014500638817, 165581872166375396005001684609744850933786, 170751192430135220135330874776205357150643, 176080310451648614735683265259541625131917, 181574117568219567595606191968037458694350, 187237653371593499855336608782839599108410, 193076110157494428899202448817240492657638, 199094837507399201941346305650586135104432, 205299347006440393735491298010890871105720, 211695317101442869538561671363388208207343, 218288598103215694837832769896310130186026, 225085217337341119935617328507479613638110, 232091384447825876443532607366609664204739, 239313496858107092960202147890843709079136, 246758145394035870378822272622492886759334, 254432120073596057956765705656077274905098, 262342416068254146996486838016806825735601, 270496239840978560292288607184620181431739, 278901015466113076071437143396418763158433, 287564391136439801892208252144808498914352, 296494245862922127048053369179796424991920, 305698696372777555051762412300895307355800, 315186104211694377809824067800745695876274, 324965083056174930804295304795170843128109, 335044506242161798322194627006540097615630, 345433514516281957644296467784594488150796, 356141524016227603154218875620684608178645, 367178234486981421586174587862744138084066, 378553637739788548241914240690558759965888, 390278026360977475350350904235883849145372, 402362002677937966540986661392100920835870, 414816487989775718847618771657086786320590, 427652732070381273538574378304681258183494, 440882322951874681892466154811921800464703, 454517196996617859166024564943359945836827, 468569649266223591783489820909701213431515, 483052344196233986693359896938961741118235, 497978326585391960636465784540867721389802, 513361032908687358914858737645900418452312, 529214302963624671877291375233595346480734, 545552391859432292200311960663658841634539, 562389982359214042482435678117269316557283, 579742197585332522066279842749829922238702, 597624614098610901957524369019806359916905, 616053275362245371203982435277301047619983, 635044705601634747680848839631023982004707, 654615924071657058193414954074072630378031, 674784459743255421384045155110038952844616, 695568366421537593469936862920419503687257, 716986238307945330020214637410513534841684, 739057226019411553010514735620155800936205, 761801053077795475211959225929099083341131, 785238032883268615471514492509607846986366, 809389086185718338685779482314718194478514, 834275759068640481721561995549041125198748, 859920241460409098286203019221498426049138, 886345386188239697760169810619495821214146, 913574728590602900351246792146986020166307, 941632506704298528058841351199475312189343, 970543682042866151921114995677278647051064, 1000333960983487384823225924581400908415224, 1031029816780028119906134208995063100349128, 1062658512220375851915276276781770664218055, 1095248122946748577988257684774235713620101, 1128827561458187961756718076825868579878199, 1163426601815000877926107409911247312671830, 1199075905065480563048101312186340462889834, 1235807045415821823339310647360694770976398, 1273652537164744545758602558478951360199679, 1312645862424956590411986075938008740269139, 1352821499654221489982197712488386716918466, 1394214953019448737907795174081020025344597, 1436862782617895317814287029484889852045770, 1480802635580257032679690476964336815048937, 1526073278081137668341210705222887430467303, 1572714628283113622050872264620245251593966, 1620767790241361907998596159942712275396795, 1670275088796590998896434046441232922226854, 1721280105484807372867707872023531641028787, 1773827715493266521620553303605539321191325, 1827964125692796169875209286436391463553324, 1883736913777542205454220450627627623259317, 1941195068544074990540045428979016191639996, 2000389031342706002066542299793470385460486, 2061370738734802836764995854566155303984553, 2124193666390855237295126848177651304771906, 2188912874265036693494950830717381377028748, 2255585053083026111045491605488788770723642, 2324268572180902803925801089505241532372552, 2395023528734006463865393777009618587865097, 2467911798415762618894099450970214743830291, 2542997087527614266341531131155488309496563, 2620344986642372729167756639129596232676117, 2700023025804506238499890103635894089061265, 2782100731332124214826958614641030125525703, 2866649684266689656207103547176805808440159, 2953743580517802421127563114076865977101494, 3043458292751743520432874651720063107204341, 3135871934073855838888529023956107673712656, 3231064923556261052910373332504935862797269, 3329120053663876986526898261070055923719636, 3430122559633205372646625087287937211822652, 3534160190859908112027331948036509871665786, 3641323284352781830643904592555281862394088, 3751704840313377042758262146206083252003804, 3865400599902190780808951173413769647996364, 3982509125254091437648230938615612208665896, 4103131881807413100481036594320324769150680, 4227373323012985194323423711608184825342596, 4355340977491243188514068153816831306895351, 4487145538707498883814621981695998192364169, 4622900957237435860424466344971232268204925, 4762724535696938539859365522259172192904979, 4906737026412463548801840841684873231780860, 5055062731910321266214119225872816963618338, 5207829608305455225661590517932499593346072, 5365169371672589117533265179651465213065049, 5527217607484957221664058373483343723457242, 5694113883208245978415885137066068212123749, 5866001864139853903170598890375497722568181, 6043029432586126043327997947804537261632986, 6225348810472839597848358451250756664355121, 6413116685486911149761987232778609385930658, 6606494340850065239034236380227641058150882, 6805647788828050819868979358323999932124240, 7010747908081918653627592069900003331313885, 7221970584970881095795482028016800180820721, 7439496858919368313305215988334362724771990, 7663513071964074049835939108652486902110027, 7894211022600052038312153153213944478502286, 8131788124048283504368802122476259666266295, 8376447567070589442260008009490542419035162, 8628398487461311075206252460332652862255740, 8887856138348830806441624164049446644850259, 9155042067443756769419570588999753348369075, 9430184299374449615171525434346929913380052, 9713517523254533328367646730292257128468580, 10005283285631105617251911693555313988951766, 10305730188966550833887158622225882793870924, 10615114095811162591357578955035756794792317, 10933698338828207481051879591623783495776717, 11261753936837608871545727424765479332663030, 11599559817049104097308327355988372276048642, 11947403043660532920062240162109982732038936, 12305579053001853563436039878064111396987556, 12674391895410558576190022945518383739880457, 13054154484029380065367934740521575035737492, 13445188850722536356548468579355836503711052, 13847826409312283888776199274753856796140269, 14262408226343203250985371145381259866780148, 14689285299587470941399899516935780651704730, 15128818844510353023514200659979474735307053, 15581380588921307822374775037453775778161261, 16047353076042406735268558256873995945513104, 16527129976232279828881942708844776384464289, 17021116407610470996229825460422687493186469, 17529729265833951018746497935845078659890151, 18053397563284591024896658648428572235865795, 18592562777933648798617019961060449405909563, 19147679212156771553800491680991098027580653, 19719214361780676686556748847336177859301463, 20307649295650542327464338407254381339975427, 20913479046015228078542293790419905560761109, 21537213010035759130193615737267088448395988, 22179375362731050171081952056678531837889796, 22840505481683625455563830127361075327371679, 23521158383837114577790556963222227106000454, 24221905174726576594546126895660998853438296, 24943333510492234997442188730027525898780317, 25686048073036999702793467468390786400124671, 26450671058698216939314139092285245295973631, 27237842680814431101251934813725928051352031, 28048221686578571931124162969964326092879283, 28882485888579903642551832555531326354473378, 29741332711448297843395776670122397861883486, 30625479754025927644678434167180990258864646, 31535665367503334638305708045172921411192557, 32472649249969002223583442636051886869991257, 33437213057834087022865114174942368814910252, 34430161034606824057360675774071124844324749, 35452320657504340411776429386623070217701549, 36504543302403196013949362207515330097647793, 37587704927643928869086720565780879321511877, 38702706777219225863983333932863348093272056, 39850476103890079618538830159833487410474911, 41031966912789437618869032001059848756084848, 42248160726088413119739466638144552323713487, 43500067369316119455836884732425450126947387, 44788725779940622161938557132353149517286403, 46115204838835388698521382300086700967297095, 47480604225272965964225446909163940530854245, 48886055296105443836288374939754912569146850, 50332721989809581743968458842609321908902282, 51821801756093298129565443975439366054876444, 53354526511779563329962057216972758755120795, 54932163623703609032906044555449817428152758, 56556016919379786521948984121697568905387876, 58227427726215386308830422339091993158663088, 59947775940070288750745505735874752333374707, 61718481123983464563536630863824661110113796, 63541003637910101895183114954840145149292684, 65416845800336519376734175109252150860580603, 67347553082664049326295825379342980093338072, 69334715337277759510580422669502260806303661, 71379968060241243503324661931781060749324186, 73484993689584767139344382479620231631183677, 75651522940180830762091099949674803438719295, 77881336176228713325723232474376057863740692, 80176264822397824887364220834077902488566333, 82538192814708729095848887627141354879711412, 84969058092260527985637712495417502527185280, 87470854130943949320510443975971946835138265, 90045631520310964084053249990010937444894325, 92695499584804111262350055974260737744844448, 95422628050581942200702573081762530097483506, 98229248759211141561480162743174860460818780, 101117657429530960930753745861664678146900761, 104090215469031639746372716613046079631949469, 107149351836125512459179342432451074387037948, 110297564954727537400216830254362020974452590, 113537424682601059135272019175625182351771821, 116871574334964760305280235070093485320251361, 120302732764897999994146845039030344917099694, 123833696502124103227405361570266404624249712, 127467341951794690775316299821751262820881739, 131206627654942851319650237363078640543654792, 135054596612318891391008027499470425580432487, 139014378673369585301307698714750696823099888, 143089192992170321476772911494889854353801084, 147282350552169337941209810862656202790787526, 151597256761654393940535419677042768604712910, 156037414121904773527302487822155138327467728, 160606424970045498010525842428806297123858552, 165307994298676076201980378700802929059254471, 170145932654403084070932109870040756168710712, 175124159117464379533146881818886304115161176, 180246704364692865515871516928175716173839969, 185517713818129458146794756789700737802672595, 190941450881658341049550188940772428156908867, 196522300268102736608633731882221903643157365, 202264771419286347221163140155395229044373926, 208173502021634361753239493581781000379902438, 214253261619958533712261273633312568534432854, 220508955332143368390591600698387426550353823, 226945627667524958132062352835746248064637032, 233568466451830531002429379443766529871241848, 240382806861625383006018171677560819894185695, 247394135571294603535256144602606866240405218, 254608095015669935411733325612529295818289145, 262030487771497293652789926334662608772703764, 269667281061027961524554376702089852893750024, 277524611381106350682779059931465398510289289, 285608789261219518075063188379075841701045142, 293926304154068441300563223938797391628021832, 302483829462318433559528236497029583024925005, 311288227705286098229483859533153862573065659, 320346555829422952370468512825476501720279146, 329666070666561360868064260343000838882005942, 339254234543996793186306018801880125891768132, 349118721050591719526787469215748980389969031, 359267420963200781319340509141723359392139708, 369708448337834283241288717642941671464293868, 380450146770097643363182274556695361095570047, 391501095829568289741422903357728378777292941, 402870117672898693278270594359324766532538649, 414566283840564867726663901314692596917724884, 426598922242313840494799852942560578757434467, 438977624336501397014428660715295722645259985, 451712252508652923999834250380300716164026723, 464812947654725522641673841317054538579675578, 478290136974698833996875010300762426852994254, 492154541982275320613296817419063021480897005, 506417186736628188612904384946629177037385896, 521089406302296823756465721686332489363901014, 536182855443495667067702889308553286989842029, 551709517559272987058732033726414836044686330, 567681713866131136215790299044381782863326237, 584112112834899732091089551822696678257870194, 601013739888837904274979492259791417839597310, 618399987370131427205120722214822202847265786, 636284624782145348147246779724001081380195366, 654681809314992756214978035210013805953036282, 673606096662185762054420590231604111296001465, 693072452136345712578743276113416150752087187, 713096262092166298476936146006078235148869758, 733693345665045675620103221811925839589137272, 754879966834032170432994681991340025646287799, 776672846817962733382493486664108976957797819, 799089176813914207769909350804312788545560063, 822146631087334861139118855960812993137861856, 845863380423477656407478640401062182049753410, 870258105950017596427655710881608384191819132, 895350013341003340908903434433902590340243612, 921158847412568355077259409777167008634536574, 947704907121109296671108703260237415752302351, 975009060974929378439831181825181614138429453, 1003092762870642259012048761577536344900501189, 1031978068365937822919977630423924788381164679, 1061687651400625223260725491897381989044758504, 1092244821478190996099333866524979808922587177, 1123673541320441138175675857178371108868614648, 1155998445008135998570275650221373071413852719, 1189244856620875906567575462640079440481899776, 1223438809389853884094553311483480470730670802, 1258607065377459820245926747296470281365858120, 1294777135698098372511393066450966101993668751, 1331977301294970866081833870637554996763958665, 1370236634287969857600959477643960487220012138, 1409585019908244088581211398017660321799847492, 1450053179035411559300661824373034368888015949, 1491672691353829696660870245298238166197288200, 1534476019144774367164618227346257726463963584, 1578496531731834104647063662459881829494293743, 1623768530597292695477448002061084962635120407, 1670327275187752513696917505446102298619907925, 1718209009427743055484269864637107802492230487, 1767450988960564325635712949770501863347983237, 1818091509136133426500226272916439354488032841, 1870169933766135249256642280413869548769941928, 1923726724667324935152078810077909633202004255, 1978803472014391136559675897059347341946632697, 2035442925524365450538378425403285032080279082, 2093689026495155117192662938550026550230539608, 2153586940721383578124807244516386442633461623, 2215183092311347193890775715280006108661858745, 2278525198429536751789077317873916660427033454, 2343662304989829795921741192667051288127895168]