题目描述

有 $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$。

数据范围

对于所有测试点，$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$ 及任意 $y\in\{1,2,3,4\}$，都有 $g_i(1,y)=g_i(2,y)=g_i(3,y)=g_i(4,y)$。

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