Problem D
Wider Digbuild

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

3 5

827

4 2

41

10 1

144