厌倦了那些虚假的广告游戏？现在来试试这个！

你有一个 $n \times n$ 的网格。每一行和每一列都关联着一把画刷，总共有 $2n$ 把画刷。当你选择使用一把画刷时，它会将对应行（或列）中的每一个单元格涂成该画刷指定的颜色。在这个游戏中，有 $n$ 种颜色，编号从 $1$ 到 $n$。对应行的画刷所指定的颜色构成了 $[1, 2, \dots, n]$ 的一个排列。同样地，对应列的画刷所指定的颜色也构成了 $[1, 2, \dots, n]$ 的一个排列。

样例中的画刷与目标图案

网格最初是空的，没有任何颜色。游戏的目标是将网格涂成给定的图案。

你不仅仅满足于判断目标是否可以达成。你想知道，如果你使用每把画刷恰好一次，在所有 $(2n)!$ 种可能性中，有多少种操作顺序可以得到目标图案？由于答案可能很大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 20$)，表示网格的大小。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)，其中 $p_i$ 表示对应第 $i$ 行的画刷颜色。保证 $p$ 是 $[1, 2, \dots, n]$ 的一个排列。

第三行包含 $n$ 个整数 $q_1, q_2, \dots, q_n$ ($1 \le q_i \le n$)，其中 $q_i$ 表示对应第 $i$ 列的画刷颜色。保证 $q$ 是 $[1, 2, \dots, n]$ 的一个排列。

接下来的 $n$ 行，每行包含 $n$ 个整数，表示一个 $n \times n$ 的矩阵 $c$ ($1 \le c_{i,j} \le n$)，其中 $c_{i,j}$ 表示目标图案中第 $i$ 行第 $j$ 列单元格的颜色。

输出格式

输出一个整数，表示方案数对 $998\,244\,353$ 取模的结果。

样例

输入 1

2
1 2
1 2
1 1
2 2

输出 1

6

说明

对于样例，如果我们从上到下、从左到右给 4 把画刷编号，则达到目标图案的 6 种操作顺序如下：

• 3, 2, 4, 1
• 3, 4, 1, 2
• 3, 4, 2, 1
• 4, 1, 3, 2
• 4, 3, 1, 2
• 4, 3, 2, 1