F-tb的排列问题_牛客小白月赛101

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

tb 给了 fc 一个长度为 $n$ 的排列 $A$ ，fc 想要更改一下此排列，他选择了一个幸运数字 $w$ ,依照如下方式操作了 $n$ 次:

第 $i$ 次操作中，选择两个整数 $x,y$ ，满足 $i \le x \le y \le min(i+w,n)$ ，交换 $A_x$ 与 $A_y$ 的值， $x$ = $y$ 时数组不变。

经过这 $n$ 次操作后，他得到了新的排列 $B$ 。

由于 fc 的记忆只有七秒，他很快就忘记了 $A$ 排列是什么样子，只记得一部分 $A$ 排列中的元素以及其对应位置。现在他将 $B$ 排列以及残缺的 $A$ 排列给出，请你帮他计算一下一共有多少种可能的 $A$ 排列。（可能存在 fc 记忆错乱了，没有符合条件的 $A$ 。）

由于答案过大，输出方案数模以 $998244353$ 即可。

排列：一个长度为 $n$ 的正整数数组，其中元素两两不同且最大值为 $n$ 。

输入描述:

第一行输入  ,表示数据的组数。

每组数据以如下格式给出：

第一行输入两个正整数。

第二行输入  个整数表示残缺的  ，若  ，则表示记不清该位置上的数了，否则其为该位置上对应的数。

第三行输入  个整数，表示一个长度为  的排列  。

数据保证  。

输出描述:

每组数据输出一个非负整数，表示符合条件的排列数对  取模后的值。

示例1

输入

复制

6
3 1
3 -1 -1
2 1 3
3 2
3 -1 -1
2 1 3
4 1
4 3 1 2
1 4 3 2
6 4
6 1 5 -1 3 -1
4 2 6 3 1 5
7 4
2 5 -1 -1 -1 4 -1
1 3 6 2 7 4 5
14 13
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1 2 3 4 5 6 7 8 9 10 11 12 13 14

输出

复制