SP13945 GHALIBC - GHALIBS CHALLENGE

“每件事你都要问‘你究竟是什么？’ 你自己说说，这种谈话方式是什么？” 这段诗句体现了加利布的智慧与难以挑战的才华。加利布是一位伟大的诗人，备受皇帝推崇，而这让一些贵族心生不满。于是，他们设下一个考验，想借此降低加利布在皇帝心中的影响力。 贵族们准备了 $n$ 个袋子，第一个袋子里有 $1$ 个弹珠，第二个袋子有 $2$ 个弹珠，依此类推。每个弹珠的半径都是唯一的，从 $1$ 到 $i$，其中 $i$ 是袋子的编号。加利布需要计算出所有这些弹珠在各自袋子中的排列方式，并将其累加。 加利布向国王抱怨任务过于困难，于是国王决定简化任务：已知 $(n+1)$ 仅被一个素数 $p$ 整除（即 $(n+1)=p^a$），加利布只需计算袋子大小满足 $r \mod (p-1)$ 并且 $\frac{p+1}{2} \le r \le p-1$ 的情况。此外，任何包含三个长度递增的弹珠子序列的排列方式都不计入。 加利布仍觉得这个任务过难，因此向你寻求帮助。由于答案可能很大，请输出答案对 $p \times p$ 取模后的结果。

第一行是一个整数 $t$ ($1 \le t \le 10$)，表示测试用例的数量。 接下来的 $t$ 行，每行包含三个整数 $r, p, a$，如题目所述。 满足 $\frac{p+1}{2} \le r \le p-1$ $5 \le p \le 1000$ $1 \le a \le 10^8$

对于每个测试用例，输出最终答案对 $p \times p$ 取模的结果。 **本翻译由 AI 自动生成**