Α Batch Compilation commands

음이 아닌 두 정수 $A, X$가 있을 때 $A^{X}$을 구하는 방법을 생각해보자. 물론 이 수는 매우 클 수 있기에, $1,000,000,007$ ($= 10^{9} + 7$)로 나눈 나머지를 구할 것이다. $a mod x$를 $a$를 $x$로 나눴을 때의 나머지라고 표현하면,

(a × b) mod x = {(a mod x) × (b mod x)} mod x

가 성립하기 때문에, 어떤 두 정수를 $1,000,000,007$로 나눈 나머지만 알고 있어도 그 두 정수의 곱을 $1,000,000,007$로 나눈 나머지를 쉽게 계산할 수 있다.

본 문제로 돌아가서, 그렇다면 이제 $A$를 $X$번 곱하면 $A^{X}$을 쉽게 구할 수 있을 것 같아 보인다. 그러나 안타깝게도 $X$가 상당히 커서 64비트 정수의 범위에 있다면 $A$를 하나하나씩 곱하는 방식으로는 상상할 수 없을 정도로 긴 시간이 흘러야 답을 찾을 수 있을 것이다. 그래서 다음과 같이 곱셈의 횟수를 줄이는 방법을 사용한다.

1. 먼저 $A^{1}$, $A^{2}$, $A^{4}$, $A^{8}$, ...을 순서대로 계산한다. 각 수는 이전에 있는 수를 제곱함으로써 계산할 수 있고, 지수가 $X$를 딱 넘지 않을 시점까지만 계산하면 충분할 것이다. $X$가 64비트 정수의 범위에 있으므로 계산하는 수는 64개보다 작을 것이다.
2. 이제 $X$를 이진수로 나타내 보자. 예를 들어 $X$를 $11$로 두면, $X = 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}$를 구하는 프로그램을 작성하라.

입력

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

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

출력

$A^{X}$을 출력한다. 이 수는 매우 커질 수 있으므로 $1,000,000,007$로 나눈 나머지를 출력해야 한다.

입출력 예제

예제 1

입력

3
3

출력

27

예제 2

입력

100
100

출력

424090053