Statement : E0. Amanojaku and Sequence (Tutorial Version)

Tinkerbell of Inequality— Taboo Japan Disentanglement

This is a tutorial version of E1. You are given the full array once per test case. There are no subarray queries: compute $g(a,m)$ for the entire sequence $a$.

For a non-negative integer sequence $c$, define

Let $b$ be an integer sequence with $b_i \ge -1$, and let $m$ be a non-negative integer. A sequence $c$ is valid for $(b,m)$ if $|c|=|b|$, $\sum_i c_i = m$, and $c_i = b_i$ whenever $b_i \ge 0$ (when $b_i = -1$, the value $c_i$ may be any non-negative integer). Define

or $g(b,m)=0$ if no valid $c$ exists.

For each test case you are given $n$, the array $a$ of length $n$, and $m$. Output $g(a,m)$ modulo $998\,244\,353$.

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

Each test case:

• One line: $n$ and $m$ ($1 \le n \le 100$, $0 \le m \le 500$).
• One line: $a_1,\ldots,a_n$ ($-1 \le a_i \le 10^6$).

It is guaranteed that $\sum n \le 10^4$ and $\sum n \cdot m \le 5 \cdot 10^5$.

For each test case, print $g(a,m)$ modulo $998\,244\,353$.

Input

6
1 2
-1
2 8
6 -1
2 5
-1 -1
4 7
-1 -1 -1 -1
3 2
4 -1 7
4 5
-1 -1 3 -1

Output

4
100
205
12180
0
286

Note

• $n=1$, $a=[-1]$, $m=2$: the only valid $c$ is $[2]$, so the answer is $2^2=4$.
• $n=2$, $a=[6,-1]$, $m=8$: we must have $c=[6,2]$; prefix sums $6,8$ give $36+64=100$.
• $n=2$, $a=[-1,-1]$, $m=5$: all splits $c_1+c_2=5$ are allowed; summing $f(c)$ over $[0,5],[1,4],\ldots,[5,0]$ gives $205$.
• $n=4$, all $-1$, $m=7$: every non-negative quadruple with sum $7$ is valid; the answer is $12180$.
• $n=3$, $a=[4,-1,7]$, $m=2$: fixed entries already sum to $11 > m$, so no valid $c$.
• $n=4$, $a=[-1,-1,3,-1]$, $m=5$: fixed $c_3=3$, so $c_1+c_2+c_4=2$; summing $f(c)$ over all such triples gives $286$.