Problem D
Wider Digbuild
Languages
en
is
Benni is once more playing the game Digbuild. Before he looked at how a tunnel of width $3$ could be illuminated, but this time we are looking at a tunnel of width $k$. A tunnel of length $n$ and width $k$ has a floor which can be split into $n \times k$ squares. Torches can be placed on squares, so each square can either have a torch or not. There are no constraints on the total number of torches, placing no torches is valid. However it is not valid to place torches on adjacent squares. Squares are considered adjacent if they share a side, not if they share a corner.
Input
The first and only line of input contains two positive integers $k, n$ which satisfy $1 \leq k \leq 10$ and $1 \leq n \leq 10^{18}$.
Output
Print the number of ways to place torches on $n \times k$ squares satisfying the constraints above. The answer might be very large, so print it modulo $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 |
