Problem Statement

You are given positive integers $N,M$.

A sequence $A=(A_1,A_2,\dots,A_N)$ is determined as follows.

• For each $i$ $(1 \leq i \leq N)$, $A_i$ is chosen uniformly at random from the integers between $0$ and $2^M-1$, inclusive. This choice is independent of the other elements.

Output the expected value of $A_1 \oplus A_2 \oplus \dots \oplus A_N$ modulo $\bmod 10^9+7$ (see Notes). Here, $a \oplus b$ denotes the bitwise XOR of $a,b$.

Notes

Under these constraints, the expected value to be found is a rational number. Writing it as an irreducible fraction $\displaystyle \frac{P}{Q}$, it can be proved that $Q \not \equiv 0 \pmod{10^9+7}$. Then there is a unique integer $R$ between $0$ and less than $10^9+7$ such that $R \times Q \equiv P \pmod{10^9+7}$; output this $R$.

Input

$N$ $M$

• All input values are integers.
• $1 \leq N,M \leq 10^{18}$

Output

Output the expected value of $A_1 \oplus A_2 \oplus \dots \oplus A_N$ modulo $\bmod 10^9+7$.

Print a newline at the end.

Sample

2 1

500000004

314159265358979323 271828182845904523

803876782