L. Spatial Quantum Energy Theory
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a strange parallel universe, the rules of physics there are different from ours. But with the accumulation of time, the scientists there also gradually touched the field of microscopic physics.

People believe that an atom is composed of twenty types of elementary particles, but each type of elementary particle appears at most once in each atom. All elementary particles and atoms have energy. The energy of the $$$i$$$-th type of elementary particle is $$$e_i$$$ $$$(1\leq i \leq 20)$$$. The calculation of the energy of an atom is a bit complicated. Suppose that an atom contains $$$m$$$ elementary particles, the types of which are $$$a_1,a_2,... ,a_m$$$ $$$(1\leq a_i,m\leq 20)$$$ then the energy of the atom is:

$$$$$$ \left(\sum_{i=1}^m e_{a_i}\right)^m $$$$$$

Let's define some symbols for convenience. For an atom $$$A$$$,

  • $$$S_A$$$ denotes the set of elementary particles $$$A$$$ has
  • $$$E(A)$$$ denotes the energy of $$$A$$$
  • $$$w(A)$$$ denotes the number of elementary particles $$$A$$$ has

It has been found that, two atoms $$$A$$$ and $$$B$$$, as long as $$$S_A\subseteq S_B$$$ or $$$S_B\subseteq S_A$$$, will both enter the excited state under suitable conditions, releasing the energy of $$$E(A)\times E(B)$$$. An atom can enter the excited state with multiple atoms, but a certain pair of atoms can enter the excited state only once. These theories were proven by the high-energy collision experiments of that world.

However, with further research, more advanced quantum colliders can make multiple atoms go into excited states at the same time. It was found that there's something wrong with the above theories. Theoretically, all pairs of atoms that can enter the excited state would release energy once, but the experiment found that the real energy released is much more than predicted. Professor Teralem proposed the amazing "Spatial Quantum Energy Theory", which perfectly explains this phenomenon.

The "Spatial Quantum Energy Theory" showed that the original theory was only partially correct. The process described above is called inductive excitation. However, there exists another type of excitation called oscillatory excitation. When atom $$$A$$$ and $$$B$$$ enter inductive excitation, a very large range of spatial fluctuations is generated. Atom $$$C$$$ (different from $$$A$$$ and $$$B$$$) will be influenced by the spatial fluctuation and enter oscillatory excitation once if and only if $$$S_A\subseteq S_C, S_C\subseteq S_B$$$. The energy released by oscillatory excitation is $$$E(A)\times E(B)\times w(C)$$$. Notice that $$$C$$$ can enter oscillatory excitation for each pair of $$$A$$$ and $$$B$$$. In this case, each pair of inductively excited atoms may lead to a large number of other atoms being excited by the oscillations, resulting in a geometric increase of the energy released by the whole system.

You are in Professor Teralem's class and he has given you a homework assignment: given $$$n$$$ atoms, calculate the energy released by the whole system under suitable conditions. i.e. the total energy released by all inductive excitations and oscillatory excitations.

He knows the answer to this question could be very large, but he just needs to know that you have learned it. Please output the answer modulo $$$998244353$$$.

Input

The first line contains an integer $$$n$$$ $$$(2\leq n\leq 10^6)$$$, representing the number of atoms in the whole system.

The second line contains $$$20$$$ integers. The $$$i$$$-th number represents $$$e_i$$$ $$$(1\leq e_i \leq 10^9)$$$, the energy of the type $$$i$$$ elementary particle.

The next $$$n$$$ lines contains the elementary particle composition of each atom. The $$$i$$$-th line contains an integer $$$a_i$$$ $$$(1\leq a_i \lt 2^{20})$$$. If the $$$k$$$-th bit of $$$a_i$$$ in binary is $$$1$$$, then the $$$i$$$-th atom contains the type $$$k$$$ elementary particle, otherwise it does not. For example, if $$$a_1=13=(1101)_2$$$, it means the first atom is composed of type $$$1$$$, type $$$3$$$ and type $$$4$$$ elementary particles.

Output

Output an integer in a line, indicating the total energy released by the whole system under suitable conditions modulo $$$998244353$$$.

Example
Input
6
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
7
7
3
3
9
9
Output
94018
Note

In the example, we number the imput atoms from 1 to 6. According the description, the energy of them is 216, 216, 9, 9, 25, 25 respectively. The detail of the released energy is as follows:

Atoms involvedEnergy
$$$(1,2)\rightarrow \varnothing$$$$$$216\times 216=46656$$$
$$$(1,3)\rightarrow \{2,4\}$$$$$$216\times 9+216\times 9\times 3+216\times 9\times 2=11664$$$
$$$(1,4)\rightarrow \{2,3\}$$$$$$216\times 9+216\times 9\times 3+216\times 9\times 2=11664$$$
$$$(2,3)\rightarrow \{1,4\}$$$$$$216\times 9+216\times 9\times 3+216\times 9\times 2=11664$$$
$$$(2,4)\rightarrow \{1,3\}$$$$$$216\times 9+216\times 9\times 3+216\times 9\times 2=11664$$$
$$$(3,4)\rightarrow \varnothing$$$$$$9\times 9=81$$$
$$$(5,6)\rightarrow \varnothing$$$$$$25\times 25=625$$$

In the "Atoms involved" column, on the left side of the arrow is a pair of atoms in inductive excitation, while on the right side of the arrow is the set of atoms that enter oscillatory excitation by the pair.

The energy released by the whole system is $$$46656+11664+11664+11664+11664+81+625=94018$$$.