Hide
Problem E
Skákskokk
Languages
en
is
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$.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
8 |
56 |
| Sample Input 4 | Sample Output 4 |
|---|---|
20 |
897691418 |
