题目描述

有 $n$ 个 $3\times 3$ 的矩阵

$$A_1,A_2,\ldots,A_n.$$

设 $S_n$ 为全部 $n$ 阶排列的集合。求下式对 $998244353$ 取模的结果：

$$\sum_{\sigma\in S_n} \left(A_{\sigma(1)}A_{\sigma(2)}\cdots A_{\sigma(n)}\right)_{1,1}.$$

其中，$(M)_{1,1}$ 表示矩阵 $M$ 的第 $1$ 行第 $1$ 列元素。

输入格式

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

接下来 $3n$ 行，每连续 $3$ 行描述一个矩阵 $A_i$。每行包含 $3$ 个整数，分别表示该行的三个元素。

输出格式

输出一行一个非负整数，表示答案对 $998244353$ 取模的结果。

样例 1

输入

3
9 9 8
2 4 4
3 5 3
1 2 3
4 5 6
7 8 9
1 9 1
9 1 9
1 9 1

输出

4767

数据范围

对于全部测试数据：

$$1\le n\le 40.$$

矩阵元素均为区间 $[0,998244353)$ 内的整数。

子任务

子任务编号	$n\le$	特殊性质	分值
1	$8$	无	10
2	$15$		25
3	$40$	对任意 $x,i$，$A_{x,i,3}=A_{x,3,i}=0$	20
4		对任意 $x$，$A_{x,2,3}=A_{x,3,2}=0$
5		无	25