/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 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) で定義します．
a_0,a_1,a_2,\ldots,a_N の最大公約数を 998244353 で割った余りを求めてください．
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
1 つ目のテストケースについて，(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 です．
Score : 1000 points
Problem Statement
You are given positive integers N, B, C, D.
For a non-negative integer k, define the integer a_k as the product of all terms of an arithmetic sequence with first term Bk + C, common difference D, and N terms; that is, a_k = (Bk+C)(Bk+C+D)(Bk+C+2D)\dots(Bk+C+(N-1)D).
Find the greatest common divisor, modulo 998244353, of a_0, a_1, a_2, \ldots, a_N.
You are given T test cases; solve each of them.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq N, B, C, D \leq 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N B C D
Output
Output T lines. The i-th line should contain the answer to \mathrm{case}_i.
Sample Input 1
3 3 1 1 1 4 2 2 6 2026 3 22 216
Sample Output 1
6 128 114347907
For the first test case, (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), and their greatest common divisor is 6.