During a game of Mafia, after Verma is killed by Mafia in the first round, he starts getting bored and keeps disturbing others in the game. This irritates everyone else and to keep the game interesting, Akhil asks Adarsh to keep Verma occupied in something else.

So Adarsh gives him a $1*N$ matrix which has $N$ cells. Also, he gives him $M$ colours numbered from $1$ to $M$ . Now, Verma can choose any submatrix with even number of cells from the matrix and colour it with one of the M different colours. He can colour as many times as he wants . If Verma tries to recolour any cell which is already coloured, the cell gets coloured in the last colour.

Adarsh asks Verma to make as many distinct matrices that he can make such that every cell is coloured. Each matrix is different from other if atleast one of the cell has a different colour.

Find the number of matrices Verma can make and submit the answer modulo $1000000007$

Take $N=99999999999999$ and $M=999999999$