花环

Problem Description

小 z 手里有一个大小为 $n$ 置换 $P$ 和一个长度为 $n$ 值域为 $[1,n]$ 正整数的的颜色序列 $a$，位置 $i$ 的颜色为 $a_i$ ，求 $P$ 中所有置换环的颜色数。 为了方便你输出，小 z 会给你一个序列 $b$。 记颜色数为 $x$ 的置换环有 $c_x$ 个，那么你只需要求出 $\sum\limits_{i=1}^n b_{c_x}$。 但是小 z 原神玩多了，所以置换 $P$ 中有 $k$ 个位置的值被他忘记了，你需要对所有可能的最终置换形态求上述问题答案之和，答案对 $998244353$ 取模。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le 5$），表示测试数据组数。 第 $1$ 行 $2$ 个非负整数 $n$（$1\le n\le 5\times 10^4$），$k$（$0\le k\le 15$）。 第 $2$ 行 $n$ 个非负整数表示 $P_{1\cdots n}$（$0 \le P_i \le n$，且 $\forall i \neq j,P_i \neq 0,P_j \neq 0$，保证 $P_i \neq P_j$），如果 $P_i=0$，表示小 z 忘记了这个位置的值。 第 $3$ 行 $n$ 个正整数表示 $a_{1\cdots n}$（$1\le a_i\le n$）。 第 $4$ 行 $n$ 个正整数表示 $b_{1\cdots n}$（$0\le b_i\le 998244352$）。

Output

对于每组数据，输出 $1$ 行 $1$ 个整数，表示答案。

Sample Input

3
3 2
0 0 3
3 3 2
4 1 4
5 3
0 0 2 4 0
2 5 5 4 3
1 1 2 1 0
10 5
10 7 0 0 5 0 1 0 0 4
9 4 1 1 6 1 1 2 3 7
5 2 5 4 3 3 0 2 2 5

Sample Output

5
11
1302

Source

2024“钉耙编程”中国大学生算法设计超级联赛（10）