Rhezo likes numbers of the form \(A^B\). But computing \(A^B\), for any 2 numbers A and B is a hard task for him. He would like you to help him out in this.

Input:
First line of input contains a single integer A. Second line contains the integer B.

Output:
Help Rhezo find \(A^B\). As this number can be large, print it modulo \(10^9+7\).

Constraints:

• \( 1 \le A \le 10^9 \)
• \( 1 \le B \le 10^{10^5} \)