Problem Statement

Find the number, modulo $998244353$, of arithmetic sequences $A=(A_1, \cdots, A_N)$ of length $N$ that satisfy all of the following conditions.

• For every integer $i$ satisfying $1\leq i\leq N-1$, $A_i$ is an integer between $0$ and $M$, inclusive.
• $A_N$ is an integer between $L$ and $R$, inclusive.

Input

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

$N\ M\ L\ R$

All input values are integers and satisfy the following constraints.

• $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$

Output

Print $T$ lines. The $i$-th line should contain the answer to the $i$-th test case. Print a newline at the end.

Sample

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

6
866938593
1