P1025万象启星环（circum）

【题目背景】

越过万山的货物终于抵达星尘镇，其中装载着修复古老防护装置星环所需的全部部件。tfbz 与 Ehundategh 完成装配后，还需要按照星环留下的规则注入能量，才能让它重新照亮整座城镇。

【题目描述】

启动星环需要依次完成 $n$ 次能量注入。第 $i$ 次注入时，可以从 $1$ 至 $m$ 中选择一个整数 $x_i$ 作为本次注入的能量值；全部注入结束后，依次选择的能量值形成一个长度为 $n$ 的有序序列 $(x_1,x_2,\cdots,x_n)$。

星环具有固定的能量周期 $p$。每次注入的能量都会沿着星环向前传递；如果 $\sum_{i=1}^{n}x_i$ 不是 $p$ 的倍数，最后留下的能量便无法与最初的能量衔接，整次循环也会因此中断。

仅仅让能量完成循环仍不足以启动星环。沉睡的核心必须由质数能量唤醒：如果 $x_1,x_2,\cdots,x_n$ 中没有任何一个质数，即使能量顺利循环，星环依然不会发出光芒。

因此，tfbz 需要依次从 $1$ 至 $m$ 中选择 $n$ 个能量值，使它们的总和是 $p$ 的倍数，并保证其中至少有一个质数。星环将每一种能够成功启动核心的有序注入方案记录为一个启星序列；只要某一次注入的能量值不同，或相同能量值出现的次序不同，就会被记录为不同的方案。

tfbz 想知道，一共有多少个不同的启星序列。由于答案可能很大，请将答案对 $998{,}244{,}353$ 取模后输出。

【输入格式】

从文件 $\textbf{\textit{circum.in}}$ 中读入数据。

第一行一个正整数 $T$，表示测试数据的组数。

对于每组测试数据，一行三个正整数 $n,m,p$，分别表示能量注入次数、每次注入的最大能量值和星环的能量周期。

【输出格式】

输出到文件 $\textbf{\textit{circum.out}}$ 中。

对于每组测试数据，输出一行一个整数，表示启星序列的数量对 $998{,}244{,}353$ 取模后的结果。

【样例 1 输入】

1323 5 332 2 141 1 1

【样例 1 输出】

1332330

【说明/提示】

【样例 2】

见选手目录下的 $\textbf{\textit{circum/circum2.in}}$ 和 $\textbf{\textit{circum/circum2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{circum/circum3.in}}$ 和 $\textbf{\textit{circum/circum3.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{circum/circum4.in}}$ 和 $\textbf{\textit{circum/circum4.ans}}$。

该组样例符合测试点 $9\sim 14$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{circum/circum5.in}}$ 和 $\textbf{\textit{circum/circum5.ans}}$。

该组样例符合测试点 $15\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证：$1\leq T\leq 10$，$1\leq n\leq 10^9$，$1\leq m\leq 2\times 10^7$，$1\leq p\leq 100$，单个测试点内 $\sum m\leq 2\times 10^7$。