Problem C
Stauralitun
Languages
en
is
Lita á alla ljósastaura línulands rauða, bláa, græna, gula, svarta eða hvíta. Rauð og blá málning er seld í tunnum sem duga fyrir tvo staura, og hálfur pakki af bláum er þegar til afgangs. Því þarf að lita sléttan fjölda rauðan og odda fjölda bláan. Einnig er svarthvíta efnið selt saman í pakkningum sem dugar á tvo staura, svo heildarfjöldi svartra og hvítra staura þarf einnig að vera sléttur. Á hversu marga vegu má lita staurana? Lítum svo á að lita fyrsta staurinn bláann og annann grænan sé ekki það sama og lita fyrsta grænan og seinni bláann.
Inntak
Fyrsta og eina lína inntaksins inniheldur jákvæða heiltölu $n \leq 10^{18}$.
Úttak
Prentaðu fjölda leiða til að lita $n$ staura á veg sem uppfyllir skilyrðin að ofan. Þessi tala gæti verið mjög stór svo prentið niðurstöðuna mátaða við $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 |
209920 |
