factmul.py

import sys
mod=109546051211
p1=186583
p2=587117
cstep=230

cache=((77396427480,52889689605),(5272877346,52505768915),(23312383874,100759133632),(55125656150,85763942152),(1913848581,29807394680),(93601284295,69391413771),(40110786096,21074045463),(43361950149,29474436878),(70956662966,18409314155),(36943853666,53786619913),(33315993993,1793702482),(47929330005,68131991682),(31866128503,106318227606),(68215694997,23743899505),(31903163772,84242385128),(96834936895,1161175749),(62955488598,30108810998),(20293566465,37784280449),(75446270601,88591320756),(64897605831,58098533438),(91719288672,48639872074),(62635663450,59620501391),(106813617163,86237071706),(83140494129,84665402536),(36665900390,11656845818),(98595093508,27519892469),(12247926592,88354300099),(51453321544,18201760191),(64300350020,20645051786),(101324422081,3492860383),(48027412616,31919578410),(91335926894,108270922777),(44280905361,25902303014),(53212999128,98417186823),(20262324576,86625553042),(57819103042,59325728239),(29579391148,104261998240),(31511941095,77182046858),(84754641430,93838555123),(79738290675,27132737921),(29705798264,93798808228),(95954256191,81931172878),(56844032547,65100830500),(83985245888,13199306827),(37000610566,89008396892),(48469901143,7731216237),(35189497638,70181202857),(39988743490,27193344717),(49890767221,49661928926),(69867651001,29130671967),(36451444232,47188188100),(71191264622,76773366817),(11431900400,43107476662),(8628291604,1796489220),(73593165259,49229215939),(80340391182,96465872250),(94085249037,103904459785),(81520613330,62228319620),(20181478058,37537656081),(96660739496,4035558967),(12137821722,46120025102),(53091519947,40311604082),(74008937604,98859408756),(73896213761,49468303602),(42079115983,82207116973),(99971838316,97984576810),(56638726574,97652026092),(81319761914,53975156501),(86176860892,10585003924),(108696007838,106657410056),(74285820188,45351030238),(36079507248,71330548179),(64952562059,69138200960),(44721203800,19929392876),(17570301485,72224168132),(24021850310,33799108473),(37868500296,25430071299),(54368827333,21578285321),(12183591712,4047113789),(20780850559,70591860587),(57507662742,30516535356),(10705518206,40710210407),(89898904824,25523225265),(4952202099,78483755363),(102635379077,51452923121),(37250886368,30610223462),(3384433431,97033116901),(3329887630,10237501629),(79300321104,40104149508),(84490836299,62354700741),(73791168301,25077305992),(24227270083,52404937033),(77915262457,84591669489),(39945698502,69450958727),(58501896931,58074494063),(38720017697,25983538834),(89149582666,3131813520),(47500831195,2350886253),(90087690526,21174516065),(59387849726,14242223456),(61355591679,71496117930),(33291258510,103959947218),(98880943959,105101804083),(563870758,91720534850),(102210992189,74022371591),(29175101179,101320463781),(74913332857,9626332619),(106310663912,46063310906),(41212918739,107472648348),(14759296884,20986348145),(24199487306,70109876640),(28428659568,61186795051),(24608588358,22915745924),(55103773965,60057521983),(90574513104,105135576327),(31208302503,29910461269),(92888940540,60205683297),(33825746430,20898497401),(33002103494,40354626783),(72454895557,34267756952),(108721767724,61644255092),(31850400631,47236905774),(18660798383,35719278272),(92520616721,1537489998),(42923068718,4509047281),(91457215645,41122550774),(86147909996,11565468488),(46226713050,77706863172),(19871301785,25999785341),(49386877074,25091475326),(18780879638,4356740237),(20278992307,87524112357),(7019034378,72681228417),(46694253017,30621730719),(92347067553,11098820611),(80473789541,71315805896),(61401079429,33087035908),(10105394267,11129747171),(9038146633,83673681516),(33869017666,91620086336),(81401058833,77600973237),(13331498119,84511579626),(25521962742,75265807431),(13139681523,91813342122),(63273698808,104570663250),(59547686963,72117368344),(13129018539,81954069347),(5677173866,35913683761),(3751002657,6989019741),(49484446919,75642667854),(57683520301,95259510221),(95503418438,61669958725),(75825808887,7029912038),(93848751368,79349726605),(76604263981,101301334867),(75020873958,63627909888),(25377717412,46176125057),(107842475011,38823208057),(44352073676,45513828132),(5629829219,22439077763),(56201884527,45991622070),(89100223130,19798042342),(89925564543,89527657329),(83256479309,73180879278),(36298871613,11050618684),(24778925110,95573512576),(39260319443,26582017076),(105196449030,6950071354),(64847170048,62374148880),(106811716818,41154837798),(82847727427,13486039294),(102359207116,23937766273),(12279709363,58279740961),(69992752101,42521771749),(93596678089,12477412746),(43160517128,26766146360),(24183569791,73348724628),(3647967595,75650314386),(36832020924,105103192152),(52898751984,29604103361),(82478044899,23097724262),(40368470385,34438710791),(20268493062,42236672327),(55374758632,64724313928),(6585106773,40626648513),(84242549187,75042746529),(93005245055,94757262547),(108709264735,87275903810),(47861561699,93084382292),(65090473485,33121216804),(1948372322,13830205255),(101819471195,100292711561),(98236999445,64268771734),(38645193758,87527008247),(30824976949,12169979841),(67377499347,76913929421),(12327764834,77835251570),(25042948787,23741428164),(96110224426,91029302316),(64272043960,21555831529),(72507322259,4628335800),(68189462849,95482853217),(78462276898,43800046973),(5615177260,93469735145),(73275875601,11712292876),(90453085988,102551972159),(102225391835,7876120390),(74456017715,46557004735),(91482880920,79802924855),(11203569116,59991453634),(83061835561,5366406616),(105063457935,44654898753),(50385288584,22439361426),(17351480206,41251787622),(57377280695,36152063007),(20085345362,105905967580),(13524263731,14182117987),(3359786880,53884939000),(8297761434,1611325792),(69938933561,48724022558),(107211198420,105029276971),(28963232148,107187851710),(61571757217,85360579934),(80283212092,82434341404),(65105666413,43444030293),(25125324770,38273522881),(46541199214,36543428241),(93737113791,16236424773),(100753352551,10086434520),(49752581172,28314602047),(58070996262,18885747402),(94328973271,37431813050),(71217495920,77749535115),(38178667921,50940974057),(70378332520,5446763368),(70339377270,92844385928),(1975179084,104860200466),(18691751281,20877489156),(15080029857,57643175439),(86756818001,35885119698),(108180977526,28931354120),(6618173935,21930046256),(39248110326,35020901876),(39726596400,91893308852),(68229596387,59540993415),(108992240178,13673247802),(11325797608,84005669540),(37767502561,8687310831),(87147139602,61481702894),(55355584615,80864903729),(40408254152,56002031324),(37022569371,105759942793),(19945059510,50887897561),(77623855815,2919051879),(18099691275,93437773642),(65596815060,80912150558),(29721852802,100697182750),(60676717662,93219066689),(41574261417,4607204320),(60155689517,48042066893),(29782940444,6979523859),(26835764210,56812649464),(79365396594,32990790240),(63849555490,10970073217),(52227740048,39507776411),(100716058444,55046882049),(3876947896,83123912791),(108481218200,62898420640),(43895380227,3511937332),(77580331681,3616634028),(37295004710,18533129953),(8865806417,79468318194),(26473336829,70419751334),(97757728049,90438962023),(56113949535,13312881218),(49257719604,883839614),(84984288718,6957075097),(56869465035,97095294113),(82930435588,96904510539),(25424995008,64346463170),(41240542026,51922469645),(62130013189,1671775866),(22137248957,21172696176),(61323902990,2051325478),(103126318872,42492053352),(80701724891,73402794690),(100185861327,6619647206),(70739504237,33194571281),(13661574215,41035394208),(60067272097,46277445514),(7791788448,20164944218),(81953992594,44625325211),(52072190807,18788515967),(1694567538,74618898744),(11960668537,87727262576),(80328760500,47573945391),(17234889747,18023452170),(66229073380,585930638),(70582049987,63462937075),(96022388488,90851117019),(31145641365,22623552970),(74304487203,57616926565),(66971019429,76447343223),(90066894706,18103999030),(6717750869,13888086824),(37737619750,89240049231),(17414720249,14796253789),(66987499129,77784141798),(55797361006,55183753019),(83993707610,66020241787),(67465984458,104602758899),(12452926563,73467198871),(50838560868,77549344070),(11217056890,30292213294),(20547928862,89528471958),(7975498075,45424688249),(94178017772,36670496660),(88490452111,89403463172),(100371124112,29935642319),(73218010854,17619568448),(68380272951,62438385638),(9565281632,32837905051),(53952662113,3500056394),(3773827185,88716934059),(104676074411,92121777285),(58470260909,28500735799),(11609397588,36651607985),(21574978957,34238687568),(17008046876,10048304480),(68682383287,9786160249),(108282234494,83825490973),(67656253029,55782768018),(55399387305,6227569541),(91053666463,83020357643),(23756018877,91221958039),(108970662699,59332323466),(46827471859,54589113662),(32786819861,98206797739),(11998745467,18195331630),(35340735677,7023119107),(22025684502,108756829909),(19872162047,32542617062),(18295719368,57731825983),(96019579780,98965697555),(60388552771,21076316623),(175092656,12725446732),(45787747747,61141966214),(78865773411,48762739297),(11481377945,99390090762),(91707480087,56537551638),(14494330491,65690035851),(72715369219,75136293028),(56762325650,708594332),(29045465434,30293072483),(83044449407,75407482850),(84508562449,82428853515),(54539879683,7877897049),(90362995475,101821254459),(60628781207,37435610478),(63586777660,23235598299),(59897296490,51371573855),(98766030818,7975810867),(28744089948,73469561406),(43879889145,33555447790),(92822516093,41137455349),(108155680111,48973362849),(93206701143,65833736649),(72938845259,32260968929),(66981537011,81022436624),(13517778562,12887533174),(65491226267,44062418725),(30744855683,16975780856),(3247041465,17055694773),(83043076865,7017451924),(74191619741,59534284125),(66628579777,87040455486),(49671771407,5930294391),(45844898996,39635320930),(67630365411,93450684968),(83541897695,33681796464),(2175367068,10909171176),(80359794410,45934200253),(71860300416,30529764167),(27479150718,53849675593),(71040696561,86342557224),(66691042662,29922961729),(59738630025,71877367908),(27932395653,14663617515),(14576634300,65716759669),(25552514262,27303628999),(19573816308,76361096377),(58378665265,92725822241),(39714430063,27860078320),(6082561829,13819786964),(90672233139,47844304130),(433561722,38166103915),(15329822806,12645871042),(92606239702,32064962764),(47145919400,89963267522),(31353582587,90034032256),(89970043354,2005556905),(31751804218,3747130401),(76610529217,64337904558),(44126957368,74160056175),(35301247268,31534824658),(55139043022,21831762556),(20289106128,21879957244),(5562554977,12587503024),(91310446607,367153089),(93844753084,93662032857),(102571330481,49353712072),(81578689192,93571697665),(72403065191,107612979762),(50591925655,77262056572),(89191395563,97904597912),(15632685693,90149268842),(42927229756,68162331287),(107318887558,79667645191),(12106869168,71872223111),(70897134249,43455517529),(55819133290,9335727091),(84041448575,93568266350),(29364952008,87120879595),(24427706014,19449638077),(40623513921,37976720852),(15436424706,35020871935),(28097896912,91247230152),(23030337839,100783321328),(87223979871,37854546960),(59437940797,62549430782),(10208392566,4259063079),(106702306362,26556918688),(70340934452,29277282816),(79543771481,91194027850),(89222817667,104246626321),(17270426607,15204695244),(42169247483,109275157947),(13126944546,44923923467),(46830835261,73993648722),(93502814919,97924321308),(49818113275,38948955792),(62111073751,11467113629),(92521522661,8493480000),(98254797586,42116023752),(66363502084,11739913786),(87909314648,100354292712),(64506283863,75216802756),(89337979950,34856821791),(21493446601,21349349223),(39135385694,55342695080),(48230388645,16694537893),(18073268126,80190608746),(35416554138,40270365409),(98460904514,24334802662),(8782193161,81684111149),(73741921489,95846685744),(3124914206,75699740377),(75888197651,78157350296),(108665508576,69390464970),(83495125671,101912093477),(48764848392,59595724889),(55072251656,60677846029),(18703049823,81106867557),(97258286212,20008584209),(27555192500,84377991472),(88033010903,54350638197),(33797430303,99665504915),(83238017689,7902585358),(29867832428,86063412162),(104382203876,63217267971),(10638117230,73655621923),(3011669288,41418062371),(13603889942,38604932940),(3515112891,57233152069),(17206578875,65616336841),(71817802284,24417412313),(38176456647,73829830687),(46683471190,68895267727),(318048732,41049011092),(78354290366,105249412396),(91762685367,426506394),(18698796464,67555062594),(102665451500,26413257744),(86884201589,94705971885),(86515287658,21584435905),(93970696147,73464810380),(94360147664,86901443268),(109216557349,39460487988),(62433769087,57720455084),(104819094347,102342634423),(1416622974,71997296206),(55536516391,43394335176),(87695919971,13561654584),(31028201952,65959658218),(47566471885,73150039235),(51741658177,89322962106),(40751809651,101594455166),(67545822102,13161224333),(71776327273,17123931068),(7030407176,33240449531),(91719021164,31418056523),(105988306220,64909923212),(65195197872,87886881641),(64678962299,1199953136),(87788359649,24729636018),(4589482483,30921682180),(98799284926,54884461047),(73739101143,8269506633),(3631963429,93534748240),(41796098851,36968256606),(72401409894,86823926625),(6333087845,66738715233),(27197205456,2055934002),(69543204305,91620179868),(76529226674,19102458044),(34904130132,93170026898),(108425991475,11570261575),(28219059962,54925391798),(106816612143,67224668794),(196594216,12719542758),(82738415148,79496514883),(84404673961,83639902237),(97574322816,48555309916),(80215007318,14353625580),(47326936930,50190780817),(20876771648,34292935271),(54196365398,55974589429),(69229786845,81706062023),(88215865001,85040133541),(59884165936,49735147354),(16670790375,68000223098),(99860482969,42606796520),(52547733656,7503032797),(49053096657,90303919249),(102884700671,59573794483),(36681547553,41428560930),(88564531394,54075643918),(38626124194,10042338304),(2737318545,40508534871),(94704960282,23869030137),(14284483754,90308329118),(5141459983,40762739025),(63472179251,14012271200),(101159628861,109042395404),(104480773687,33131809179),(47512430229,83987223125),(84398769187,69385916757),(32161796261,12419857576),(78564101202,54204078802),(41097468122,50250989864),(82824457408,46698524924),(107033117108,17366977009),(100473953345,98149048989),(62180762216,81706365340),(81618384649,82068752414),(47696061915,90771934755),(88187893211,56601218024),(94413081665,103776486437),(57436185987,1242485789),(86624327837,4677761152),(56342334470,2668148890),(39620618415,94094643966),(16084638241,68831225291),(45992876619,30466247785),(75883117085,92344616017),(52168674642,45183530543),(85813064191,63508847790),(6993977823,8023474909),(51428866628,108444782673),(90657859481,19280275772),(89371519746,60228873310),(66715891474,15423715068),(33681591473,39002980149),(72225350393,64658532778),(76640518323,76505173882),(80871411328,32495334200),(101686189988,102158720071),(32896399460,57492730043),(44299174994,56030225178),(97894335606,57342596477),(62815899159,20560890514),(67042690384,14860299813),(218841213,60352248695),(34444149080,44650295793),(20248480875,81893949852),(46351980862,34574405441),(106668989571,36037036970),(21762256311,48062289264),(52250512026,44162677050),(37840931485,66576239149),(68947327684,50393828492),(30212120072,56577087720),(61311041535,44446555562),(78619858460,23426811272),(3740523823,83935925620),(66672730985,107995708567),(105606155063,46713462287),(30144064003,61864425015),(96288583943,64822527734),(54732961237,98214259873),(31538973370,39574642926),(80903447199,69367149414),(108976713596,83199199884),(88342398174,61291377260),(52846795502,51341471146),(83880942494,103432216341),(48331766975,19190627620),(42287973965,40093350855),(106058655631,103605440826),(66946578650,5132156670),(105529978018,103320269933),(93007931115,35646840266),(85668880558,17387303539),(85927670805,103832948775),(85988138835,59237649214),(64648533697,51925222765),(75972203954,76021107440),(35311034609,50382344038),(8556291957,48008608912),(50916511548,14799304540),(103376279656,98965246601),(80465543537,94266982888),(19076731800,109358627490),(77043177735,34705127500),(100970098079,90765748535),(46884632057,27882781516),(33998386577,59110794058),(70135290387,101614311027),(9726378232,3410133157),(30021588413,31457920054),(30349437634,35818238396),(28754267720,14298253088),(66837929193,33479090765),(8222803905,45574937161),(98280444239,13596874679),(87627753799,31972051751),(61135612975,36993310856),(94403878208,42493007310),(58462444414,22813004917),(35177222404,21105362580),(79800856351,5334290740),(21977196261,7454229824),(57741214773,2525296481),(36388412016,5697674751),(16123717585,87249851072),(65145583415,55173038730),(17621635706,53895895835),(6681830688,6942453040),(55850490972,75450924035),(64920308155,8581792402),(36000394775,34135437885),(85376987886,16197667961),(39640709450,60931581477),(22674910577,18538034392),(7135034043,35961252186),(73358413553,108329225427),(63289908251,1709400389),(50249333413,46132922169),(21197672384,5225709955),(31599362552,29098507544),(64297390515,107254766311),(63133244214,77355813997),(9905370205,16828733311),(4369569507,75516739955),(39322347527,83470383864),(9360497050,3903453021),(80162164597,25146865633),(42337360816,60740325721),(44925965329,46553896670),(41277413527,16364121881),(103141870944,42490921339),(67214106706,78148582598),(36664347626,9266558176),(95672966498,24707462723),(49523205649,34727651721),(47337874529,58899920921),(13553335131,82597560989),(92706605629,81666201401),(86953461769,77318314304),(95674397337,70226243970),(69432620384,75217679540),(21363197884,26271077770),(41412286201,107721460280),(42296616371,8313597529),(1926162486,7423270733),(101029218565,64440737086),(78121171067,14468617877),(88720189926,59390674521),(69451754450,86245549443),(5295622119,69517357852),(103341816513,104640417658),(76656023793,96629777495),(2053328456,56789140565),(6773481406,97882695869),(72390648598,109266392608),(104908880958,31526127125),(19623823614,56253875689),(20186818572,44334088103),(97511539791,18590632184),(30367638349,48516615580),(38875777589,101210189683),(61276990229,84749295086),(102672274780,5222525376),(28413930047,9356115169),(85121000335,101744428641),(8684935184,58190518010),(52220456311,94796606167),(21377831151,67865000005),(83786125843,70440096539),(76832953971,4244196566),(75687534824,67098670836),(67726057148,18048097136),(11280214248,36581948358),(47205999984,29063048905),(79377886723,61673277408),(20631448601,2139289115),(62652502782,69954578539),(82380740033,56785477896),(19278098805,63662382907),(80027802249,21430573659),(66605618469,99066151857),(536421973,78340873849),(70768115739,70288598956),(62701887727,81140894767),(44334517821,53260569697),(68522266094,103530800196),(102591162674,48559322034),(87816171893,9703401973),(36078117083,59789350400),(68784476069,80417702929),(30337290079,48029016523),(28820113445,88994133923),(94826769508,61324749173),(81582338953,73179839894),(18937998797,70619921143),(50953242874,84015282753),(6740182946,19062699809),(109512722198,11220951328),(51083593152,44145247048),(36903213813,100077733427),(34644068841,11883777552),(5926294859,15946531921),(93884219566,80000170572),(107210167450,44756829763),(79396706270,76036607091),(77096718145,99450454831),(14750529141,19353688448),(32646792196,1582545915),(81495633025,32828482462),(12184334496,72000976421),(105636324111,15521819384),(91680971295,38019645727),(104288367820,52466153785),(34396120571,75552067301),(27404604271,75045546735),(14102956770,34871260466),(26616821117,53156087606),(47633789690,61743612552),(36640449335,56003222285),(3425421927,75647933232),(366494683,72770825732),(94664025182,84434955236),(80567070758,98631251292),(17737181143,71365394538),(32472166715,8900074068),(47352465216,7426020266),(34306506262,91917097786),(55942130720,4848536587),(96328335939,51541030093),(97320365392,18650729652),(95825597677,36763047418),(68192306676,105644730479),(82375657507,109265514855),(93086145587,40988263413),(4120192704,79791938060),(37007677252,47358715594),(69257843635,68082921000),(45161710385,44793836523),(17927263515,106569792393),(30761281055,30980887214),(64431944639,45890597333),(28870140944,82613015219),(75924248650,47352071175),(82342164750,54215119972),(82905421857,15408372683),(68779871566,84666410681),(45359338673,40668637992),(68728364069,77167393110),(7199895304,64956373930),(77139367896,61086520210),(76570800877,89235818050),(55113966215,53474200514),(100295671667,22441360335),(101271979217,78576421866),(69174055636,91381689960),(4407249156,57930088340),(51967974278,91502180226),(72178373647,53336945670),(15399790408,25024120188),(102729928112,27827321933),(47096484449,58049497674),(71186196604,57148875660),(55465624163,90451685203),(107892792754,86070355956),(60133176985,67102042620),(103151249501,58170495472),(57197086618,32462744110),(86390698013,50537442157),(17719743621,63160680581),(104169919113,42712323863),(21071934107,29642636922),(441269,17545),(362289,105613),(83821,518807),(412859,68946),(178663,237148),(416459,315548),(104151,93972),(420042,455338),(235164,202331),(353344,163891),(265388,454803),(247257,156277),(544970,185454),(364159,322824),(397888,242312),(400173,182111),(390218,428618),(125616,372161),(212440,192482),(249807,275767),(481747,153816),(175459,40496),(446758,5491),(478076,172801),(243460,160527),(162572,194547),(40722,125631),(197456,394925),(421298,310431),(324787,101855),(78262,160017),(349834,91499),(225267,310325),(238796,543821),(17702,103453),(179991,168915),(421648,582402),(166609,29359),(226953,514333),(429291,524393),(571240,492692),(190989,24624),(426189,485682),(51286,286395),(334599,235014),(302528,131315),(353131,456042),(494907,75829),(91581,553866),(584881,569890),(455671,468419),(76887,23523),(78440,173837),(118329,538066),(449961,481330),(403552,357588),(566995,4277),(61882,216682),(344552,49888),(413389,518208),(264714,102282),(359767,301949),(46265,475008),(237620,203771),(311026,64245),(255019,121140),(560519,103132),(499117,439866),(31226,561111),(243399,339219),(459451,302964),(335418,535397),(419971,435036),(93627,220615),(247365,585911),(179054,450349),(427256,478089),(551511,35410),(457749,288807),(182844,568500),(381612,466874),(239626,160309),(415551,537527),(22487,145634),(252100,448614),(251765,432836),(407992,476192),(155103,585906),(480405,132977),(187880,75884),(31175,363475),(89926,320814),(156538,195093),(282106,466737),(165710,332107),(184769,510187),(281661,331031),(576206,580080),(184638,364216),(290623,50583),(57452,459842),(161437,317940),(111697,443059),(125243,238748),(317130,314537),(148334,205753),(378887,505404),(23039,429424),(16780,58381),(360212,70541),(119139,472088),(568086,249488),(402585,326585),(45895,167080),(274769,403208),(126709,200727),(145973,174352),(94923,15683),(32287,366076),(306332,562551),(9286,64312),(344960,300002),(247978,344687),(468004,407959),(56517,19432),(143215,12597),(436197,176697),(277291,36178),(477356,472955),(320921,230154),(107635,64519),(465701,147552),(299147,428828),(235114,409059),(363483,479319),(272689,362642),(445620,144509),(457227,213168),(461720,191478),(337158,297901),(451116,541599),(223403,201124),(70347,54328),(527978,570265),(315737,348431),(164956,440902),(234643,442043),(157264,553408),(312265,461803),(424363,425899),(498525,365839),(499658,127853),(241399,445047),(313270,448707),(132291,441897),(47951,520829),(382249,174247),(494039,336838),(299316,164848),(549407,354008),(187123,430951),(156120,426306),(531562,157391),(290757,430028),(574260,30622),(208102,237994),(384970,341690),(227597,469221),(457956,179384),(169062,186770),(402098,54633),(376455,329787),(581006,460918),(338283,9689),(168942,455277),(231660,494369),(224047,543183),(507681,177588),(224217,474183),(132848,257063),(37632,309983),(12904,560513),(32057,462977),(429658,468873),(454972,44886),(83117,533792),(538241,133762),(506172,126418),(526196,350302),(573542,131961),(476300,252516),(537277,548422),(415824,323063),(326455,88605),(259275,538127),(249679,485745),(418551,558213),(358353,165392),(389711,573262),(449583,325063),(559368,84958),(268151,253267),(487929,351458),(303846,544506),(207526,512986),(547964,27642),(410152,571810),(336173,103990),(464385,545623),(358907,194661),(183656,170554),(146236,541608),(335067,441255),(526612,153430),(287588,217972),(497724,139300),(293131,146477),(544114,480779),(259615,306418),(196877,434620),(185646,302530),(274529,87230),(106322,413447),(174469,398910),(152919,345784),(216773,544787),(79763,85859),(387009,95210),(284056,137869),(150640,534837),(455498,329877),(70176,463832),(313802,405999),(485270,397987),(260680,296851),(375785,540495),(546723,267280),(415714,379608),(347781,493837),(338814,342777),(115571,95491),(473072,504813),(154421,347261),(130453,559559),(508797,105450),(505601,535592),(330583,279521),(63595,516402),(255644,140492),(301241,455805),(3540,328575),(377026,394197),(44679,69727),(26876,209141),(173480,299140),(548805,370821),(203287,471855),(433444,491147),(286763,446968),(545574,311287),(538683,327608),(74501,250564),(113816,244186),(469805,575175),(333377,12531),(309981,79231),(503996,556763),(322056,473028),(311201,460265),(228847,343245),(432532,236375),(127390,378635),(108453,521446),(366946,275279),(57986,518877),(463290,43986),(250595,396976),(277473,235413),(421537,370134),(559634,522302),(435479,528829),(324544,156997),(17630,301847),(258877,192846),(348974,410544),(256970,214639),(8256,28763),(394448,182473),(31160,549746),(381118,10675),(575803,492999),(330010,2474),(172637,112894),(161867,332159),(133773,233625),(44902,68211),(378297,357345),(92777,504480),(332248,223852),(446427,145448),(413060,193266),(113649,45894),(319741,578479),(68805,281871),(421733,364662),(225404,12429),(268531,428629),(271346,67702),(485508,1730),(403274,96259),(158859,418439),(475861,34185),(312299,192146),(518366,529916),(256986,237022),(201226,575562),(45299,331453),(207980,273572),(98117,449931),(220515,26746),(451611,55046),(542263,239406),(198233,247255),(149606,273270),(290302,199952),(431449,442774),(236804,5941),(312764,389943),(8558,571789),(147001,331706),(583087,432808),(22734,437968),(364450,476432),(514314,364732),(147954,347795),(373767,344951),(469047,82063),(63601,9765),(2375,181581),(139076,359050),(114894,327934),(127778,330252),(565691,207055),(583462,242131),(431394,274305),(43251,575593),(399988,362050),(431132,570849),(509151,125516),(252734,38886),(402855,438265),(9689,17930),(439571,268558),(307356,585750),(571728,242950),(207335,64845),(1898,142593),(201548,541210),(132385,298139),(306269,285499),(330660,454865),(150458,410026),(551015,568946),(366603,231070),(542385,211995),(97417,321268),(44433,486340),(131000,14768),(452388,151994),(204614,545534),(306055,495620),(230973,536858),(409424,442555),(160579,467024),(333709,80274),(379584,447252),(577544,449963),(508932,508245),(2256,484489),(209906,160767),(247586,438752),(512137,454375),(581022,277061),(546860,183632),(345230,566206),(345528,168581),(173437,286192),(109939,503651),(487056,398385),(406371,462301),(542005,74566),(402438,414583),(189372,70865),(219270,151203),(57236,93885),(318156,154952),(383342,450065),(21122,397015),(473116,355996),(5482,245921),(132723,289419),(459658,132039),(41090,166011),(35897,565486),(145332,358803),(453849,3614),(243684,283913),(398627,69176),(107278,408871),(565137,483884),(573585,19218),(84970,438666),(581444,564115),(261475,464383),(557109,24086),(360202,421190),(137851,158871),(62879,511257),(322455,420662),(366102,98407),(305101,150088),(138662,199358),(337608,15978),(237755,74883),(228715,398167),(78084,168794),(347248,574398),(287521,105227),(449696,363745),(304578,413317),(344294,28775),(271465,564992),(493483,390335),(35387,558808),(482904,430342),(127077,370271),(431831,6662),(469264,243637),(489809,265280),(426126,89386),(430874,128007),(197506,228864),(31345,363282),(475701,150734),(165674,84000),(476182,580110),(502958,573966),(545112,562397),(477194,390789),(305910,55350),(380925,77948),(502038,272696),(13360,369550),(141297,221774),(239563,158226),(466635,420071),(274912,6564),(487171,560065),(541569,279421),(300093,223645),(366664,139268),(65762,333182),(522412,548142),(283825,294079),(507695,485763),(89274,568859),(378949,314052),(145928,159081),(391656,12512),(582607,277538),(94420,31778),(106965,98115),(325945,15686),(325115,1126),(209287,149742),(257299,225021),(86191,56972),(243495,331769),(262873,572993),(80544,287070),(449215,370920),(133687,455218),(206426,359232),(110897,283051),(5497,178188),(91498,249132),(276017,481358),(435544,22795),(154847,140231),(532415,424378),(174657,403366),(372003,388964),(318957,224069),(32116,120122),(120365,469914),(380306,428769),(226700,273425),(387155,286613),(295785,94064),(321422,562550),(121880,410743),(485512,185311),(94465,385296),(280853,509496),(488981,501139),(583950,179890),(204765,242661),(25619,363080),(30904,374268),(519366,23109),(492522,558304),(66744,229492),(475694,574136),(11491,463162),(90324,252848),(337948,39035),(189530,127394),(60592,442849),(495388,118958),(130173,486177),(1781,182210),(6499,579273),(254738,25812),(519396,379663),(583366,371722),(263707,411585),(396849,524601),(333031,563388),(401928,259180),(434852,281433),(11555,473321),(444872,31624),(336630,219288),(156935,561897),(318926,119778),(169405,126760),(247944,47991),(257295,509447),(568384,134055),(447820,89504),(398223,499518),(149230,17587),(405687,551183),(514869,189950),(154755,186864),(239652,563791),(11246,277714),(406446,449674),(119591,392866),(374131,466718),(193458,225800),(45919,571281),(396919,519498),(321912,545729),(143511,556847),(204945,473475),(373870,489054),(79666,517599),(13522,446946),(294651,290393),(235409,565805),(505268,366541),(217896,186427),(184373,358392),(321468,124347),(29999,172346),(235230,7008),(254161,94375),(157103,148362),(8364,194579),(552009,478573),(95555,431255),(238883,145185),(444163,173370),(88155,348819),(487705,464285),(308670,75368),(367609,216293),(567595,220848),(237544,471088),(276229,206661),(99001,302646),(219367,371367),(209025,490236),(412609,323222),(335558,368248),(259358,241141),(292244,434087),(58143,64754),(235120,285632),(42629,220025),(281497,180121),(367962,325175),(492599,373761),(247179,4458),(458786,63735),(191882,355914),(450443,576156),(476650,224244),(369224,303847),(455988,130790),(156285,310104),(357883,377885),(424057,584378),(214614,154142),(222060,227075),(9445,51292),(108868,342281),(522427,169630),(235707,483135),(192565,397361),(440491,382890),(62532,295341),(128901,446479),(309722,528472),(510336,491928),(59078,429097),(33245,340023),(165534,64075),(583444,345621),(30892,547520),(50913,570062),(396793,59205),(453961,26163),(510347,61341),(383141,210975),(276216,556774),(280551,556907),(504081,557136),(402471,475752),(200547,17101),(381556,289646),(206370,303100),(10133,505721),(282957,456198),(276195,351646),(343210,520247),(203924,222204),(323566,156219),(344859,276416),(464438,408604),(431282,320491),(375078,279486),(161320,155373),(485861,202167),(308254,518435),(506146,444500),(429770,61042),(354244,98937),(275380,165334),(435405,61617),(528191,305676),(291754,357144),(562144,287893),(409847,41271),(196522,414945),(21787,408263),(510995,515474),(276830,572727),(119833,346975),(413736,177056),(34728,513526),(50811,414374),(419388,69318),(34355,360398),(264212,6430),(330928,321395),(253840,175724),(401451,214697),(440467,423815),(49018,50323),(5632,439741),(271272,425423),(81610,316604),(426173,47278),(518301,392911),(493006,345192),(413729,169465),(12359,21663),(562938,153927),(554943,209288),(440341,222852),(338538,373156),(226815,114026),(281568,293417),(227974,522295),(213100,112635),(44220,95041),(140918,35382),(40737,316376),(474479,415995),(69192,165618),(327757,263927),(310466,584247),(140504,59721),(275616,412351),(557731,221710),(239331,66423),(420228,371730),(463980,82935),(115831,159148),(528506,258668),(563728,444750),(475086,280632),(214648,319990),(95942,250392),(167720,49309),(33878,525074),(443989,574885),(481562,164340),(82495,189804),(10216,534827),(580517,93407),(133830,282886),(456104,266379),(114704,30786),(27938,384195),(586540,440769),(247198,197768),(187771,361829),(84972,115047),(190919,581124),(523613,43295),(97357,216513),(389047,532174),(408515,329453),(450114,531981),(510028,315506),(196418,74576),(197032,341684),(374556,511412),(66297,148046),(387075,224332),(33781,186568),(191198,22500),(130432,414442),(359867,551594),(468652,66472),(480787,328972),(259799,96965),(226234,326916),(44230,295547),(33240,505074),(214869,369087),(310500,500867),(257305,517053),(5451,334386),(100982,50122),(453156,320880),(362708,309455),(135791,268697),(195736,90222),(376063,210085),(194120,161827),(336197,127329),(551475,90669),(13741,277721),(148903,481423),(470442,457985),(51719,555136),(85525,247672),(177859,29063),(129769,261433),(477697,314447),(269347,569739),(350394,27111),(65203,543172),(177714,16587),(287201,350006),(295023,226765),(574068,284999),(504225,585253),(108134,366561),(344185,188678),(559798,127980),(41071,190685),(230776,553108),(199961,28200),(156557,33059),(371431,448973),(309155,41950),(399241,472032),(4553,114155),(11835,66755),(126336,478756),(566476,550503),(142757,12878),(485533,459515),(62835,428681),(409093,237213),(24676,47911),(335937,142172),(349098,17119),(583038,122181),(65952,148380),(163529,230256),(458774,328026),(115157,451442),(22287,526519),(48651,223607),(304895,209719),(480714,39834),(450421,339380),(248006,419479),(163365,754),(350390,331126),(12588,489341),(362369,356074),(458543,327965),(504117,341639),(562323,30644),(168793,384325),(417197,455603),(464712,277185),(565790,256735),(303156,383799),(49158,315399),(442451,190118),(71206,190022),(362283,220449),(108087,261043),(76871,267411),(458808,39467),(160046,402853),(241145,204572),(173505,354104),(350704,432787),(445104,202932),(549700,26560),(352599,309912),(345612,124457),(581234,194305),(570691,37235),(379666,90962),(560899,42256),(431305,363027),(188502,229316),(438571,385703),(237866,24607),(353316,371896),(552655,559984),(13862,74704),(408436,210940),(159446,4655),(564302,121001),(533498,43694),(517150,117934),(440870,135342),(137021,184257),(62863,2337),(108356,117399),(316267,405701),(342800,66345),(14002,526610),(26443,580682),(434669,317495),(405629,401691),(69439,527247),(144405,206651),(362390,366222),(394424,339472),(245404,551255),(438015,321018),(309351,250985),(117928,324653),(497197,351394),(349322,346786),(471702,576141),(177597,221926),(260891,493248),(20701,355520),(144271,7),(460505,269879),(423561,100571),(446995,549736),(564646,172763),(376912,564299),(370734,186253),(540999,333114),(527521,201718),(4749,252449),(260750,15495),(552157,14077),(331515,134795),(473862,542342),(210648,574870),(55865,280580),(398119,223704),(116592,251603),(473148,52968),(84062,219405),(438522,472320),(93703,170540),(381791,29837),(312420,468836),(405465,41754),(401986,441325),(571140,497790),(379650,284044),(480474,396684),(562070,509740),(17466,169221),(158484,331983),(140607,296964),(177091,36849),(478742,152753),(353867,456953),(58753,367759),(406527,579601),(575733,222461),(553626,21759),(485059,558307),(415366,410309),(449621,304060),(185269,551966),(352982,430797),(166374,399729),(392365,224669),(464939,559935),(355055,398925),(155386,462696),(287943,528505),(49018,228321),(400130,487492),(135583,261124),(86499,420397),(327473,489306),(89450,562742),(523610,47862),(488991,177835),(16766,537312),(100725,32330),(239223,79972),(202189,255910),(180278,187745),(22703,538832),(584546,460870),(444983,128687),(424229,438238),(353624,457621),(165100,398321),(537635,248744),(204856,52570),(319436,70418),(421623,328190),(59434,476596),(447837,101728),(115241,381641),(341187,34212),(95398,27415),(108044,204103),(547938,364396),(564100,172799),(23938,160882),(4503,489190),(267337,92271),(306559,334957),(110352,493926),(533967,349209),(67835,198613),(398680,93895),(7496,380708),(493914,148734),(577988,37062),(279395,50036),(164748,489177),(514392,377684),(275798,358671),(88341,531238),(542514,553518),(339973,146745),(106753,384994),(93913,503875),(500893,375680),(395212,440169),(573368,527578),(506324,150830),(91422,28027),(421178,152042),(408627,236866),(294666,207559),(198971,268973),(89691,38773),(164643,380638),(505851,15082),(150332,55503),(334656,452580),(349960,567319),(512569,466424),(174978,443821),(550802,84938),(310423,394646),(388171,355242),(224323,301841),(321846,319706),(124554,20922),(66702,508811),(160830,73020),(274859,579034),(38041,261106),(477526,332506),(393361,106024),(284906,521279),(9691,399745),(567297,350318),(550777,462987),(580301,168273),(571213,268399),(120322,344515),(454111,5418),(257426,123029),(453253,274596),(32550,181143),(141367,201987),(98626,461890),(382072,422486),(328879,134893),(361912,248443),(371505,401154),(32068,158215),(17633,402824),(564481,490316),(548765,389515),(486589,416051),(170841,411740),(429238,395641),(381929,326734),(373643,62438),(16816,557462),(221291,505608),(427010,362506),(121408,48784),(297580,147663),(373585,38835),(391208,441375),(129087,532825),(512729,40892),(422742,122383),(204809,512558),(325882,227961),(290488,514749),(381452,552226),(336762,164562),(561233,253592),(342368,71906),(410141,190254),(493132,272692),(463937,506635),(373959,322220),(279479,218793),(52347,108225),(224524,334664),(149581,436912),(459524,446637),(197142,357409),(156727,572765),(268530,466806),(489584,386895),(118133,344470),(186247,496521),(484553,458962),(129486,304613),(314789,476844),(355921,280590),(142061,393245),(469228,448448),(45358,459067),(2682,336575),(565967,394033),(447120,286164),(210551,24758),(63260,444850),(259369,140277),(141947,463663),(396205,56213),(90692,376187),(540505,133205),(550589,371943),(200193,431939),(186976,206948),(512356,365228),(490430,281944),(449455,103214),(444805,444853),(430661,422300),(14003,361800),(53712,144702),(60378,385215),(418813,173586),(105999,334560),(5252,343389),(1977,436860),(343402,217917),(104607,558657),(29672,193987),(2779,13008),(250375,123911),(46360,24897),(285153,584861),(95640,411166),(117450,501111),(79626,114221),(296579,523486),(373016,73811),(55612,346387),(306168,101445),(398481,20239),(154984,522761),(107009,419403),(273913,297579),(416644,309482),(164880,190984),(158346,144119),(99583,435371),(538097,329034),(235194,241389),(504012,486064),(113499,393627),(377603,233929),(126822,58623),(198943,84848),(411946,514400),(459560,34122),(350605,80426),(256356,473139),(578191,435961),(111630,353275),(371109,381578),(441129,373427),(62368,553874),(35536,359688),(88004,263077),(373319,442600),(132464,5130),(525248,428757),(354866,416647),(55489,276538),(494584,185163),(58939,110879),(237345,458895),(544580,133960),(98240,286673),(586773,554072),(340864,386674),(495578,173466),(323752,516615),(474914,16959),(479152,72690),(185806,263913),(57654,577482),(1404,94809),(300780,58874),(196918,288529),(486535,248679),(558959,512994),(315703,4515),(557658,216664),(225456,544064),(555131,245051),(529717,302128),(376264,86499),(124118,362898),(372762,271962),(105035,561706),(293906,413537),(175229,99803),(294124,76998),(463893,277086),(314267,82185),(147561,489080),(505673,153923),(380146,223785),(53334,175037),(248480,33406),(106890,141717),(260697,214826),(444740,453777),(333596,251887),(538811,107609),(58479,263176),(536442,262931),(468436,533218),(510860,411403),(363218,450017),(75012,443042),(203397,213899),(199355,223460),(567754,36473),(85787,354264),(136375,214811),(235679,393165),(409697,239163),(18023,500814),(108235,82269),(303801,452874),(403221,121895),(522050,381910),(148582,306582),(235145,400497),(54529,466990),(140722,123188),(57336,513352),(485912,524824),(251141,524390),(115689,566769),(181599,79175),(565040,496019),(274517,194855),(318647,262253),(395603,348762),(144163,157376),(133490,260532),(381863,485253),(316389,240163),(442348,279206),(126136,426244),(298829,331829),(318699,265236),(375068,7615),(241280,8707),(268410,359362),(326357,408808),(543314,150087),(44113,327122),(159176,456596),(527317,550844),(353274,368661),(223842,560535),(422010,225470),(550443,280181),(492657,67782),(342773,314472),(255846,510997),(477919,244053),(411235,137621),(37268,9734),(104264,424100),(372651,103506),(44837,170908),(169095,106711),(87236,67445),(283170,350485),(312016,181300),(239657,341499),(325511,52313),(373440,500033),(276427,234594),(457655,255269),(410625,449410),(103822,6293),(174208,497586),(300905,188334),(228921,101544),(216518,25924),(104419,468183),(151642,173962),(328041,531687),(544160,341948),(331525,14746),(127168,136824),(579345,465786),(123755,477521),(221843,438517),(196823,502018),(161265,437943),(247952,522031),(15187,258961),(308113,196293),(463670,160219),(505984,227658),(42807,40637),(539874,181257),(526289,379477),(273196,201480),(529875,108725),(577298,249362),(108539,45814),(134904,213863),(169811,172931),(372992,78178),(296338,376064),(161654,551916),(32779,245527),(517826,561981),(493108,579345),(16102,492743),(238216,155447),(436558,421072),(294581,49149),(255665,226499),(157864,203225),(498309,421161),(326616,183844),(246520,547197),(174089,216929),(136917,245417),(436783,164669),(339120,246994),(571790,94197),(203267,585390),(220359,550282),(429210,523801),(399219,456246),(93417,139543),(587078,509988),(99397,162328),(207228,179772),(138362,238652),(330243,227990),(435551,78553),(423575,182220),(151650,388383),(271358,370150),(180069,206251),(567734,210522),(287469,180851),(401934,152793),(345898,389103),(352548,190755),(41262,580189),(192897,351579),(426479,224334),(203974,395342),(3815,451335),(71847,437804),(478056,456602),(32558,389825),(214732,281748),(439249,116667),(227749,407448),(460178,533333),(582963,250941),(355270,443542),(188979,209516),(524797,31042),(367714,421233),(174403,338918),(274073,181310),(471623,238269),(360118,184578),(385529,61735),(460122,406101),(355916,50923),(522599,10485),(252767,238588),(459150,94333),(24600,351806),(42025,201146),(102785,78394),(164431,358285),(527789,258019),(453921,101034),(290446,290714),(248812,254127),(335938,430775),(317294,522914),(154171,451373),(265408,322200),(471514,199686),(67183,97412),(543723,486562),(224688,499086),(262023,454865),(321013,9809),(515029,365236),(28408,29897),(172756,440537),(233243,530899),(210156,67430),(145763,559260),(478258,197637),(368299,580429),(501391,449938),(338375,529755),(580890,203675),(324586,274656),(386152,23313),(397379,350677),(149134,282416),(370948,319321),(121542,70532),(479516,167319),(444429,95187),(33583,281352),(123950,450502),(130962,148015),(17888,159951),(151671,90052),(365099,345974),(61236,297250),(66193,380017),(334018,50888),(65857,527712),(446336,439357),(215490,584250),(48077,223511),(44439,484152),(101482,380958),(147526,183210),(496805,234051),(191372,148932),(507052,120069),(340950,329563),(191613,216956),(50184,515652),(121937,299498),(81238,400073),(568310,216153),(584730,412082),(427626,71670),(257847,548959),(132744,329000),(354797,345180),(230002,353820),(96708,121038),(301957,24740),(128440,23250),(561476,543552),(157777,231972),(382157,203843),(360334,399691),(322058,225765),(46872,352251),(93299,190269),(110216,441440),(326301,246487),(108122,337536),(266114,278046),(252449,94268),(265682,127297),(157137,189049),(284794,15154),(331856,532967),(518419,118284),(117759,429463),(112077,514547),(542226,489444),(130668,355373),(528114,152978),(131130,437447),(382563,542873),(486876,402350),(482951,524906),(515647,557482),(376857,14418),(311995,439298),(502966,62223),(8341,202864),(587050,111219),(100920,455948),(302681,9049),(286358,144943),(259628,275603),(516860,11909),(207385,333644),(198155,342426),(8261,62709),(561048,435089),(370719,340869),(318746,252494),(557221,25975),(124896,372625),(366700,344099),(172194,549959),(265796,266048),(135863,208881),(485442,107323),(437743,390404),(384110,347026),(491153,535335),(524460,127511),(161587,384971),(398605,222678),(49637,69094),(51779,346212),(177798,156086),(417472,548878),(155866,286217),(138438,460061),(399922,497491),(361031,352660),(575771,390881),(358324,12967),(513161,452922),(148785,332290),(367209,522434),(237847,298590),(267287,431479),(151721,569964),(26205,306907),(379596,156916),(214191,32100),(260911,142334),(76180,478447),(78649,120203),(236552,331877),(262213,463354),(16587,271433),(477627,165072),(69269,77489),(351092,21092),(547364,52938),(19926,37295),(241069,90207),(419750,521250),(188777,288971),(364959,42886),(108237,246843),(477994,336059),(191275,548300),(265616,370047),(62311,354730),(34751,435920),(13507,15243),(401604,545679),(491552,539309),(527681,457245),(492251,299889),(363507,199410),(151380,177876),(390668,45008),(165625,326728),(358938,416224),(275035,135344),(516852,58327),(581435,266741),(291765,501989),(288275,468724),(185125,154083),(476179,579606),(404052,386321),(230953,81702),(175357,182266),(301937,152587),(265088,437937),(254980,295953),(6739,286389),(78677,284344),(461069,41248),(154869,405601),(47828,125601),(58251,50120),(69134,156528),(101456,550268),(42103,59318),(445059,210235),(42936,46494),(135845,268267),(225002,297662),(537885,462962),(298369,548124),(449179,104615),(206638,44240),(208776,575428),(541393,103268),(480725,68620),(363261,434839),(503277,75592),(363326,291473),(528991,241720),(196990,427856),(500860,227628),(133640,404338),(121789,334439),(502706,241564),(341591,388973),(538258,498039),(350059,146061),(498593,441414),(497003,291874),(91740,122536),(113906,409160),(154289,150751),(526925,275658),(475611,440650),(538352,509182),(284186,549399),(429709,306242),(217590,137897),(489650,517206),(293796,162443),(471033,5857),(29727,467279),(28295,130612),(480854,365038),(224981,269173),(217240,257285),(354258,508294),(260503,276268),(254380,290966),(462019,38646),(48808,15460),(554448,379753),(148435,43252),(330188,579397),(219421,249960),(51578,357018),(134633,510216),(12926,584307),(71040,322633),(536538,48906),(565938,36320),(127185,418533),(456870,299860),(143017,483412),(345729,102609),(442577,433002),(536405,310856),(410051,178016),(500965,148005),(144118,460094),(432481,14652),(8159,73569),(37171,476386),(42103,448542),(477485,404501),(22182,555956),(59371,435127),(194836,210825),(109586,209315),(249113,66796),(53746,278474),(20804,14817),(220066,107640),(214280,426453),(515528,322169),(91814,84985),(272233,97710),(32405,310041),(247602,489272),(316102,380246),(423313,21690),(30760,582002),(98954,311046),(385757,103998),(55016,272787),(128811,571999),(233540,257029),(400656,57767),(41015,424060),(326817,82523),(259659,293736),(281405,239048),(284408,171564),(187734,487849),(545394,238886),(409236,322623),(63004,99526),(387842,271159),(93732,548609),(513899,279834),(172793,246604),(342971,383358),(274862,378956),(238458,245427),(7204,335421),(528193,27582),(431085,447849),(288297,381182),(447180,412993),(162652,453199),(441871,116322),(508727,37360),(539119,406692),(300866,187482),(65831,240117),(411917,441374),(374701,577725),(336914,345711),(547527,64647),(75802,220670),(234012,493317),(533979,480960),(448107,48303),(453451,173603),(86049,524293),(242656,425914),(275103,222309),(44639,478902),(447776,423331),(362367,335582),(231826,60177),(342046,534463),(369773,217260),(124972,134772),(477943,6982),(275791,5471),(120517,236442),(526946,526795),(84350,418769),(349997,310809),(463987,154399),(381392,509017),(161333,204354),(72998,115054),(529702,453622),(55313,531786),(71994,462126),(437207,322768),(465771,168222),(62112,357257),(209056,385004),(323401,4329),(278220,72368),(76048,410134),(249043,539083),(558179,304416),(386177,34468),(514780,69983),(457127,247563),(161491,275739),(412264,487310),(41128,470988),(171400,112325),(157378,53648),(416941,423661),(121019,279538),(186834,48275),(578121,207398),(219284,8165),(100311,438512),(63789,517074),(393528,71398),(216715,386246),(390791,319446),(236032,367277),(402713,77424),(379269,166417),(533308,508314),(12741,512121),(128115,305060),(497005,218403),(480084,503055),(46742,57980),(422136,382520),(218802,143184),(39955,126104),(277240,447498),(250710,91836),(532412,193301),(509408,544112))

def fpl5(f,r,s,b,m):
 for i in range(s+1,b+1):
  f=f*i%m;r=r*f%m
 return r

a=int(sys.stdin.read())
if a>=p2:
 print 0
else:
 if a>=230:
  f,r=cache[a/cstep-1]
  s = a-a%cstep
  if s>=p1:
   f=f*p1;r=r*p1
 else:
  f,r,s=1,1,1
 print "%d" % fpl5(f,r,s,a,mod)