Fast Exponentiation

Given two integers $A$ and $X$, think about how to compute $A^X$. The value can be enormous, so compute it modulo $10^9 + 7$. Writing $a \bmod x$ for the remainder of $a$ divided by $x$,

$(a \times b) \bmod x = \{(a \bmod x) \times (b \bmod x)\} \bmod x$

holds. The remainders of two integers modulo 1,000,000,007 are therefore enough to compute the remainder of their product.

So multiplying $A$ by itself $X$ times looks like it would work. When $X$ grows into the range of a 64 bit integer, multiplying one factor at a time takes far too long to finish. Reduce the number of multiplications like this.

1. Compute $A^1, A^2, A^4, A^8, \dots$ in order. Each number is the square of the previous one, and stopping as soon as the exponent would pass $X$ is enough. Since $X$ stays inside a 64 bit integer, fewer than 64 numbers are computed.
2. Now write $X$ in binary. For $X = 11$, $11 = 1 + 2 + 8$, and by the law of exponents $A^{11} = A^{1+2+8} = A^1 \times A^2 \times A^8$. Multiplying a few of the numbers from step 1 gives $A^X$.

Multiplying one factor at a time costs time proportional to $X$, while the method above costs time proportional to $\log X$. Write a program that computes $A^X$ modulo $10^9 + 7$.

The first line contains an integer $A$. ($1 \le A \le 10^{18}$)

The second line contains an integer $X$. ($1 \le X \le 10^{18}$)

Print $A^X$ modulo 1,000,000,007 on one line.