Compute \(a^b mod 1,000,000,007\).

Input

One line containing \(a\) and \(b\).

The input satisfies:

• \(0 \le a, b \le 10^12\)

Output

Print the result.

Example

Input

798997288095 352427476297

Output

1473908