codeforces#P1671F. Permutation Counting

    ID: 32893 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forcecombinatoricsdpfftmath*2700

Permutation Counting

Description

Calculate the number of permutations $p$ of size $n$ with exactly $k$ inversions (pairs of indices $(i, j)$ such that $i < j$ and $p_i > p_j$) and exactly $x$ indices $i$ such that $p_i > p_{i+1}$.

Yep, that's the whole problem. Good luck!

The first line contains one integer $t$ ($1 \le t \le 3 \cdot 10^4$) — the number of test cases.

Each test case consists of one line which contains three integers $n$, $k$ and $x$ ($1 \le n \le 998244352$; $1 \le k \le 11$; $1 \le x \le 11$).

For each test case, print one integer — the answer to the problem, taken modulo $998244353$.

Input

The first line contains one integer $t$ ($1 \le t \le 3 \cdot 10^4$) — the number of test cases.

Each test case consists of one line which contains three integers $n$, $k$ and $x$ ($1 \le n \le 998244352$; $1 \le k \le 11$; $1 \le x \le 11$).

Output

For each test case, print one integer — the answer to the problem, taken modulo $998244353$.

Samples

5
10 6 4
7 3 1
163316 11 7
136373 11 1
325902 11 11
465
12
986128624
7636394
57118194