問題文

色について異なる文化を持つ yuki 国と coder 国の $2$ つの国があります．この $2$ つの国の間では，文化の違いにより，同じものに対してもその色の表し方が異なるという特徴があります．

また，yuki 国と coder 国の間では，文化の違いにより，虹を構成する色も相異なります．

具体的には，yuki 国では虹は色 $1, 2, \dots, M$ の $M$ 色から構成され，coder 国では虹は色 $M + 1, M + 2, \dots, M + L$ の $L$ 色から構成されます．

ここに，$N$ 本のペンがあります．$i$ 本目のペンは，yuki 国では色 $A_i(1 \leq A_i \leq M)$ であり，coder 国では色 $B_i(M + 1 \leq B_i \leq M + L)$ です．

なお，異なるペンの間に $2$ 国間での色の対応関係はないことに注意してください．（相異なる $i, j$ に対し，$A_i = A_j$ であっても $B_i = B_j$ であるとは限りません）

$N$ 本のペンから $1$ 本以上を選ぶ方法の数は $2^N - 1$ 通りありますが，その中で次の条件を満たす選び方の数を求めてください．

• yuki 国と coder 国のどちらに対しても，選んだペンの中にその国において虹を構成する色がすべて含まれている．

答えは非常に大きくなることがあるので，$998244353$ で割った余りを出力してください．

制約

• 入力は全て整数
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M, L \leq 18$
• $1 \leq A_i \leq M$
• $M + 1 \leq B_i \leq M + L$

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$ $L$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

出力

条件を満たすペンの選び方を $998244353$ で割った余りを出力せよ．

サンプル

4 2 2
1 3
1 4
2 3
2 4

7

2 2 2
1 3
1 3

0

12 3 4
1 5
2 5
2 4
1 6
3 7
3 4
2 6
1 4
2 7
1 7
3 5
3 6

2161