問題文

以下の条件を全て満たす長さ $N$ の等差数列 $A=(A_1, \cdots, A_N)$ の総数を $998244353$ で割った余りを求めてください。

• $1\leq i\leq N-1$ を満たすすべての整数 $i$ に対して、$A_i$ は $0$ 以上 $M$ 以下の整数
• $A_N$ は $L$ 以上 $R$ 以下の整数

入力

$T$
$case_1$
$\vdots$
$case_T$

$N\ M\ L\ R$

入力は全て整数で以下の制約を満たす。

• $1\leq T\leq 10^5$
• $2\leq N \leq 10^{18}$
• $0\leq M \leq 10^{18}$
• $0\leq L \leq R \leq M$

出力

$T$ 行出力してください。$i$ 行目には $i$ 番目のテストケースに対する答えを出力してください。最後に改行してください。

サンプル

3
3 5 2 3
2 1000000000000000000 0 1000000000000000000
1000000000000000000 0 0 0

6
866938593
1