Expected Count of Good Strings

We are given three binary strings (s_1,s_2,s_3) of length (n). A binary string (t) of length (n) is defined to be (good) if and only if for every pair of positions (1 \le i,j \le n) there exists an index (k) in ({1,2,3}) such that (s_{k,i}=t_i) and (s_{k,j}=t_j). In other words, for every (1 \le i,j \le n) we require [ (t_i,t_j) \in {(s_{1,i},s_{1,j}),(s_{2,i},s_{2,j}),(s_{3,i},s_{3,j})}. ] It turns out that a string (t) is good if and only if (t=s_k) for some (k\in{1,2,3}).

Now, each (s_i) is generated randomly as a 0–1 string of length (n) in the following way. For every (1 \le j \le n), the (j)-th character of (s_i) 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 in ([0,9])). All these events are mutually independent.

Define (f(s_1,s_2,s_3)) to be the number of good strings (t), which is exactly the number of distinct strings among (s_1,s_2,s_3).

By elementary probability, if we let [ P_{a,b}=\prod_{j=1}^n\Bigl[ (1-\frac{p_{a,j}}{9})(1-\frac{p_{b,j}}{9})+\frac{p_{a,j},p_{b,j}}{9^2}\Bigr] ] for each pair ((a,b)) and [ T=\prod_{j=1}^n\Bigl[\prod_{i=1}^3\Bigl(1-\frac{p_{i,j}}{9}\Bigr)+\prod_{i=1}^3\frac{p_{i,j}}{9}\Bigr], ] then the expected value of (f(s_1,s_2,s_3)) is given by [ E[f(s_1,s_2,s_3)] = 3 - (P_{1,2}+P_{1,3}+P_{2,3}) + T \pmod{998244353}. ] Your task is to compute (E[f(s_1,s_2,s_3)]) modulo (998244353).

Note: All fractions must be interpreted in (\LaTeX) format.

inputFormat

The input consists of (n+1) lines. The first line contains a single integer (n) ((1\le n\le 10^5)), which is the length of each string. Then three lines follow. The (i)-th of these lines contains (n) integers (p_{i,1}, p_{i,2}, \dots, p_{i,n}) ((0\le p_{i,j}\le 9)) separated by spaces.

outputFormat

Output a single integer: the expected number of good strings (f(s_1,s_2,s_3)) modulo (998244353).

sample

1
0
9
5

2