AT_arc223_f [ARC223F] Zonal Score Maximization

定义长度至少为 $2$ 的正整数序列的得分为其最大值与最小值之和。 对于长度至少为 $2$ 的正整数序列 $A$，令 $f(A)$ 为将 $A$ 划分为一个或多个连续子序列，且每个子序列长度至少为 $2$ 时，所有子序列得分总和的最大可能值。 形式化地，对于任意 $K$，若 $A$ 可以被划分为 $K$ 个长度均至少为 $2$ 的正整数序列 $B_1, B_2, \dots, B_K$，且它们按顺序拼接后恰好等于序列 $A$，$f(A)$ 被定义为 $\sum_{k=1}^{K}\left(\max(B_k)+\min(B_k)\right)$ 的最大可能值。 给定一个长度为 $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$ 组测试数据。

输入从标准输入按以下格式给出： > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每组测试数据 $\mathrm{case}_t$ 按以下格式给出： > $N$ $X$ > > $Q_1$ $Q_2$ $\dots$ $Q_N$

共输出 $T$ 行，第 $t$ 行包含第 $t$ 组测试数据的答案。

对于第一组测试数据，满足第一个条件的排列 $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$。 - 所有输入值均为整数。