파이보나치

피보나치 수는 다음 점화식으로 정의되는 수열이다.

$F_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F_{n-1} + F_{n-2} & n > 1 \end{cases}$

피보나치 수는 $x^2 = x + 1$의 두 근 중 하나인 황금비 $\varphi = \frac{\sqrt{5}+1}{2}$와 관계가 깊다. 일반항을 $F_n = \frac{\varphi^n - (1 - \varphi)^n}{\sqrt{5}}$로 쓸 수 있다는 점이 그런 예다. 이제 $\varphi$로 파이보나치 수를 다음 점화식으로 정의한다.

$P_n = \begin{cases} 1 & n = 0 \\ \varphi & n = 1 \\ P_{n-1} + P_{n-2} & n > 1 \end{cases}$

$F_{-1} = 1$로 두면 $n \ge 0$에서 $P_n = F_n \varphi + F_{n-1}$이 성립한다. 여기서 묻는 것은 $(P_n)^k$를 두 정수 $A$, $B$로 $A \varphi^k + B$ 꼴로 나타낼 수 있는지다. 나타낼 수 있으면 $A$와 $B$를 출력하고, 불가능하면 -1을 출력하라.

첫째 줄에 두 정수 $n$과 $k$가 공백으로 구분되어 주어진다.

$0 \le n \le 10^{12}$, $1 \le k \le 10^{12}$이다.

첫째 줄에 $(P_n)^k = A \varphi^k + B$를 만족하는 두 정수 $A$, $B$를 각각 1,000,000,007로 나눈 나머지를 공백으로 구분해 출력한다. 그런 두 정수가 없으면 -1을 출력한다.

$n = 3$, $k = 2$인 경우 $(P_3)^2 = (2\varphi + 1)^2 = 4\varphi^2 + 4\varphi + 1 = 8\varphi^2 - 3$이다. $-3$을 1,000,000,007로 나눈 나머지가 1,000,000,004이다.