Given non-negative integers \(a\) and \(b\), compute

\(a^b \bmod 1{,}000{,}000{,}007\).

Use the convention \(a^0 = 1\), including when \(a = 0\).

Input

One line containing a and b.

The input satisfies:

• \(0 \le a \le 10^18\)
• \(0 \le b \le 10^18\)
• \(Define a^0 = 1, including when a = 0.\)

Output

Print a^b mod 1,000,000,007.

Example

Input

2 10

Output

1024