For three binary strings $s_1, s_2, s_3$ of length $n$, a binary string $t$ of length $n$ is called "good" if and only if $\forall 1 \le i, j \le n, \exists k \in \{1, 2, 3\}$ such that $s_{k,i} = t_i$ and $s_{k,j} = t_j$. Let $f(s_1, s_2, s_3)$ be the number of such good strings.

We are given three random binary strings $s_1, s_2, s_3$ of length $n$, where the $j$-th character ($1 \le j \le n$) of $s_i$ ($1 \le i \le 3$) is $1$ with probability $\frac{p_{i,j}}{9}$ and $0$ with probability $(1 - \frac{p_{i,j}}{9})$, where $p_{i,j}$ is an integer from $0$ to $9$. All random events are independent. You need to find the expected value of $f(s_1, s_2, s_3)$, modulo $998244353$.

Input

The first line contains an integer $n$ ($3 \le n \le 3 \times 10^5$) representing the length of the strings. The next 3 lines each contain $n$ digits, where the digit at the $i$-th row and $j$-th column represents $p_{i,j}$.

Output

Output a single integer representing the expected value modulo $998244353$.

Examples

Input 1

3
900
090
009

Output 1

4

Note 1

In this example, $s_1, s_2, s_3$ are $100, 010, 001$ respectively. The four valid strings are $100, 010, 001, 000$.

Input 2

3
999
999
999

Output 2

1

Input 3

10
0123456789
1234567890
2345678901

Output 3

612360617