djq is studying biology and has learned that genes are DNA segments. He now has a base pair sequence of length $3n$ consisting of ACTACT...ACT, which is actually composed of $n$ codons of ACT.

The evil Dr. ffffxk is causing trouble with his mutation gun. This mutation gun is very powerful and has $m$ built-in programs, one of which is a faulty program that causes the gun to break once it is run. The other programs, when applied to the base pair sequence, shuffle the sequence. Specifically, each program consists of $n$ permutations of length $3$. The $i$-th permutation acts on the $i$-th codon, transforming $s_1s_2s_3$ into $s_{p_1}s_{p_2}s_{p_3}$.

Every time the mutation gun is run, it independently and uniformly selects one of the programs to execute.

ffffxk uses his mutation gun repeatedly until it breaks. djq is curious about the probability of the base pair sequence ending up in each possible configuration. The answer should be taken modulo $998244353$.

Input

The first line contains an integer $n$, representing the number of codons.

The second line contains $6^n$ integers $c_i$, representing the count of a certain type of program. The programs are defined as follows:

Represent $i-1$ as an $n$-digit base-6 number $\overline{a_na_{n-1}a_{n-2}\cdots a_1}$, where $a_j$ indicates that the permutation applied to the $j$-th codon is the $(a_j+1)$-th lexicographically smallest permutation of length $3$.

That is, $0 \dots 5$ correspond to $(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)$ respectively.

$m = \sum c_i + 1$.

Output

To reduce the output size, you only need to output the XOR sum of all answers.

If any answer does not converge modulo $998244353$, output -1.

Otherwise, output a single integer representing the XOR sum of the probabilities of the final base pair sequence configurations, taken modulo $998244353$.

Examples

Input 1

1
0 0 0 1 0 0

Output 1

1

Note 1

The mutation gun has two built-in programs: one is the faulty program, and the other corresponds to the permutation $(2,3,1)$.

The probability that the final sequence is ACT is $\frac 47$, which is $427819009$ modulo $998244353$.

The probability that the final sequence is CTA is $\frac 27$, which is $713031681$ modulo $998244353$.

The probability that the final sequence is TAC is $\frac 17$, which is $855638017$ modulo $998244353$.

The XOR sum of these three values is $1$.

Input 2

2
806045030 846930886 683448424 716392562 959503440 424238335 719885386 651516139 596516649 191397068 26958009 352245674 783368690 104275706 48409057 969269573 366936187 542139073 304089172 305211383 35005211 521595368 294702567 728712076 336465782 861021530 278722862 233665123 148685361 468703135 103269576 803735449 317389669 635723058 370888716 127653814

Output 2

271035623

Constraints

For all data, it is guaranteed that $1 \leq n \leq 8$, $998244353 \nmid m$, and $c_i \in [0, 998244353)$.

A: If $c_i \neq 0$, then the base-6 representation of $i$ only contains $0, 3, 4$.