빠른 거듭제곱

두 정수 $A$와 $X$가 주어질 때 $A^X$를 구하는 방법을 생각해 보자. 이 값은 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다. $a \bmod x$를 $a$를 $x$로 나눈 나머지라고 하면

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

가 성립한다. 두 정수를 1,000,000,007로 나눈 나머지만 알아도 두 수를 곱한 값의 나머지를 계산할 수 있다는 뜻이다.

그렇다면 $A$를 $X$번 곱해서 $A^X$를 구하면 될 것처럼 보인다. 그러나 $X$가 64비트 정수 범위까지 커지면 하나씩 곱하는 방식으로는 답을 얻는 데 걸리는 시간이 지나치게 길다. 그래서 곱셈 횟수를 다음과 같이 줄인다.

1. 먼저 $A^1, A^2, A^4, A^8, \dots$을 차례로 계산한다. 각 수는 바로 앞의 수를 제곱해서 얻고, 지수가 $X$를 넘지 않는 시점까지만 계산하면 충분하다. $X$가 64비트 정수 범위이므로 계산하는 수는 64개보다 적다.
2. 이제 $X$를 이진수로 나타낸다. 예를 들어 $X = 11$이면 $11 = 1 + 2 + 8$이고, 지수법칙에 따라 $A^{11} = A^{1+2+8} = A^1 \times A^2 \times A^8$이 성립한다. 1번 단계에서 미리 계산해 둔 수 몇 개만 곱하면 $A^X$가 나온다.

$A$를 하나씩 곱하면 시간이 $X$에 비례하지만, 위 방법을 쓰면 $\log X$에 비례한다. $A^X$를 $10^9 + 7$로 나눈 나머지를 구하는 프로그램을 작성하라.

첫째 줄에 정수 $A$가 주어진다. ($1 \le A \le 10^{18}$)

둘째 줄에 정수 $X$가 주어진다. ($1 \le X \le 10^{18}$)

$A^X$를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.