Problem D
Víðara Digbuild
Languages
en
is
Benni er enn að spila leikinn Digbuild. Áður skoðaði hann hvernig mætti lýsa upp göng af breidd $3$, þetta sinn skoðum við göng af breidd $k$. Göng af lengd $n$ og breidd $k$ hefur gólf sem skipta má í $n \times k$ reiti. Á hvern reit má setja kyndil eða sleppa því að setja kyndil. Engin skilyrði er um fjölda kyndla, til dæmis má setja niður engan kyndil. Hins vegar má ekki setja niður tvo kyndla á aðlæga reiti. Reitir teljast aðlægir ef þeir deila hlið, ekki ef þeir deila horni.
Inntak
Fyrsta og eina lína inntaksins inniheldur tvær jákvæðar heiltölur $k, n$ sem uppfylla $1 \leq k \leq 10$ og $1 \leq n \leq 10^{18}$.
Úttak
Prentaðu fjölda leiða til að setja niður kyndla á $n \times k$ reita gólf í göng þannig að skilyrðunum að ofan sé uppfyllt. Svarið gæti verið mjög stórt svo prentið það mátað við $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 5 |
827 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 2 |
41 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 1 |
144 |
