AT_arc216_d [ARC216D] GCD of Product of Arithmetic Progression

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.

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 $ T $ lines. The $ i $ -th line should contain the answer to $ \mathrm{case}_i $ .

### Sample Explanation 1 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 $ . ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 1 \leq N, B, C, D \leq 10^6 $ - All input values are integers.