Fast Exponentiation Practice

Problem Description

Given two integers $a$ and $n$, compute $a^n \bmod (10^9 + 7)$.

Input Format

The input consists of a single line containing two integers $a$ and $n$.

Output Format

Output one positive integer: the answer.

Sample Input

5 10000

Sample Output

378321089

Constraints

For $100\%$ of the test cases, $1 \le a, n \le 10^9$.