题目描述

虽然坤哥上次被袭击以后成功以铁山靠突破包围圈，但是他身上仍然受了不少伤。$\color{black}{\text{x}}\color{red}{\text{yw}}$ 认为坤哥是扶不起的阿斗，转身就成为了小黑子，只有其他 $n$ 个 ikun 前来慰问坤哥，并纷纷表示他们今后要当坤哥的保镖“誓死保卫我家坤坤！”。

于是坤哥把他们整成一个列队，第 $i$ 个人的战力一个 $3 \times 3$ 的矩阵 $A_i$ 表示。对于一个列队 $P$（$P$ 是一个排列），令 $B = A_{P_1} \times A_{P_2} \times \dots \times A_{P_n}$，那么这个列队的战力值为 $B_{1,1}$。由于在应急情况下，ikun 们排成的列队 $P$ 是随机的，因此坤哥想知道列队战力值的期望。显然这个期望可能很大，因此坤哥只需要你求出期望对 $998244353$ 取模后的结果。

输入格式

第一行一个正整数 $n$，表示 ikun 的人数。

接下来 $3n$ 行，每行三个正整数，第 $(i-1) \times 3 +1 + j$ 行第 $k$ 列表示 $A_{i,j,k}$。

输出格式

一行，一个正整数，表示期望对 $998244353$ 取模后的结果。

样例 1 输入

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

样例 1 输出

442

样例 2

见下发文件。

link

数据范围

对于 $10\%$ 的数据，$n \leq 8$。

对于 $30\%$ 的数据，$n \leq 15$。

对于另外 $20\%$ 的数据，$\forall x \in [1,n],i \in [1,3],A_{x,3,i} = A_{x,i,3} = 0$。

对于 $100\%$ 的数据，$1 \leq n \leq 40,0 \leq A_{i,j,k} < 998244353$。