时间限制： 2.0 秒

空间限制： 512 MB

题目描述

定义 $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}$ 的值。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $Q$，表示数据组数，保证 $1 \le Q \le 10$。

输入的接下来 $Q$ 行每行包含四个非负整数 $R, P, N, K$，保证 $1 \le R \le 3,~2 \le P \le 998,244,353,~1 \le N \lt P,~0 \le K \lt 10^5$，且保证 $P$ 为质数。

输出格式

输出到标准输出。

输出一共有 $Q$ 行，每行对应一个询问的答案。

3
2 7 5 3
1 17 9 4
3 29 23 9

2907
490656
480228738

子任务

保证所有数据满足 $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 分）：无特殊情况。