Little Cyan Fish compte à nouveau des permutations.

Little Cyan Fish possède trois entiers $n$, $k$ et $S$. Une permutation de longueur $n$ est une séquence contenant chaque entier de $1$ à $n$ exactement une fois. Little Cyan Fish qualifie un indice $i$ de bon si $1 \le i \le n - 2$ et $p_i + p_{i+1} \le S$.

Trouvez le nombre de permutations $p$ de longueur $n$ qui possèdent exactement $k$ bons indices. Comme la réponse peut être grande, affichez-la modulo $998\,244\,353$.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T \le 1000$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient trois entiers $n$, $k$ et $S$ ($1 \le k \le n \le 10^5$, $1 \le S \le 2n - 1$).

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un seul entier, indiquant le nombre de permutations qui possèdent exactement $k$ bons indices, modulo $998\,244\,353$.

Exemples

Entrée 1

6
3 1 3
3 1 4
4 1 4
4 2 5
3 2 5
1 1 1

Sortie 1

2
4
12
10
0
0

Remarque

Dans le premier cas de test, les deux permutations sont $[1, 2, 3]$ et $[2, 1, 3]$.

Dans le deuxième cas de test, les quatre permutations sont $[1, 2, 3]$, $[2, 1, 3]$, $[1, 3, 2]$ et $[3, 1, 2]$.

Dans les cinquième et sixième cas de test, il y a moins de $k$ indices satisfaisant $1 \le i \le n - 2$, donc la réponse est $0$.