cats 的加减乘除

Problem Description

cats 有一个长度为 $n$ 的排列 $p$，现在他想要在这 $n$ 个数每相邻两个数之间随机加入一个运算符号，符号为加减乘除中的一种（每一种符号的概率相等，均为 $\frac{1}{4}$）。添加完符号后这个排列构成了一个表达式，现在 cats 想要知道这个表达式的值的期望。（表达式的计算遵循先乘除后加减，同级运算则按从左到右的顺序依次进行的原则） 现在 cats 的这个排列中一些位置的值被擦去了（用 $p_i=-1$ 表示），cats 想要知道所有可能的排列（每一种可能的排列出现的概率均相同）构成的所有表达式的值的期望对 $998244353$ 取模的结果。

Input

第一行一个整数 $t$（$1\leq t\leq 1000$），表示测试数据组数。 接下来对于每一组数据，第一行一个整数 $n$（$1\leq n\leq 2\times 10^5$），表示排列的长度。 接下来一行包含 $n$ 个由空格隔开的整数 $p_i$（$p_i=-1$ 或 $1\leq p_i\leq n$），表示给出的排列，其中 $p_i=-1$ 表示这个位置被删去了。保证所有不为 $-1$ 的 $p_i$ 互不相同。 保证所有数据的 $n$ 的和不超过 $10^6$。

Output

对于每一组数据输出一行，表示所有可能表达式的期望对 $998244353$ 取模的结果。

Sample Input

4
5
1 2 3 4 5
6
-1 -1 -1 -1 -1 -1
3
-1 1 2
4
1 2 -1 -1

Sample Output

263858861
248609357
811073540
337297410

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（6）