問題文

正の整数 $N,M$ が与えられます。

数列 $A=(A_1,A_2,\dots ,A_N)$ を以下のように決定します。

• 各 $i$ $(1\le i\le N)$ について、$A_i$ は $0$ 以上 $2^M-1$ 以下の整数から一様ランダムに選ばれる。この選択は他の要素とは独立である。

$A_1\oplus A_2\oplus \cdots \oplus A_N$ の期待値を $mod{10}^9+7$ で出力してください（注記参照）。ただし、$a\oplus b$ は $a,b$ の排他的論理和を表します。

注記

この制約下で、求める期待値は有理数になります。これを既約分数 ${\displaystyle \frac{P}{Q}}$ とすると、$Q\not\equiv 0(\mathrm{mod}{10}^9+7)$ となることが証明できます。このもとで、$R\times Q\equiv P(\mathrm{mod}{10}^9+7)$ なる $0$ 以上 ${10}^9+7$ 未満の整数 $R$ が一意に定まるので、$R$ を出力してください。

入力

$N$ $M$

• 入力はすべて整数
• $1\le N,M\le {10}^{18}$

出力

$A_1\oplus A_2\oplus \cdots \oplus A_N$ の期待値を $mod{10}^9+7$ で出力してください。

最後に改行してください。

サンプル

2 1

500000004

314159265358979323 271828182845904523

803876782