행렬 거듭제곱

2×2 정수 행렬 M이 주어진다. M^N mod (10^9+7)을 구하라. N이 최대 10^18이므로 분할 정복으로 O(log N)에 구현하라.

N이 짝수이면 M^N = (M^(N/2))^2, 홀수이면 M^N = M × M^(N-1)로 재귀한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 10^18)

둘째 줄부터 두 줄에 걸쳐 2×2 행렬이 주어진다. (각 원소는 0 이상 1,000 이하의 정수)

출력

M^N mod (10^9+7)을 2×2 행렬로 출력하라. 각 행을 한 줄에 공백으로 구분하여 출력한다.

예제 입력 1

2
1 2
3 4

예제 출력 1

7 10
15 22