#include<iostream>
using namespace std;
long memo[1000][3]={
{150350626,490189494,111597035},
{926330576,877218207,585551355},
{16515145,792336636,693968458},
{331585876,865390300,790531852},
{980450965,364822946,952454297},
{365676891,34721793,126002492},
{113026459,211176624,79083008},
{484830470,489276259,895595767},
{304668658,560674156,493887548},
{36891058,908460138,964927951},
{873443045,663959822,770193592},
{576084400,351309356,898166436},
{812180643,34728542,995574830},
{556522235,946297609,180149291},
{711518700,646371660,947284727},
{940293115,845895238,397265537},
{263811271,490220918,305633059},
{523583821,981951309,300449903},
{621726030,384152217,912251114},
{708713046,371975563,946533617},
{105544191,71343585,994178311},
{662925986,396013987,765917092},
{834667204,341094152,871872879},
{349454264,47125963,973309033},
{778512760,431043837,989939305},
{867434972,370146386,838068347},
{530732350,872482683,247807883},
{412139028,829535814,571695187},
{498203958,303189210,804500967},
{832459368,967988087,509786860},
{465313735,584343994,403301331},
{589650681,132225666,83568042},
{245739450,306710464,273604920},
{982007641,848719223,662895182},
{85825486,417590676,927352261},
{191194848,103684887,788042948},
{821751484,636741114,110498807},
{466762743,31497600,869818772},
{610416484,550090373,367502146},
{555285113,392460984,207105907},
{578658843,688807392,667128385},
{260890325,903333739,405115213},
{740423420,34803879,923026409},
{639622813,729987547,43597420},
{450662765,541353446,553493376},
{270674828,29563180,211213510},
{691159425,779310126,47310805},
{146085099,573486682,257866832},
{427672972,793777511,418568394},
{355333862,864787550,200000007},
{801356260,969567541,14731780},
{491339383,566334113,7793009},
{638523089,10891922,595927503},
{171081025,689319466,850622192},
{903026782,869935040,743511666},
{103509707,251655405,476575827},
{911390571,732223594,621157576},
{446373718,192043699,408477196},
{441193184,571286786,901761459},
{534952325,4660654,371423623},
{990869393,521818629,219320350},
{397698864,872935933,257181253},
{39688715,905978774,298595824},
{796706474,540377917,4077436},
{114446478,418078,343507214},
{932183508,478613700,943961538},
{775783362,588684121,240255098},
{679465412,878336833,735664525},
{40413676,639284028,993832538},
{457037277,393241336,407794103},
{385659116,770716118,61162437},
{362803698,859137012,81857139},
{968553004,809790292,863486550},
{149160072,801111326,382741530},
{823155482,4258201,747701232},
{526627164,940822230,610965613},
{861137040,125212249,910719884},
{679747506,385921075,494396848},
{487600387,642109873,497610238},
{445100786,530142919,885945115},
{732943346,117421826,564084062},
{190828595,381604439,275537031},
{68266548,207547749,83655001},
{505796553,506593171,978886792},
{257923320,918528888,835147394},
{31876012,861085340,11368212},
{475788538,236563805,581127662},
{91116093,42290336,667477530},
{785146729,916937613,753219652},
{780396802,662356693,73070046},
{804187342,460962947,533029876},
{605570083,816832494,309884586},
{542386186,553560792,884973672},
{657287196,859755617,576228131},
{599405538,993450205,341817344},
{129614129,386573344,171709500},
{859970405,286263480,517145514},
{257759591,278360791,560097918},
{927656777,823805809,492906780},
{999999973,21,999999734},
{182058055,784899752,596009305},
{926342861,49105349,448177222},
{77554314,46441847,697439097},
{899276474,713229531,630225404},
{325949238,846771862,502497646},
{296143443,227831353,874933793},
{591809498,628259534,126511116},
{790565508,820848482,305976154},
{415422897,109277797,523324173},
{823366807,964730508,978161894},
{246092844,710826196,321750028},
{790626967,530750723,414314757},
{115157709,604322345,370421540},
{950493799,385098025,28211210},
{382169137,539061078,307876327},
{793834193,749517265,636542485},
{325056057,167164764,802377412},
{819127561,229893238,523317660},
{928511635,62267753,777619929},
{715243378,47291577,287143675},
{909712812,288961399,531187171},
{776810308,773263819,786797403},
{784292410,93787217,944259558},
{108200324,725901983,437839183},
{582486863,745198009,268103036},
{280285212,404231303,846548045},
{277236443,803104478,348357863},
{407525121,870954027,591653118},
{428038915,520823346,207818008},
{24131371,897801569,250793022},
{450556912,175116499,484747937},
{728615958,663730573,366191585},
{85778458,173292411,194610054},
{434844001,588810499,729425916},
{851337637,373656446,220720494},
{676757830,667188263,77651088},
{432013043,979146626,976501268},
{791516450,392548740,158737535},
{797737447,667571280,631174455},
{361986899,558994539,758601952},
{790554612,197339586,680467618},
{99737399,735358267,430309343},
{556485354,96441288,883211301},
{582562894,942240941,273680605},
{45888384,426323253,781091568},
{417882691,299850013,118440039},
{866092252,383316259,46850198},
{76326907,612460248,817531204},
{128446669,662024783,814813107},
{79187200,219772980,200012817},
{114805570,224103399,372831074},
{187477386,955783560,327877697},
{518945490,267389792,24435162},
{658953880,631548509,928784030},
{565725343,654406853,39099133},
{765433460,902183596,801536189},
{389416172,620295206,832820014},
{856211351,877279949,610643664},
{996454278,838328639,902002585},
{909494817,173410246,54967674},
{268632008,24614978,58428432},
{809893189,3509036,670025301},
{676137825,55739030,691591915},
{259916253,705922970,69995694},
{117599414,397941010,586305515},
{356648582,353875477,538541877},
{985732338,638556973,448006797},
{343249520,850394809,68405623},
{50899520,537994888,858031058},
{718800694,485645421,496453263},
{72628513,79531916,373040694},
{706551485,450096530,338665172},
{74794108,812339225,156314532},
{751895321,717914330,438817009},
{102136029,230908390,51456160},
{851943247,828481468,1276545},
{350798058,456118491,116460667},
{992927483,257723588,97906795},
{905894203,892179771,134943449},
{999574610,455258545,726782935},
{545784743,865326437,52763053},
{525520982,46542795,913458593},
{37440083,735476785,169672517},
{441373838,36016362,138095394},
{519713698,475514225,190989458},
{999007620,475286909,739030673},
{791029697,916229791,923313064},
{790149915,363663578,271858374},
{560701143,567892312,981581173},
{375999376,777695784,672638455},
{337852385,895415801,884992302},
{564099580,98149307,865576433},
{183646357,193819582,4095468},
{707103328,626208081,960783525},
{482666013,672663640,346879212},
{711159817,696443258,661608702},
{772539478,337953167,680895194},
{81750538,794261121,415935760},
{759591676,771316744,610877457},
{1597,999999020,999397937},
{292920852,619522428,280930336},
{535555272,814830418,541571124},
{338432125,24896576,554108296},
{402420147,612821988,116925487},
{699934968,836899827,59843110},
{715581393,257204693,852865590},
{71927331,260625488,130948492},
{358590920,930845367,393771834},
{170455323,303269427,482554626},
{264869286,749206315,838357449},
{560193378,927209211,332113682},
{264448417,703406845,494496313},
{775407083,562121446,524758679},
{770269534,954095356,81991186},
{326531994,17757856,535764657},
{749500087,926793566,451989471},
{458554162,653035237,541303276},
{977421092,213066589,661618080},
{738227440,689263420,294920625},
{674848433,405320339,779553125},
{137953946,347470760,335900330},
{826989804,260586779,695939625},
{303589792,250906684,108957487},
{565130550,835481081,337761534},
{844604882,544649992,713457458},
{959160169,630982513,493454340},
{439154927,381607124,577990823},
{434180425,235625211,206727545},
{383967184,218113703,849839931},
{33366209,835338478,990409271},
{358511555,185180616,435388586},
{165399538,672437627,101254838},
{722673059,548546282,230781696},
{580324466,477187527,180090608},
{901305862,20556488,202775036},
{1187366,538466976,587907519},
{873635649,343367793,27785025},
{331964373,518711753,463918971},
{895923780,74059691,634510736},
{431330760,334795872,27390880},
{265274659,36232136,124894475},
{51451957,534827964,287598586},
{104765131,432455620,324301703},
{979921372,984688548,969494035},
{392583208,421453810,315585580},
{88838835,877486314,185951177},
{602505025,204825834,351075901},
{266550300,640881872,33488209},
{535333634,91057912,873946617},
{922867773,805882474,228284466},
{802781999,497572790,823443225},
{697223545,511838889,618279650},
{971039063,421787945,332475101},
{858086839,627900828,975718123},
{507882293,372943093,548274711},
{921117932,345715884,513781361},
{786049485,113901934,412600904},
{311693072,575798992,282080264},
{725456086,27267461,817930154},
{718791584,845057847,942232496},
{383426329,321277419,732228619},
{537321526,962139389,488648149},
{181833734,474286844,44750340},
{987229733,281242731,476418585},
{358381106,296354585,632755781},
{305333264,889239007,617953133},
{894797088,399138365,510739406},
{187807267,153107431,235544827},
{567308905,74956418,680699665},
{759330350,781424045,264550114},
{200800801,491283865,239643901},
{429276745,986326239,352172677},
{516123955,10266406,122683607},
{511760093,456915409,86390998},
{376451197,143047546,816043545},
{432040514,120549054,206369629},
{651354360,437218828,117970834},
{652661129,501070380,585898653},
{935372380,425441191,322580067},
{574892880,72705620,123981650},
{615173922,212235922,883973545},
{109685426,430884217,727564056},
{172049565,225043601,383587841},
{749633215,800637836,797646086},
{315533049,732302705,678583913},
{14766177,800430105,29316123},
{345815969,700636326,170790768},
{771838168,865521624,323950136},
{861899746,392123919,596414445},
{547632659,785941725,439990192},
{316750682,454494707,644967415},
{881749853,570150119,17290116},
{826235105,336918924,153724589},
{108856626,708464793,872997152},
{715292019,391358946,220598626},
{445874710,880593768,998686042},
{830674395,829937790,218537571},
{899965158,391366788,410118424},
{371534710,924307489,713631831},
{999924982,46368,671232238},
{50661999,97546342,417238355},
{902559544,653865278,799285529},
{16135923,783419095,219562062},
{186976757,484137243,424323047},
{777107504,818936556,571245648},
{71531324,683548167,399410611},
{27605973,122342621,876809153},
{355661378,429419584,748455849},
{573176985,637059239,474728402},
{727776849,822572946,276715547},
{424818579,710341202,653141463},
{780297532,409127800,939040845},
{440709649,975969889,771975355},
{846838369,772420565,926335473},
{270827257,626319704,124713839},
{979661977,691185448,904213481},
{122898483,140179314,853944810},
{242081444,755977156,667775128},
{374798937,542351738,112195337},
{566880502,902652630,186591601},
{606451782,379913000,800836400},
{354669184,979157666,151944668},
{946987478,113598719,524913019},
{330664015,6487490,1861581},
{721083970,656252556,332496193},
{639187167,939590803,207173160},
{82482135,261360827,277380014},
{185995051,54661140,656035953},
{525503570,227832690,388897025},
{407656820,841290252,582453221},
{699400129,121394612,417855086},
{497605819,731701189,103234761},
{948588014,45032517,140589896},
{289906293,983375900,730543609},
{787287157,660188632,303781270},
{267435975,24864047,434234707},
{507111748,882567229,345048928},
{606158138,227999044,710424742},
{93845194,851623278,734010545},
{365467528,705599596,693070236},
{741536513,99750036,961637230},
{482020643,127727607,299765962},
{519553531,578144719,850642663},
{361132951,777397639,399640108},
{502700973,765347824,716279068},
{406692099,458293523,275805171},
{816171783,989869620,777658332},
{395809084,266091985,90945989},
{710872715,58253388,985357564},
{546027777,903751015,623800565},
{154440743,389975639,966354230},
{43016230,987788839,215300746},
{842218878,908576940,748108055},
{10964974,857112792,481098808},
{563807061,817267909,3180015},
{942024051,849169982,113920048},
{666258299,26313938,777369192},
{494214377,60167623,940495078},
{907109932,880100715,269835106},
{307300980,108871225,452136886},
{710330662,875346441,970122837},
{935995278,775940003,776432444},
{777676747,652779463,72408220},
{340286625,75668771,385814485},
{38488723,673393600,905693828},
{292688115,851891495,284013554},
{958804834,601940012,753854804},
{829809001,953555997,779024374},
{285582134,939053501,446119531},
{592673115,787424730,365644695},
{489733910,830126597,521045558},
{117441647,192570566,906427976},
{667380182,705139707,606404668},
{195380483,807061608,226114688},
{204657838,45856997,956635496},
{842152749,505713043,456491914},
{35547239,994596747,245168592},
{331999678,191968720,980411773},
{131604252,112084399,799259884},
{980460233,127577343,900717152},
{541041133,159585306,876837553},
{319264038,701899153,820402212},
{876230425,687474052,408687089},
{325865309,334005612,266804529},
{650233111,106258885,443696495},
{306982075,904498429,961652788},
{955619886,153863125,11909721},
{933456455,956820388,686087221},
{930011089,2283628,305090178},
{885265840,283043407,385708940},
{774865673,743333131,558083090},
{993657630,104795289,293709761},
{983303988,970991109,266070523},
{176635292,75946886,743917905},
{898609339,933466038,514285409},
{332728967,915649947,438471012},
{185764237,654970983,631521077},
{619887337,811499983,715420121},
{778277087,786231588,374562983},
{3524578,997821698,410141410},
{325965216,795799540,564113150},
{44146461,453501740,481579479},
{903179508,154406218,19359591},
{809672344,632727759,364033131},
{776012610,673082321,679293647},
{922446414,616031689,646347168},
{630591952,989271374,986839082},
{925324440,886434339,448275793},
{890226578,754946557,243021700},
{529619056,589865503,872850958},
{473333556,686754540,151085513},
{61567838,67586695,968634546},
{511239568,567294100,224838326},
{428327410,742138355,340383858},
{944587025,545216266,707676539},
{206387323,587490616,147149572},
{765217186,758537061,114879647},
{644751131,256007331,118079546},
{646222654,820205083,320186846},
{681768169,170006352,28107846},
{358812503,796618373,110022542},
{503558674,719003248,645940754},
{187999057,409953565,374067781},
{893660864,859606903,770748153},
{264448773,611480100,105635803},
{999043206,208250061,737707029},
{684184763,334434098,599696239},
{824052248,195301230,664611038},
{917365208,73749944,445888686},
{806763391,624019965,483840929},
{769682620,109272662,770780210},
{447127137,937606742,737861541},
{693690605,334925440,51117047},
{794079868,304145502,129643612},
{96198025,950578032,242483605},
{429321900,292922829,768084572},
{292112370,175972738,495194185},
{178603344,765333263,443476095},
{693352144,899646530,326751187},
{391695550,502023354,578609710},
{882509482,275516207,208457722},
{293577983,461974556,295875362},
{476219087,394742783,44042840},
{46830057,477622685,36218595},
{980471236,607198721,512306877},
{796632652,582718266,516057405},
{37421447,271302355,940851259},
{130422885,852794931,684308555},
{53648999,171032873,810182361},
{413826897,717820129,499553298},
{938503143,173572310,920327909},
{281013666,62086007,550463895},
{444673958,875096183,741991175},
{626559397,87798235,809344154},
{993186036,215465457,470018793},
{803751993,743295249,907763266},
{899810693,649342994,241194276},
{460231377,596322755,390542798},
{640377418,607999228,708145071},
{838062468,37994620,923868375},
{231032795,537440148,328858101},
{470900723,568680736,97744209},
{267359416,845078619,760190528},
{19299011,162325060,16144294},
{832648934,54146439,233509070},
{938325436,71861015,199956604},
{41376036,309681274,246801822},
{811169966,29761025,71236999},
{10330895,789529350,905098812},
{385033448,209613911,713286550},
{781705597,492766356,707895003},
{50965888,962857236,134356796},
{117007715,848167603,212409744},
{305357276,611189288,948722373},
{4630487,701673616,478481798},
{986780570,110938093,271277961},
{677925428,816734399,969108371},
{743354124,476399850,182869658},
{879227832,306592098,643972021},
{343476498,931159308,758759346},
{955893016,287254752,296492829},
{884904900,579855830,900105606},
{645120754,463676186,588811716},
{934697381,501098519,39945742},
{123510951,273529742,559574147},
{557076403,688144040,338372580},
{740049711,67796855,113963738},
{355708762,163920462,870536461},
{427579386,500545572,737604138},
{844873162,911018251,819634879},
{264562946,608848388,44404039},
{416341873,504471340,200148316},
{958477795,26499275,63916004},
{589284713,722031600,953808144},
{50069349,735737583,807291540},
{915863960,83859031,706831121},
{438406536,386426233,548470058},
{965330220,468134284,522078018},
{49442460,122808141,946866316},
{834419866,102334155,510853745},
{628972961,499875544,580475428},
{22556810,31553096,46617631},
{534427502,959488722,507055422},
{758423348,777658301,996791897},
{750300092,546194588,629823236},
{573487526,362962660,88779624},
{334572493,381903130,77030023},
{154090250,908166784,596212827},
{586174150,880452841,874160194},
{380127701,453748616,105335718},
{328504450,12195649,792583845},
{326014110,414297563,837387666},
{531030830,361207607,446207103},
{21773508,347077002,300834324},
{333582883,748515983,717397248},
{320133919,696755803,854890103},
{911894034,208579071,685434796},
{454615616,211678378,933781522},
{252736542,908009641,540169284},
{390015786,107048889,847424535},
{529360703,179023735,18912541},
{978073313,227689923,439289876},
{217056913,618583866,42674314},
{667275678,591988356,39300624},
{849823797,604182954,805719845},
{405782487,272656407,912228895},
{760834235,20236679,252210639},
{83549566,766181120,140515092},
{358331962,305919970,687426537},
{674464076,829771610,254470054},
{125516990,742790316,694056925},
{487418896,200782252,357175271},
{447953789,213471915,674732490},
{388340177,721785618,392906521},
{691405710,662644186,857531668},
{554434872,207763088,728404280},
{763606967,846714155,548510164},
{999484764,801337854,41310518},
{318604269,864990120,405854565},
{224841755,699302941,298551243},
{780518134,950988333,104552452},
{719814261,159468415,697153849},
{98149541,868944620,351904986},
{437854391,774336334,534798945},
{415151264,696312499,944991009},
{151573523,153948171,662880139},
{425020229,258919793,681056197},
{474315370,652546545,178024767},
{767624360,903201644,87101095},
{4108204,358703167,890320855},
{735911851,452125854,197327164},
{749341566,94168860,658507462},
{258105250,961902760,826404159},
{540743577,16370198,741437016},
{756449583,55855689,328289318},
{281632551,215953567,319594434},
{42639431,454565561,538394664},
{874911065,912663095,987454529},
{995151646,543935779,606326098},
{303763304,105381649,525352914},
{431128057,864966792,819701443},
{931670909,496065601,945035762},
{656430799,628525731,668075778},
{752659872,295053465,244642569},
{827011659,781723795,448820505},
{606016708,770640835,20208828},
{96521495,843040222,937762990},
{45202870,647675849,441031768},
{228865808,953067322,106945015},
{310754962,360721530,857760585},
{770103297,9854839,803215577},
{487161638,553139664,619019172},
{833257262,430983239,181897505},
{452827650,467042066,604148313},
{577709280,975483289,52685746},
{779160797,280196628,253964268},
{101957869,618886780,576991680},
{730356746,417238491,612921060},
{544687938,478087100,446980964},
{876144487,107935489,681148200},
{531987437,339441448,482831920},
{90205956,44877033,712656776},
{803094361,519745367,98761471},
{743358099,114364163,893447897},
{544752241,37843332,536437737},
{510427173,752731929,826626498},
{262043949,659684718,506058729},
{348231857,338917961,587869207},
{973757923,472074656,587231440},
{405695833,899099104,548456798},
{790675963,640792843,441630745},
{438274486,185051899,433621005},
{968239976,783542987,796549766},
{126983393,988568159,310641616},
{748131286,486867813,178131345},
{621665221,142975631,537802563},
{209128718,182996199,841888907},
{9592645,186188830,510757989},
{897927321,441785834,359382247},
{778742000,192473059,44066357},
{112305827,710050067,545147927},
{895683483,63502762,403531865},
{978728087,749624170,51949371},
{544430559,817332360,555668596},
{959883325,655772232,340578923},
{123640060,324723417,290282076},
{644500996,61281649,18420937},
{832433873,429727121,393424632},
{559588575,863770217,28513396},
{604379130,83949699,603077492},
{86957406,740049971,81448600},
{615769104,460427984,145931828},
{530311604,455948497,554231548},
{548317728,945242677,600965010},
{377017593,274532785,588039164},
{747318596,664986881,595294988},
{375763524,438246679,639704982},
{988315078,795108980,737725529},
{475159963,503342098,833415046},
{987490029,798695907,237828250},
{761234638,789266152,629955599},
{526995944,579570455,866809243},
{610326109,516604943,808143007},
{744382501,316940568,965728861},
{793833055,991921272,118050107},
{929180052,976898908,551450593},
{556606451,714442003,29180583},
{249118185,794186389,452195284},
{241032704,548011571,704468302},
{493425268,376714645,131564763},
{331018899,979582738,12842989},
{644184919,625627491,547956488},
{252481466,631894632,83478401},
{953931953,771930697,15042607},
{407733836,905145457,329894868},
{512239305,942212112,820150587},
{818360440,28462257,66729734},
{845613084,571787872,728836942},
{332247325,445818124,394267944},
{40742042,630738657,323979426},
{433138486,28032457,538802673},
{875151995,43009995,322659056},
{910752528,764860371,610256271},
{374013713,128569876,265045201},
{507419503,666114064,82835832},
{79411823,181717753,460399575},
{986627937,559467465,150165447},
{576754886,477517678,216349911},
{868006340,378490160,421933408},
{393087522,423131148,438560380},
{473640112,576512706,580720442},
{499932984,511977608,775495016},
{424379383,915474426,131975418},
{958492673,142802466,542139154},
{453683822,159317181,64501406},
{959518215,106887179,437148085},
{96136071,986075800,995821304},
{418948862,508512088,921587900},
{587495556,827019348,453544297},
{885062356,9067912,530005158},
{505948673,809120922,752214385},
{740566869,116236185,596168371},
{880393255,614212241,683041648},
{605687257,970162190,910002157},
{297803373,204835455,313338976},
{578889498,708019999,400926925},
{422113734,67428572,396103066},
{64295165,529474289,285868607},
{232976206,416306838,122548089},
{9483443,836474305,364311742},
{23439703,44056218,988871480},
{52437287,39578745,40946687},
{719901251,895620318,235381425},
{411743328,437833771,406595535},
{843033549,450612130,798959260},
{392662237,719820489,227858036},
{530054771,95587151,451520926},
{929879066,913391220,533900739},
{520439271,223314363,843009073},
{477732907,995872758,535307981},
{40697627,758997311,313547597},
{875415210,310923640,933388470},
{609444552,108291740,377753703},
{127472218,123785862,799549581},
{273133904,947833675,358503572},
{452846641,933455556,26296179},
{943884784,927021623,757643794},
{277394078,906935490,556794757},
{805798562,311945757,282175318},
{87422827,831324169,624510285},
{573667059,273888208,634643799},
{984757439,798089477,801403468},
{534243662,146980595,921405700},
{442495865,815265263,632234021},
{787760461,381475374,328584572},
{865870870,196286361,223417559},
{732543795,12752477,500335133},
{583815479,780990776,720796264},
{747973754,113257808,209747710},
{564706400,851432142,743595923},
{92653212,127771545,560991488},
{880319790,983817118,548202635},
{465352738,808175547,145206018},
{653340568,807721059,363791341},
{135183955,632510732,27855009},
{615429703,375036853,563758069},
{373880912,737859395,577978097},
{721517999,894658683,691944369},
{113163014,522347254,54904785},
{214053392,600615566,886680257},
{584497503,205455959,964475550},
{732838212,945587350,234154924},
{544323964,209213188,742811220},
{207293458,226517494,28933905},
{946590379,348443220,85029062},
{555892321,48861014,961139670},
{427220471,193827163,143451042},
{94576047,418199828,226450033},
{414745358,434911928,806824813},
{197953180,354243748,39519988},
{692611570,725467387,293085163},
{253117501,532498888,608696482},
{97616167,100983988,528930095},
{346747027,511805060,324281127},
{840022891,775517598,730864932},
{922755384,813095246,139221785},
{78662757,400989418,149336035},
{207895823,907058870,854470158},
{313131034,937536382,74105540},
{134548496,464640208,108960298},
{316594869,216821327,650420050},
{235890128,394725881,982785730},
{685417400,87480591,562097677},
{776858354,997471889,806127345},
{145104138,795519643,220437360},
{370317968,508267963,343929007},
{773452633,815559787,724012193},
{256700575,324632358,501809661},
{65771568,181558206,743492201},
{860282292,655980397,724037382},
{861973178,731486209,32938977},
{148042268,819061841,411378207},
{96481944,182618202,483676130},
{983501231,182879543,419956015},
{736132270,996326724,873689389},
{116070824,305317501,438975222},
{203467061,446109541,734083463},
{418205184,904122757,306225912},
{436077954,307760969,119924285},
{520778395,754133024,12431477},
{3003046,451777160,452679804},
{753808361,842883739,858981321},
{796063896,10799526,443341778},
{410101114,271913949,759667938},
{920410944,456236860,26313171},
{621011666,760349062,466222854},
{438965267,199872168,239208326},
{434492568,187268944,957026988},
{392557425,586155145,365930822},
{98306258,468426494,196023050},
{789284487,106350147,317435080},
{261686500,40833746,798550278},
{965086517,503499152,804831257},
{780039259,107323927,130104315},
{176229915,591009897,90295131},
{186177082,952419457,825508900},
{64133147,987816929,261698002},
{932924403,467032750,470979912},
{821252594,480511439,356685959},
{243523224,324986415,178248829},
{128230676,919502936,636125957},
{48285894,586659342,750318855},
{331384186,474862116,304904278},
{195236074,954770851,752191601},
{799714204,845746762,250389174},
{765714204,888240634,628718111},
{985468076,888517165,929685478},
{565327467,653374477,706002115},
{994666507,26137916,74030568},
{670409052,86045214,743558048},
{555224115,987685194,516710263},
{765279468,341711992,275682542},
{553011905,390542895,603655660},
{265447704,67700365,712465470},
{617954369,413974258,680940578},
{205780854,374857254,209040597},
{375371518,770299316,613783373},
{614246575,35114310,258151337},
{153709936,866474877,173691473},
{485431333,28665233,745732999},
{246972460,486461479,217224289},
{278126210,304742948,263820936},
{922308099,308369104,745816351},
{75711099,693964760,29833407},
{227127313,583789742,8014425},
{682404183,631565472,544747147},
{361313162,217637389,397742344},
{551080038,107244957,286585970},
{947306500,235097232,553810930},
{680057396,790216554,72124658},
{532993244,284687367,563057871},
{729286688,697093021,479675558},
{149693388,266125394,417730556},
{748562969,219778140,331815818},
{686470846,616223581,135425954},
{951164109,48544618,923767947},
{783096273,259327031,579230658},
{256220419,521315079,727787510},
{121749809,585909027,146346693},
{335111523,687118902,300236456},
{441660149,603520033,516075795},
{940835184,96966881,633982269},
{886462277,711031744,830119967},
{708889823,408435189,256163325},
{133234909,348635994,71099802},
{125742506,38545482,639942303},
{544874486,451876730,956742948},
{566610755,549499251,37494250},
{31808351,55797433,828935233},
{708710588,551848063,982785105},
{686021810,113766904,208995061},
{576481600,392981991,526317578},
{801714084,737147663,540568937},
{958507356,628221787,722713871},
{725091355,558751888,900843974},
{701317215,807624810,711027201},
{746244005,439055491,555446800},
{979778211,574047029,363430668},
{41808803,387778790,846457785},
{182795469,785195740,343811684},
{789022370,829814977,464197757},
{268979149,822256242,460134887},
{532900965,256517626,466086499},
{533725675,346890856,107995796},
{772371734,705431595,175355691},
{82816325,169193802,231162997},
{829366075,640228027,828169479},
{89459982,170491414,765077584},
{576489007,20946257,493008624},
{525990521,538182908,626511910},
{54122435,592115965,157519503},
{166861465,461083751,589037885},
{554596146,652084205,862955618},
{401428759,276091666,577873863},
{894364059,506530244,149632636},
{465259491,468359805,357909044},
{450420273,473384262,972026502},
{767601613,28713044,624233589},
{636329976,156744402,250962180},
{130328088,132616976,997709618},
{385216733,189960928,483600441},
{71074301,872486946,996267614},
{160617771,576947866,323322223},
{766755116,77242022,44988721},
{287002118,397550553,8667026},
{852933700,156707159,516683938},
{272496527,619932381,936950937},
{159900589,689847614,236960280},
{962305609,623689040,155774649},
{494543560,974887031,92863609},
{397680704,192422211,827002723},
{960167729,964577774,804283289},
{760540775,721327790,579530567},
{732467836,985613290,230219487},
{419390685,17699582,968014196},
{670787718,528265844,497203069},
{563628385,505176094,171383750},
{88258202,519986622,166790345},
{168152149,999655697,83358356},
{544925113,889164309,30851551},
{949718574,739306098,941106246},
{678125716,387432377,912755154},
{705042126,785860398,688355858},
{412161264,687936554,680256700},
{570399136,799290343,809944342},
{618770434,532870014,353003673},
{152945986,144106388,364315104},
{499730181,378008585,612756608},
{730235236,548203599,542453810},
{13041873,960002226,497292916},
{863769157,819798907,65995305},
{156450053,628612855,497977916},
{398996102,536192328,890279041},
{396485785,694297011,611732153},
{683010963,595376346,477342001},
{875453298,448253639,326298614},
{413654003,868910791,862251387},
{853017107,442691961,183202460},
{969834509,963735318,54903353},
{97304683,821409901,208207434},
{818627412,862422447,779359119},
{943310796,878992079,451398658},
{117275993,359671622,95269883},
{999082517,568391255,210095214},
{537255912,180406948,359251725},
{61132760,120136665,33527897},
{285737717,758290317,317012377},
{515422924,178496287,774435550},
{728621068,837172372,50966687},
{472596219,8390086,435523618},
{856664502,491922304,107721556},
{843206126,252811133,95746906},
{499058082,683931033,786125068},
{164200141,862706445,953714309},
{600686514,404981171,857223824},
{679857496,343366122,192087135},
{820594523,73770239,784075611},
{236122399,603532786,535079407},
{164596005,939928680,932244853},
{35705139,104796271,735173949},
{657475648,429102693,14796490},
{47908455,496969285,964703414},
{791949318,372295082,331943573},
{474885099,577028763,323520856},
{791368954,265665181,832233301},
{534209946,139501346,391513615},
{963678876,567966681,388220858},
{274718657,755335564,523359584},
{90262159,942608749,653222063},
{492649422,708897480,967192012},
{64363591,927488174,959011685},
{652247495,997347675,974190485},
{221822151,253076096,506705961},
{603407563,961771168,705221453},
{80683669,963143862,431772218},
{115335749,228538957,97800280},
{847869260,963402659,721743431},
{742528589,112730963,237008952},
{721855246,836860628,58213320},
{274064524,631160278,683421425},
{599354007,781875034,834022929},
{122089960,959231025,534903222},
{268237427,856191078,90798861},
{138035103,698658005,540593209},
{553424623,49195630,789570416},
{737314792,539623406,832802250},
{246342122,93723161,46015612},
{538680306,662271247,24406852},
{839245299,833967729,326533799},
{418163403,49423109,987738762},
{594272405,439063639,612602156},
{9468933,510002023,595225336},
{837499383,169424380,59359909},
{149347236,840812253,947651149},
{228757258,196751983,365536401},
{16733253,681771825,466279804},
{626780262,304830306,528391884},
{504519264,746364196,377295813},
{656413391,325252193,753603545},
{353801518,12869153,932680483},
{891810636,620059294,853486462},
{905699527,150230093,903627839},
{654900930,872650968,128799833},
{552408693,97711045,530439064},
{590489615,858887289,101813519},
{291104721,874414528,855220780},
{753698062,663306135,611495605},
{50179805,389893429,14307759},
{379079274,100460185,428717561},
{658146590,711883378,753961026},
{519722565,849806006,877562254},
{610430559,624011198,254656568},
{289497317,594094963,219121607},
{793972701,568851772,964300386},
{112408030,577109763,317020930},
{286800396,219086057,501657152},
{445332947,268906828,982236050},
{918940145,93596191,635309375},
{275596466,535671138,615204893},
{144996647,884291363,911124200},
{234996661,333110710,385344874},
{79805678,204019072,700292373},
{531636130,589699444,896464143},
{433184658,712211349,574335240},
{391526600,587607390,296761552},
{152075608,66868890,450383195},
{826070645,338482655,113743870},
{947354201,580222161,647822725},
{684277653,208293113,121520164},
{716622931,793850486,781900333},
{847625800,481766457,134927298},
{881568104,113484033,761570825},
{694171441,408417871,242174520},
{99720534,300340349,380387199},
{280530601,603337683,812848706},
{647914434,557221867,931995909},
{182890481,390893801,375014863},
{293949683,158363670,69675496},
{264068463,837965506,998008199},
{941248608,365069693,768071074},
{277539449,979683806,828339752},
{386266693,382629633,973010746},
{565720279,787064788,514814408},
{967410938,591646451,650301091},
{521845005,937083772,860537547},
{444356125,722011322,451321462},
{209014237,142717964,248569243},
{224042709,503429617,892661365},
{807503556,417801564,929666943},
{107920472,815449418,128493982}
};
long n,a,b=1,sum=1;
main()
{
	cin>>n;
	long i=n/10000000;n%=10000000;
	if(i>0)i--,a=memo[i][0],b=memo[i][1],sum=memo[i][2];
	else n--;
	long mod=1e9+7;
	for(int j=0;j<n;j++)
	{
		long c=(a+b)%mod;
		sum=(sum+c*c%mod)%mod;
		a=b,b=c;
	}
	cout<<sum<<endl;
}