Phibonacci Batch Compilation commands

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

피보나치 수와 x² = x + 1의 두 근 중 하나인 황금비 는 매우 연관이 깊은 수이다. 이에 관한 예를 들자면 피보나치 수의 일반항을 로 나타낼 수 있다는 점 등이 있다. 이제 φ를 이용해 파이보나치(Phibonacci) 수를 아래의 점화식으로 정의하고자 한다.

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

입력 형식

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

쉬운 문제에서는 k = 1인 입력이 주어진다.

어려운 문제에서는 1 ≤ k ≤ 10¹²인 입력이 주어진다.

출력 형식

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

예제 입력	예제 출력
5 1	5 3
3 2	8 1000000004

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