Little Cyan Fish қайтадан орын ауыстыруларды санап жатыр.

Little Cyan Fish-те $n$, $k$ және $S$ деген үш бүтін сан бар. Ұзындығы $n$ болатын орын ауыстыру — $1$-ден $n$-ге дейінгі әрбір бүтін санды дәл бір рет қамтитын тізбек. Егер $1 \le i \le n - 2$ және $p_i + p_{i+1} \le S$ болса, Little Cyan Fish $i$ индексін жақсы деп атайды.

Дәл $k$ жақсы индексі бар, ұзындығы $n$ болатын $p$ орын ауыстыруларының санын табыңыз. Жауап үлкен болуы мүмкін болғандықтан, оны $998\,244\,353$ модулі бойынша шығарыңыз.

Кіріс деректер

Бірнеше тест жағдайлары бар. Кіріс деректердің бірінші жолында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 1000$) берілген.

Әрбір тест жағдайы үшін бірінші жолда $n$, $k$ және $S$ ($1 \le k \le n \le 10^5$, $1 \le S \le 2n - 1$) деген үш бүтін сан берілген.

Барлық тест жағдайлары бойынша $n$ сандарының қосындысы $10^5$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін бір жолда бір бүтін санды — дәл $k$ жақсы индексі бар орын ауыстырулар санын $998\,244\,353$ модулі бойынша шығарыңыз.

Мысалдар

Кіріс деректер 1

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

Шығыс деректер 1

2
4
12
10
0
0

Ескертпе

Бірінші тест жағдайында екі орын ауыстыру — $[1, 2, 3]$ және $[2, 1, 3]$.

Екінші тест жағдайында төрт орын ауыстыру — $[1, 2, 3]$, $[2, 1, 3]$, $[1, 3, 2]$ және $[3, 1, 2]$.

Бесінші және алтыншы тест жағдайларында $1 \le i \le n - 2$ шартын қанағаттандыратын индекстер саны $k$-дан аз, сондықтан жауап $0$ болады.