Problem D
Víðara Digbuild

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\le k\le 10$ og $1\le n\le {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$.

3 5

827

4 2

41

10 1

144