U413249 初等数论

**时间限制：** 2.0 秒 **空间限制：** 512 MB **提交前的提醒：** 本题的最暴力做法（即外层 $i$ 做 $1\sim N$ 的循环，内层使用双重循环暴力枚举求 $f(i,R,P)$ ） 在子任务 1 的限制下也会超时。提交该做法只会获得 0 分的反馈结果并且浪费评测资源。所以我们建议**不要提交该做法**。

定义 $f(i,R,P)$ 为满足 $a^R \times (b^2 + b)^i = b^i \pmod P$ 且 $0 \le a, b \lt P$ 的 $(a,b)$ 数对的个数。 一共有 $Q$ 组询问，每组询问中输入 $R, P, N, K$，要求计算出 $\sum_{i=1}\limits^N i^K \times f(i,R,P) \pmod {998,244,353}$ 的值。

无

无

### 子任务 保证所有数据满足 $1 \le Q \le 10,~1 \le R \le 3,~2 \le P \le 998,244,353,~1 \le N \lt P,~0 \le K \lt 10^5$，且保证 $P$ 为质数。 子任务 1（11 分）：保证 $P\le 300$ 。 子任务 2（14 分）：保证 $R\le 2,P\le 5000$ 。 子任务 3（15 分）：保证 $K=0$ 且如果 $R=3$，那么 $P$ 满足 $P\bmod 3\ne 1$ 。 子任务 4（17 分）：保证 $R\le 1$ 。 子任务 5（19 分）：保证 $K=0$ 。 子任务 6（24 分）：无特殊情况。