Background

What comes into view is a huge cherry blossom tree.

Under the tree stands a girl, looking up at it.
I think: She is probably a freshman. Maybe, like me, she also sneaked out.
I also look up at that cherry blossom tree. The blurry colors of the blossoms cover the sky.
A gust of wind rises, and the dancing cherry blossom petals wrap around the girl.
The girl also sees me...

Problem Description

That was your first encounter with Milja.

As always, Milja gives you another sequence problem.
The white envelope carries a scent of citrus,
and you carefully open it and read.

In 3D, we have a cube.
The coordinates of its $2^3$ vertices can all be written in the form $(x,y,z)$.

Similarly, in $n$ dimensions, we have an $n$-dimensional hypercube with $2^n$ vertices.
Its edge length is $1$, and every coordinate of every vertex is a non-negative integer.

Starting from the point $(0,0,\dots,0)$, you walk along $m$ edges. Find the total number of ways to arrive at the point $(1,1,\dots,0)$.

Among the coordinates of the destination point, there are $l$ digits equal to $1$.

Since the answer may be very large, you only need to output the result modulo $998244353$.

Input Format

The first line contains an integer $T$, which denotes the number of test cases.

The next $T$ lines each contain three non-negative integers $n,m,l$.

Output Format

For each test case, output one line containing one integer: the answer.

5
3 3 1
3 4 0
114 514 86
19198 10101 7211
604800 4089470473293004800 443520 

7
21
191637399
939162608
305624040

Hint

Sample Explanation

The $7$ ways in the first example are:

• $(0,0,0) \to (1,0,0) \to (0,0,0) \to (1,0,0)$
• $(0,0,0) \to (0,1,0) \to (0,0,0) \to (1,0,0)$
• $(0,0,0) \to (0,0,1) \to (0,0,0) \to (1,0,0)$
• $(0,0,0) \to (1,0,0) \to (1,1,0) \to (1,0,0)$
• $(0,0,0) \to (1,0,0) \to (1,0,1) \to (1,0,0)$
• $(0,0,0) \to (0,1,0) \to (1,1,0) \to (1,0,0)$
• $(0,0,0) \to (0,0,1) \to (1,0,1) \to (1,0,0)$

Constraints

For $100\%$ of the testdata: $1\le T\le600$, $\sum n\log_2 n\le2^{25}$, $n\in[1,2^{21}]$, $m\in[0,2^{64}-1]$, $l\in[0,n]$.

You turn to the back and find a line of small text:

Please do not forget to consider special cases.

Translated by ChatGPT 5