Problem C
Digbuild

Flestum finnst okkur nú gaman að spila tölvuleiki. Benna finnst best að spila Digbuild. Digbuild snýst aðallega um að lifa af. Í leiknum er all flest hægt. Það er hægt að klífa fjöll, byggja kastala og veiða fisk, svo eitthvað sé nefnt. Leikheimurinn samanstendur af stórum teningum sem allir hafa horn sínum í heiltölu hnitum í þrívíðu hnitakerfi og eru allir jafn stórir. Spilarinn getur bæði brotið þessa teninga og lagt aðra teninga upp að þeim. Það er þó meira í leikheiminum en þessir teningar. Það eru rúm, stigar, myndarammar og kyndlar svo eitthvað sé nefnt.

Benna finnst ekki gaman að byggja. Honum finnst skemmtilegast að grafa göng í jörðinni. Göngin hans Benna eru ávallt lárétt og samsíða $x$-ás hnitkerfisins sem heimur er í. Þau eru einnig alltaf $3$ teningar á breidd og $3$ teningar á hæð. Nú er Benni búinn að grafa $n$ teninga löng göng og ákveður að fara að fá sér vatnssopa. Þegar hann sest aftur við tölvuna tekur hann eftir því að göngin hans eru nokkuð dimm. Hann tekur þá ákvörðuna að raða kyndlum á gólf ganganna til að lýsa þau upp. Benni vill þó ekki að gönginn verði ljót svo hann þarf að raða kyndlunum fallega. Benna finnst göng ljót ef einhverjir tveir teningar sem hafa kyndil á sér hafa fleti sem snertast.

Í Digbuild er aðeins hægt að setja einn kyndil á hvern tening. Benna finnst það svo slæmt að göng séu ljót að hann myndi frekar hafa þau óupplýst (svo uppröðunin sem inniheldur engann kyndil er ekki talin ljót).

Hvað eru margar mögulega raðanir sem eru ekki ljótar? Þar sem þessi tala gæti verið nokkuð stór þá á að prenta svarið $\mod 10^9 + 7$.

Inntak

Eina lína inntaksins inniheldur heiltöluna $1 \leq n \leq 10^{18}$.

Úttak

Eina línan sem á að prenta út skal innihalda fjölda raðan sem Benna finnst ekki ljót, $\mod 10^9 + 7$.

1

5

4

227

100

457171387