問題文

整数列 $A=(A_1,A_2,\dots,A_X),B=(B_1,B_2,\dots,B_Y)$ が与えられます。

始め整数 $P=0$ があり、PCT 君と tute さんは以下の操作を $N$ 回繰り返します。

• まず、PCT 君が $A$ から要素を一様ランダムに $1$ 個選ぶ。選んだ要素を $Q$ とし、$P$ を $P\ \mathrm{or}\ Q$ で置き換える。
• 次に、tute さんが $B$ から要素を一様ランダムに $1$ 個選ぶ。選んだ要素を $R$ とし、$P$ を $P\ \mathrm{and}\ R$ で置き換える。

$N$ 回の操作としてあり得るものは $(XY)^N$ 個あります。その全てに対して操作終了時の $P$ の総和 $\bmod 998244353$ を求めてください。

ただし、問題文の $\mathrm{or}$ とはビットごとの論理和で、$\mathrm{and}$ とはビットごとの論理積です。

入力

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

• 入力は全て整数である。
• $1 \le N \le 2 \times 10^5$
• $1 \le X,Y \le 2^{18}$
• $0 \le A_i,B_j < 2^{18}$

出力

答えを $1$ 行に出力してください。

サンプル

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