T3 局部函数（function）

时间限制：$2$ 秒。内存限制：$512$ MB。

题目描述

有 $n$ 个寄存器排成一行，第 $i$ 个寄存器的初值为 $a_i\in\{1,2,3,4\}$。两端各有一个额外的寄存器，编号为 $0$ 和 $n+1$，值始终为 $1$，不参与刷新。

对于每个 $1\le i\le n$，给定函数 $g_i:\{1,2,3,4\}^2\to\{1,2,3,4\}$（即，输入两个 $1\sim4$ 的整数，输出一个 $1\sim4$ 的整数的函数）。刷新第 $i$ 个寄存器时，读取左右相邻寄存器的当前值 $x,y$，将它的值改为 $g_i(x,y)$。其他寄存器的值不变。

选择 $1,2,\ldots,n$ 的一个排列，按此顺序将每个内部寄存器恰好刷新一次。求能得到多少个不同的最终序列，答案对 $998244353$ 取模。

最终序列只包含编号 $1$ 至 $n$ 的寄存器。不同刷新顺序得到相同的最终序列，只计一种结果。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $n$ 行，第 $i$ 行包含 $16$ 个整数，依次为 $g_i(1,1),g_i(1,2),\ldots,g_i(1,4),g_i(2,1),\ldots,g_i(4,4)$，即先按第一个参数递增，再按第二个参数递增。

输出格式

输出一个整数，表示不同最终序列的数量对 $998244353$ 取模后的值。

样例

输入：

3
1 2 1
1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1
1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1
1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1

输出：

3

样例解释

当刷新顺序为 $(1,2,3)$ 或 $(3,2,1)$ 时，最终序列为 $(2,2,2)$；当顺序为 $(1,3,2)$ 或 $(3,1,2)$ 时，最终序列为 $(2,1,2)$；当顺序为 $(2,1,3)$ 或 $(2,3,1)$ 时，最终序列为 $(1,1,1)$。六种顺序共得到三种结果，答案为 3。

附加样例对应的数据范围如下：

• function2.in/.ans：满足测试点 $7\sim9$ 的限制，还满足特殊性质 $C$。
• function3.in/.ans：满足测试点 $10\sim11$ 的限制。
• function4.in/.ans：满足测试点 $12\sim13$ 的限制。
• function5.in/.ans：满足测试点 $17\sim20$ 的限制。

数据范围

测试点编号	$n\le$	特殊性质
1—3	$8$	无
4—6	$20$
7—9	$100$
10—11	$2\times10^5$	$A$
12—13		$B$
14—16		$C$
17—20		无

对于所有测试点，$1\le n\le2\times10^5$，$a_i\in\{1,2,3,4\}$。对于每个 $1\le i\le n$ 及任意 $x,y\in\{1,2,3,4\}$，都有 $g_i(x,y)\in\{1,2,3,4\}$。

特殊性质 $A$：对于所有 $i$ 及任意 $x\in\{1,2,3,4\}$，都有 $g_i(x,1)=g_i(x,2)=g_i(x,3)=g_i(x,4)$。

特殊性质 $B$：对于所有 $i$ 及任意 $x,y\in\{1,2,3,4\}$，都有 $g_i(x,y)=\max(x,y)$。

特殊性质 $C$：所有初值均属于 $\{1,2\}$，且对所有 $i$ 及任意 $x,y\in\{1,2\}$，都有 $g_i(x,y)\in\{1,2\}$。