Exponential Growth

You will be given two integers $X$ and $N$, you have to calculate $X^N$ modulo 1000000007.

Input

The only line will have two integers $X$ ($0 ≤ X ≤ 1000000$) and $N$ ($0 ≤ N ≤ 10^9$). Both $X$ and $N$ will not be zero at the same time.

Output

Please write one line, the answer of the problem.

Sample

Input	Output
1 5	1