Define a beautiful matrix as a $$$2\times n$$$ matrix, such that every entry of the matrix is either a $$$0$$$ or a $$$1$$$ and every $$$2\times k$$$ submatrix has a sum of $$$s$$$.
For instance, for $$$n=4$$$, $$$k=2$$$, $$$s=2$$$, $$$[1010; 1010]$$$ and $$$[1000;0111]$$$ are beautiful and $$$[1001;0111]$$$, $$$[010;101]$$$, and $$$[0000;1110]$$$ are not beautiful.
Count the number of beautiful matrices for given $$$n$$$, $$$k$$$, and $$$s$$$ modulo $$$998\,244\,353$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\leq t\leq 20$$$). This is followed by $$$t$$$ lines — the description of the test cases.
Each line contains three integers $$$n$$$, $$$k$$$, and $$$s$$$ ($$$1\leq n\leq 10^{18}$$$, $$$1\leq k\leq \min(n, 10^6)$$$, $$$0\leq s\leq 2k$$$) — the size of the matrix, the size of the submatrix, and the sum of the submatrix.
It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$5\cdot 10^6$$$.
—
Testcases in subtasks are numbered $$$1$$$ to $$$20$$$ with samples skipped.
Test $$$1$$$: The sum of $$$n$$$ does not exceed $$$10$$$.
Test $$$2-3$$$: The sum of $$$k$$$ does not exceed $$$5\cdot 10^3$$$.
Test $$$4-5$$$: $$$k$$$ divides $$$n$$$.
Test $$$6-15$$$: The sum of $$$k$$$ does not exceed $$$5\cdot 10^5$$$.
Test $$$16-20$$$: No additional constraints.
Each test is worth $$$5$$$ points with samples skipped.
For each test case, print a single integer — the number of beautiful matricies modulo $$$998\,244\,353$$$.
43 2 16 4 26 4 610 6 7
6 56 56 4360
222272727425 175432 76534472306406606064 254312 432752
933599753 43127063
— Problem Idea: dutin Problem Preparation: dutin Occurrences: Advanced 12
| Teamscode Summer 2023 Contest |
|---|
| Закончено |
