SP9972 SKEY - The SKey

这是第 10 届 ACM 埃及国家编程竞赛的赛题，首席裁判 Mostafa S. 正在准备题目集。在过去几年里，首席裁判通常会要求出题人用他的公钥加密数据，以保持题目的安全。然而，不幸的是，RSA 算法在两周前被攻破了。为此，Mostafa 决定临时设计一个新算法，以应对这一情况，直到有人找到一种新的强加密和解密方法。找到算法后，Mostafa 向裁判们介绍了这个新加密算法，并提供了一个生成算法所需密钥的公式。密钥通过以下公式生成： $$\text{SKEY} = \left(M \times \sum_{k=0}^{N} \frac{1}{A^k}\right) \bmod P$$ 其中 $A$、$N$ 和 $P$ 是整数，$P$ 是一个素数，并且与 $A$ 互质（即 $\gcd(A, P) = 1$）。此外，$M$ 是一个非常大的数，生成时确保它能被 $P$ 整除。举个例子：假设 $A = 3$，$N = 2$，$P = 7$ 和 $M = 18$，那么 skey 的计算结果是： $$(18 \times (1/1 + 1/3 + 1/9)) \bmod 7 = 26 \bmod 7 = 5$$ 因为 $M$ 很大，在裁判之间通过电子邮件交流时直接发送是不太现实的。不过，模运算有一个简便的性质：$(A \times B) \bmod X = ((A \bmod X) \times (B \bmod X)) \bmod X$。因此，我们可以用 $M \bmod P$ 来代替 $M$ 进行计算。 现在，给定 $A$、$N$、$P$ 和 $M \bmod P$，请帮助首席裁判用编程计算出 SKey。

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来的每一行给出 4 个整数 $A$、$N$、$P$ 和 $M \bmod P$。

对于每个测试用例，按格式输出一行，形如 **“Case K: SKey”**，其中 $K$ 是测试用例的编号，SKey 是根据题目描述计算的结果。请参考示例输入输出来理解格式。

- $1 \leq T \leq 100$ - $1 \leq A, N, P \leq 10^5$ - $1 \leq M \mod P < P$ ## 示例输入 ``` 1 3 2 7 4 ``` ## 示例输出 ``` Case 1: 5 ``` **本翻译由 AI 自动生成**