Administrator Uolevi wants to ban Kaaleppi for taking the b'th root of his precious number mod 10^{9} + 7. While he's doing this, he wants you to recover his number from its b'th root a. That is, he wants you to find a^{b} \text{ mod } 10^{9} + 7.

Input

The only line of input contains two integers a and b.

Output

Output a^{b} \text{ mod } 10^{9} + 7.

Constraints

• 1 \leq a, b \leq 10^{18}

Example 1

Input:

10 5

Output:

100000

Example 2

Input:

10 1000000006

Output:

1