Sets

Given numbers $n$ and $k$.

Let $[n]$ be the set of all numbers from $1$ to $n$.

A set $A$ is a subset of $B$ if for every $a\in A$, $a$ also belongs to $B$. The empty set ($\varnothing$) is a subset of any set.

It is necessary to find the value of the function $f([n],k)$.

$f([n],1)$ returns the number of subsets in the set $[n]$.

$f([n],k)$ where $k>1$ returns the sum $f(s,k-1)$ where $s$ is a subset of $[n]$.

Input

The first line contains two integers $(1\le n,k\le 10^9)$.

Output

It is necessary to output $f([n],k)$. Since the answer may be too large, output it modulo $10^9+7$.

Examples

Note

In the first example, the set with $1$ element $(\{1\})$ and $k=1$, so $f(\{1\},1)$=2 $(\{1\}$ and $\{\varnothing \})$.

In the second example, the set with $2$ elements $(\{1,2\})$ and $k=2$. $f(\{1,2\},2)=f(\{1,2\},1)+f(\{1\},1)+$ $+f(\{2\},1)+f(\{\varnothing \},1)=4+2+2+1=9$.

Scoring

In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Note that the evaluation is still in the testing phase.

1. ($5$ points): $k=1$;

2. ($5$ points): $n\le 10$, $k\le 2$;

3. ($10$ points): $n\le 15$, $k\le 3$;

4. ($80$ points): without additional constraints.