피보나치(Fibonacci) 수는 아래의 점화식으로 정의되는 수열이다.</p>

[F_n = \begin{cases} 0 & \textrm{if}\;n =0; \ 1 & \textrm{if}\;n =1; \ F_{n-1} + F_{n-2} & \textrm{if}\; n > 1.\end{cases}]

피보나치 수와 (x^2 = x + 1)의 두 근 중 하나인 황금비 (\varphi = \frac{\sqrt{5}+1}{2})는 매우 연관이 깊은 수이다. 이에 관한 예를 들자면 피보나치 수의 일반항을 (F_n = \frac{\varphi^n - \left(1-\varphi \right)^n}{\sqrt{5}})로 나타낼 수 있다는 점 등이 있다. 이제 (\varphi)를 이용해 파이보나치(Phibonacci) 수를 아래의 점화식으로 정의하고자 한다.

[P_n = \begin{cases} 1 & \textrm{if}\;n =0; \ \varphi & \textrm{if}\;n =1; \ P_{n-1} + P_{n-2} & \textrm{if}\; n > 1.\end{cases}]

편의를 위해 (F_{-1} = 1)이라고 하면, 놀랍게도 (P_n = F_n\varphi + F_{n-1} \left(n \ge 0 \right))로 나타낼 수 있다! 이제 우리가 관심 있는 것은 (\left(P_n\right)^k)를 두 정수 (A), (B)를 이용해 (A \varphi^k + B) 꼴로 표현할 수 있느냐는 것이다. 표현 가능하다면, (A)와 (B)를 출력하고, 불가능하다면 -1을 출력하라.

입력 형식

첫 번째 줄에 두 정수 (n) (0 ≤ (n) ≤ 10¹²), (k)가 공백으로 구분되어 주어진다.</p>

1 ≤ (k) ≤ 10¹²인 입력이 주어진다

출력 형식

첫 번째 줄에 (\left(P_n\right)^k = A \varphi^k + B)가 되는 두 정수 (A), (B)를 1,000,000,007로 나눈 나머지를 공백으로 구분하여 출력한다. 만약 이런 두 정수가 존재하지 않는 경우 -1을 출력한다

예제 입력 1

5 1

예제 출력 1

5 3

예제 입력 2

3 2

예제 출력 2

8 1000000004

힌트

두 번째 예제의 경우 (\left(P_3\right)^2 = \left(2 \varphi + 1\right)^2 = 4 \varphi^2 + 4\varphi + 1 = 8\varphi^2-3)이며, -3을 1,000,000,007로 나눈 나머지는 1,000,000,004이므로, 위와 같은 출력이 나온다.