题目描述

Shekhu 教授今天又给 Akki 出了一个难题。他给了 Akki 三个正整数 $A$、$N$ 和 $P$，要求他计算 $A^{N!}$ 除以 $P$ 的余数。和往常一样，$N!$ 表示前 $N$ 个正整数的乘积。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行，每行包含三个整数 $A$、$N$ 和 $P$，含义如上所述。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是答案。

2
2 1 2
3 3 2

Case #1: 0
Case #2: 1

提示

在样例 $1$ 中，答案为 $2^{1!} = 2$ 除以 $2$ 的余数，即 $0$。

在样例 $2$ 中，答案为 $3^{3!} = 3^6 = 729$ 除以 $2$ 的余数，即 $1$。

限制条件

$1 \le T \le 100$。

小数据集（测试集 1 – 可见）

$1 \le A \le 10$。

$1 \le N \le 10$。

$1 \le P \le 10$。

大数据集（测试集 2 – 隐藏）

$1 \le A \le 10^5$。

$1 \le N \le 10^5$。

$1 \le P \le 10^5$。

翻译由 DeepSeek V4 Pro 完成