Power Modulo

Medium#math #fast-exponentiation· solved by 0 · time limit 2.0 s

Print $a^b \bmod (10^9+7)$ .

Multiplying $a$ by itself $b$ times is far too slow — use exponentiation by squaring ( $O(\log b)$ ).

Input

Two integers $a$ and $b$ .

$a^b \bmod 1000000007$ .

$0 \le a \le 10^9$ , $0 \le b \le 10^{18}$ . $0^0 = 1$ .

Input

2 10

Output

Input

3 0

Output