注意

Writer による想定解の PyPy3 実装の実行時間は約 2,200 ms です。

問題文

$n$ 個の宝石があり、$i\ (1\leq i\leq n)$ 番目の宝石の美しさは $A _ i$ で価値は $W _ i$ です。$A _ i$ と $W _ i$ はいずれも正の整数です。

suisen 君は $n$ 個の宝石から $1$ 個以上 を選んで指輪を作ります。suisen 君には好きな正整数 $m$ があり、作られた指輪の価値は次のように定まります。

• $i _ 1, i _ 2, \ldots, i _ k\ (1 \leq i _ 1 \lt i _ 2 \lt \cdots \lt i _ k \leq n)$ 番目の宝石を選んだとして、
  • $\mathrm{lcm}(A _ {i _ 1}, A _ {i _ 2}, \ldots, A _ {i _ k}) = m$ のとき、指輪の価値は $\displaystyle\prod _ {j = 1} ^ k W _ {i _ j}$ である。
  • $\mathrm{lcm}(A _ {i _ 1}, A _ {i _ 2}, \ldots, A _ {i _ k}) \neq m$ のとき、指輪の価値は $0$ である。
  ここで、$k\ (\geq 1)$ 個の正整数 $x _ 1, x _ 2, \ldots, x _ k$ に対して、$\mathrm{lcm}(x _ 1, x _ 2, \ldots, x _ k)$ を、全ての $x _ 1, x _ 2, \ldots, x _ k$ で割り切れる最小の正整数と定義します。

suisen 君が作り得る全ての指輪の価値の総和を $998244353$ で割った余りを求めてください。より形式的には、次の値を求めてください。

$$ \left(\sum _ {k = 1} ^ n \sum _ {\overset{\scriptstyle 1 \leq i _ 1 \lt i _ 2 \lt \cdots \lt i _ k \leq n,}{\mathrm{lcm}(A _ {i _ 1}, A _ {i _ 2}, \ldots, A _ {i _ k}) = m}} \prod _ {j = 1} ^ k W _ {i _ j}\right) \bmod 998244353. $$

$T$ 個のテストケースが与えられるので、その全てについて上記の問題を解いてください。ただし、$T$ 個のテストケースで $m$ の値は共通です。

入力

入力は以下の形式で標準入力から与えられます。

まず $1$ 行目にテストケースの個数 $T$ および $T$ 個のテストケースで共通の正整数 $m$ が与えられます。

$T\ m$

各テストケースは次の形式で $2$ 行にわたって与えられます。$W$ は陽には与えられないことに注意してください。

$n\ B\ C\ D$
$A _ 1\ A _ 2\ \cdots\ A _ n$

このテストケースにおける $W = (W _ 1, W _ 2, \ldots, W _ n)$ は次のように定義されます。

$$ W _ i = \begin{cases} B & \text{if }i=1, \newline C \cdot W _ {i - 1} + D & \text{if }i = 2, 3, \ldots, n. \end{cases} $$

• 入力は全て整数で与えられる
• $1\leq T\leq 1000$
• $1\leq n\leq 5\times 10 ^ 5$
• $1\leq m\leq 10 ^ {18}$
• $1\leq A _ i \leq 10 ^ {18}$
• $0\leq B,C,D \lt 998244353$
• $T$ 個のテストケースにわたる $n$ の総和は $5\times 10 ^ 5$ 以下

入力量が非常に多い可能性があることに注意してください。

出力

$i\ (1\leq i\leq T)$ 行目には $i$ 個目のテストケースの答えを出力してください。最後のテストケースに対する答えを出力した後も改行してください。

サンプル

3 20
6 1 1 1
1 5 2 4 7 10
1 1 2 3
1
20 141421356 173205080 22360679
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

640
0
747444483

1 1
1 1 1 1
1

1