問題文

正整数$x$に対して、関数$f(x)$を以下のように定義します。
　　

$f(1)=1$
$f(x) = f(\lfloor x/2 \rfloor)+f(\lceil x/2 \rceil)$ $(2 \leq x)$

ここで、$\lfloor x \rfloor$は$x$を超えない最大の整数、$\lceil x \rceil$は$x$以上の最小の整数を表します。
$f(N^K)$の値を$10^9+7$で割った余りを出力してください。

制約

• $1 \leq N,K \leq 10^{18}$

入力

入力はすべて整数である。
$N$ $K$

出力

$f(N^K)$の値を$10^9+7$で割った余りを出力してください。

サンプル

2 2

4

$2^2=4$
$f(4)=f(2)+f(2)$
$f(2)=f(1)+f(1)$
$f(1)=1$
以上により、$f(4)=4$ が求まります。

1000000000000000000 1000000000000000000

504853526

$10^9+7$で割った余りを出力することに注意してください。