Phibonacci

The Fibonacci numbers are defined by the recurrence below.

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

The Fibonacci numbers are closely tied to the golden ratio $\varphi = \frac{\sqrt{5}+1}{2}$, one of the two roots of $x^2 = x + 1$. One example of that tie is the closed form $F_n = \frac{\varphi^n - (1 - \varphi)^n}{\sqrt{5}}$. Now use $\varphi$ to define the Phibonacci numbers by the recurrence below.

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

If you set $F_{-1} = 1$, then $P_n = F_n \varphi + F_{n-1}$ holds for every $n \ge 0$. The question here is whether $(P_n)^k$ can be written as $A \varphi^k + B$ for two integers $A$ and $B$. If it can, print $A$ and $B$. If it cannot, print -1.

The first line contains two integers $n$ and $k$, separated by a space.

The bounds are $0 \le n \le 10^{12}$ and $1 \le k \le 10^{12}$.

On the first line, print the two integers $A$ and $B$ with $(P_n)^k = A \varphi^k + B$, each taken modulo 1,000,000,007 and separated by a space. If no such pair of integers exists, print -1.

For $n = 3$ and $k = 2$, $(P_3)^2 = (2\varphi + 1)^2 = 4\varphi^2 + 4\varphi + 1 = 8\varphi^2 - 3$. The remainder of $-3$ modulo 1,000,000,007 is 1,000,000,004.