Luỹ thừa nhanh

Cho hai số nguyên dương \(x\) và \(n\). Hãy tính \(x^n\) theo modulo \(10^9 + 7\), bằng một hàm đệ quy chia đôi số mũ (mỗi lần gọi đệ quy chỉ cần \(O(\log n)\) tầng): \(x^n = (x^{n/2})^2\) khi \(n\) chẵn và \(x^n = x \cdot (x^{\lfloor n/2 \rfloor})^2\) khi \(n\) lẻ.

Input

Một dòng gồm hai số nguyên dương \(x\) và \(n\).

Output

In ra một số nguyên: phần dư của \(x^n\) khi chia cho \(10^9+7\).

Constraints

• \(1 \le x, n \le 10^9\)

Sample Input 1

5 7

Sample Output 1

78125

Sample Input 2

2 30

Sample Output 2

73741817

Explanation

\(5^7 = 78125\). Còn \(2^{30} = 1073741824\), chia \(10^9+7\) dư \(73741817\).