Problem B
Skákskokk

Kóngur byrjar á reitnum A1 á venjulegu $8 \times 8$ skákborði. Þér er gefin jákvæð heiltala $n \leq 10^{18}$. Á hversu marga vegu getur kóngurinn komist á reitinn H8 ef hann verður að taka nákvæmlega $n$ skref? Eitt skref er einn leikur með venjulegum skákreglum um hvernig kóngar hreyfast. Það er, eitt skref lóðrétt, lárétt eða á ská.

Inntak

Fyrsta og eina lína inntaksins inniheldur jákvæða heiltölu $n \leq 10^{18}$.

Úttak

Prentaðu fjölda leiða sem kóngurinn getur farið til að komast frá A1 til H8 í nákvæmlega $n$ skrefum. Þessi tala gæti verið mjög stór svo prentið niðurstöðuna mátaða við $10^9 + 7$.

6

0

7

1

8

56

20

897691418