Problem Statement

You are given integer sequences $A=(A_1,A_2,\dots,A_X),B=(B_1,B_2,\dots,B_Y)$.

Initially, there is an integer $P=0$. PCT-kun and tute-san repeat the following operation $N$ times.

• First, PCT-kun chooses $1$ element from $A$ uniformly at random. Let $Q$ be the chosen element, and replace $P$ with $P\ \mathrm{or}\ Q$.
• Next, tute-san chooses $1$ element from $B$ uniformly at random. Let $R$ be the chosen element, and replace $P$ with $P\ \mathrm{and}\ R$.

There are $(XY)^N$ possible ways to perform the $N$ operations. Over all of them, find the sum of the values of $P$ at the end of the operations, $\bmod 998244353$.

Here, $\mathrm{or}$ in the statement denotes bitwise OR, and $\mathrm{and}$ denotes bitwise AND.

Input

$N\ X\ Y$
$A_1\ A_2\ \dots\ A_{X}$
$B_1\ B_2\ \dots\ B_{Y}$

• All inputs are integers.
• $1 \le N \le 2 \times 10^5$
• $1 \le X,Y \le 2^{18}$
• $0 \le A_i,B_j < 2^{18}$

Output

Output the answer on $1$ line.

Sample

1 1 2
1
2 3

1

5 4 3
1 2 3 4
5 6 7

1130844

527 5 5
0 1 2 3 4
5 6 7 8 9

248270434