题目描述

对于三个长度为 $n$ 的 $01$ 字符串 $s_1,s_2,s_3$，称长度为 $n$ 的 $01$ 字符串 $t$ 是好的当且仅当 $\forall 1 \le i,j \le n,\ \exists k \in \{1,2,3\},\ s_{k,i} = t_i, s_{k,j} = t_j$。设 $f(s_1,s_2,s_3)$ 为这样的好的串的数量。

现在我们有三个长度为 $n$ 的随机 $01$ 字符串 $s_1,s_2,s_3$，其中 $s_i$ $(1 \le i \le 3)$ 的第 $j$ $(1 \le j \le n)$ 个字符有

$$\frac{p_{i,j}}{9}$$

的概率为 $1$，

$$\left(1 - \frac{p_{i,j}}{9}\right)$$

的概率为 $0$，其中 $p_{i,j}$ 是一个 $0$ 至 $9$ 的整数。所有的随机事件是独立的。你需要求 $f(s_1,s_2,s_3)$ 的期望，对 $998244353$ 取模。

---

输入格式

输入第一行一个整数 $n$ $(3 \le n \le 3 \times 10^5)$ 表示字符串长度，接下来一个 $3$ 行 $n$ 列的数字矩阵，其中第 $i$ 行第 $j$ 列的字符表示 $p_{i,j}$。

---

输出格式

输出一个整数表示答案对 $998244353$ 取模的值。

---

样例 1

输入

3
900
090
009

输出

4

在该组样例中，$s_1, s_2, s_3$ 分别为 $100$, $010$, $001$，四种方案分别为 $100$、$010$、$001$、$000$。

---

样例 2

输入

3
999
999
999

输出

1

---

样例 3

输入

10
0123456789
1234567890
2345678901

输出

612360617

---

题目使用协议
来自 THUPC2025（2025年清华大学学生程序设计竞赛暨高校邀请赛）。

以下『本仓库』皆指 THUPC2025 官方仓库（https://gitlink.org.cn/thusaa/thupc2025final）

任何单位或个人都可以免费使用或转载本仓库的题目；
任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。