SP16956 ENCODE - Encoded Coordinates

你正在密切关注一个恐怖组织，他们准备在附近发动一次重大袭击。恐怖分子之间一直在采用加密的方式传递坐标信息，你怀疑这些坐标中的某一个就是袭击的具体地点。你已经截获了与这些潜在位置相关的通信，急需解码并分析。每个位置都有其特定的 $x$ 和 $y$ 坐标值，这些坐标都是小于某个素数 $P$ 的非负整数。两种坐标的编码过程完全一样，而其中一个线索来源为你提供了关于解码单个坐标的流程。 这个解码流程需要的输入有五个数值：$A$、$B$、$C$、$K$ 和 $N$。流程围绕三个互相关联且依赖于 $K$ 的函数展开： $$ F(n + 1) = G(n) + H(n) $$ $$ G(n + 1) = K \cdot F(n) + H(n - 1) $$ $$ H(n + 1) = F(n) + K \cdot G(n) $$ 这些函数通过 $A$、$B$ 和 $C$ 来初始化，具体为： $$ F(1) = A, \quad G(1) = B, \quad H(1) = C $$ 你所需得到的解码坐标是 $F(N) \mod P$ 的结果。你可能注意到，为了计算 $G(2)$，你还缺少一个关键信息：$H(0)$ 的值。虽然你不知道这个值，但是你知道 $x$ 和 $y$ 的坐标使用的是相同的 $H(0)$。好消息是，你已经成功解码了这些地点的 $x$ 坐标。虽然你的同事们认为这些信息不足以推算出 $y$ 坐标，但你想证明他们错了。

第一行是一个正整数，表示测试用例的数量，最多为 100。以下是每个测试用例的格式： - 一行，一个素数 $P$，满足 $2 < P < 10^9$。 - 一行，五个空格分隔的整数：$A_x$、$B_x$、$C_x$、$K_x$ 和 $N_x$，所有数值均在 $0$ 到 $P-1$ 之间。 - 一行，五个空格分隔的整数：$A_y$、$B_y$、$C_y$、$K_y$ 和 $N_y$，所有数值均在 $0$ 到 $P-1$ 之间。 - 一行，一个整数 $x$，满足 $0 \leq x < P$。

对于每个测试用例，输出一行，表示计算出的 $y$ 坐标。如果实际上无法唯一确定一个有效的 $y$ 坐标，则输出 `UNKNOWN`。

- $2 < P < 10^9$ - $0 \leq A_x, B_x, C_x, K_x, N_x < P$ - $0 \leq A_y, B_y, C_y, K_y, N_y < P$ - $0 \leq x < P$ **本翻译由 AI 自动生成**