인코딩 좌표

상근이는 테러리스트의 전화를 도청하다가 큰 공격이 예고되었다는 사실을 알아냈다. 테러리스트는 인코딩한 좌표를 서로 주고받고 있고, 공격은 그 좌표 중 한 곳에서 일어난다. 상근이는 좌표를 가로채는 데 성공했다.

좌표는 x좌표와 y좌표로 나누어지며, 두 값 모두 소수 $P$보다 작은 음이 아닌 정수이다. x좌표와 y좌표는 각각 인코딩되고, 인코딩 방법은 서로 같다.

좌표 하나를 인코딩하려면 $A$, $B$, $C$, $K$, $N$이 필요하다. 인코딩 과정은 다음 세 함수로 나타낸다.

• $F(n+1) = G(n) + H(n)$
• $G(n+1) = K \times F(n) + H(n-1)$
• $H(n+1) = F(n) + K \times G(n)$

$A$, $B$, $C$는 함수의 초깃값이다.

• $F(1) = A$
• $G(1) = B$
• $H(1) = C$

좌표는 $F(N) \bmod P$가 된다.

위 과정에는 아주 중요한 정보가 하나 빠져 있다. $G(2)$를 계산하려면 $H(0)$이 필요한데, $H(0)$을 알아낼 방법이 없다. $H(0)$에 대해 아는 것은 x좌표와 y좌표를 계산할 때 같은 $H(0)$을 쓴다는 사실뿐이다. $H(0)$ 역시 $P$보다 작은 음이 아닌 정수이다.

상근이는 우연히 x좌표를 디코딩하지 않고 얻었다. x좌표로 $H(0)$을 구한 다음 y좌표를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개보다 많지 않다.

각 테스트 케이스는 네 줄이다. 첫째 줄에 소수 $P$ ($2 \le P \le 19997$)가 주어진다. 둘째 줄에 x좌표를 인코딩하는 데 쓴 $A_x$, $B_x$, $C_x$, $K_x$, $N_x$가 주어진다 ($0 \le A_x, B_x, C_x, K_x < P$, $1 \le N_x \le 10^9$). 셋째 줄에 y좌표를 인코딩하는 데 쓴 $A_y$, $B_y$, $C_y$, $K_y$, $N_y$가 주어진다 ($0 \le A_y, B_y, C_y, K_y < P$, $1 \le N_y \le 10^9$). 넷째 줄에 가로챈 x좌표 ($0 \le x < P$)가 주어진다.

가로챈 x좌표는 실제로 인코딩해서 나온 값이므로, 그 x좌표를 만드는 $H(0)$이 적어도 하나 있다.

각 테스트 케이스마다 y좌표를 한 줄에 출력한다. 주어진 x좌표를 만드는 $H(0)$이 여러 개이고 그중에서 y좌표가 두 가지 이상 나오면, y좌표 대신 UNKNOWN을 출력한다.