分数: 1000 点
问题陈述
给你正整数 N, B, C, D.
对于非负整数 k,定义整数 a_k 作为算术序列的所有项与第一项的乘积 Bk + C,共同差异 D,和 N 条款;也就是说, a_k = (Bk+C)(Bk+C+D)(Bk+C+2D)\dots(Bk+C+(N-1)D).
求最大公约数,模 998244353,属于 a_0, a_1, a_2, \ldots, a_N.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 10^5
- 1 \leq N, B, C, D \leq 10^6
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N B C D
输出
输出 T 行。的 i- 第行应包含以下问题的答案 \mathrm{case}_i.
示例输入 1
3 3 1 1 1 4 2 2 6 2026 3 22 216
示例输出 1
6 128 114347907
对于第一个测试用例, (a_0, a_1, a_2, a_3) = (1 \times 2 \times 3, 2 \times 3 \times 4, 3 \times 4 \times 5, 4 \times 5 \times 6) = (6, 24, 60, 120),它们的最大公约数是 6.