AT_arc223_f.Zonal Score Maximization

Define the score of a positive integer sequence with length $2$ or more as the sum of its maximum and minimum values.
For a positive integer sequence $A$ of length $2$ or more, let $f(A)$ be the maximum possible value of the total score of the contiguous subsequences when $A$ is divided into one or more contiguous subsequences each of length $2$ or more.
More formally, for a positive integer $K$, let $f(A)$ be the maximum possible value of $\sum_{k=1}^{K}\left(\max(B_k)+\min(B_k)\right)$ when concatenating $K$ positive integer sequences $B_1, B_2, \dots, B_K$, each of length $2$ or more, in this order yields the same sequence as $A$.

You are given an integer sequence $Q$ of length $N$ where each element is either an integer between $1$ and $N$ inclusive or $-1$, and a positive integer $X$.
Find the total number, modulo $998244353$, of permutations $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$ satisfying all of the following conditions.

• For $i=1,2,\dots,N$, if $Q_i \neq -1$ then $P_i=Q_i$.
• $f(P)=X$

Solve $T$ test cases per input.

定义一个长度至少为 $2$ 的正整数序列的得分为其最大值与最小值之和。
对于一个长度至少为 $2$ 的正整数序列 $A$，令 $f(A)$ 表示将 $A$ 划分为一个或多个长度均至少为 $2$ 的连续子序列时，这些子序列的得分总和所能达到的最大值。
更严格地，对任意正整数 $K$，令 $f(A)$ 为如下表达式的最大可能值：$\sum_{k=1}^{K}\left(\max(B_k)+\min(B_k)\right)$，其中 $B_1, B_2, \dots, B_K$ 是 $K$ 个长度均至少为 $2$ 的正整数序列，且将它们按顺序拼接后得到的序列恰好等于 $A$。

给定一个长度为 $N$ 的整数序列 $Q$，其中每个元素要么是介于 $1$ 到 $N$（含）之间的整数，要么为 $-1$；另给定一个正整数 $X$。
求满足以下所有条件的排列 $P=(P_1,P_2,\dots,P_N)$（即 $(1,2,\dots,N)$ 的一个排列）的总数，结果对 $998244353$ 取模：

• 对每个 $i=1,2,\dots,N$，若 $Q_i \neq -1$，则 $P_i=Q_i$；
• $f(P)=X$。

每组输入包含 $T$ 个测试用例，需全部求解。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case $\mathrm{case}_t$ is given in the following format:

$N$ $X$
$Q_1$ $Q_2$ $\dots$ $Q_N$

输入从标准输入中按以下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例 $\mathrm{case}_t$ 按以下格式给出：

$N$ $X$
$Q_1$ $Q_2$ $\dots$ $Q_N$

Output the answers over a total of $T$ lines. The $t$-th line should contain the answer for the $t$-th test case.

在总共 $T$ 行中输出答案。第 $t$ 行应包含第 $t$ 个测试用例的答案。

Sample 1 Explanation:
For the first test case, the permutations $P$ satisfying the first condition are these two: $(2,1,3)$ and $(2,3,1)$. In either case, the only way to divide $P$ into contiguous subsequences each of length $2$ or more is to take $P$ itself as a single contiguous subsequence. The total score in that case is $3+1=4$, so $f(P)=4$.
For the second test case, dividing $P=(1,3,4,2)$ into $(1,3)$ and $(4,2)$ gives a total score of $10$, which cannot be exceeded, so $f(P)=10$.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 10^5$
• $1 \leq X \leq 10^{18}$
• $Q_i=-1$ or $1 \leq Q_i \leq N$
• If $Q_i \neq -1$ and $Q_j \neq -1$, then $Q_i \neq Q_j\;(i \neq j)$.
• The sum of $N$ over all test cases is at most $10^5$.
• All input values are integers.

样例 1 解释：
对于第一个测试用例，满足第一个条件的排列 $P$ 有两个：$(2,1,3)$ 和 $(2,3,1)$。在这两种情况下，将 $P$ 划分为若干长度均不小于 $2$ 的连续子序列的唯一方式是将 $P$ 整体作为一个连续子序列。此时总得分为 $3+1=4$，因此 $f(P)=4$。
对于第二个测试用例，将 $P=(1,3,4,2)$ 划分为 $(1,3)$ 和 $(4,2)$ 可得到总得分 $10$，该得分无法被超越，因此 $f(P)=10$。

约束条件

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 10^5$
• $1 \leq X \leq 10^{18}$
• $Q_i=-1$ 或 $1 \leq Q_i \leq N$
• 若 $Q_i \neq -1$ 且 $Q_j \neq -1$，则 $Q_i \neq Q_j\;(i \neq j)$。
• 所有测试用例的 $N$ 之和不超过 $10^5$。
• 所有输入值均为整数。