問題文

長さ $N$ の整数列 $S=(S_1,S_2,\dots,S_N)$ があります。また、$M$ 種類のカードが $10^{100}$ 枚ずつあり、種類 $i \ (1 \leq i \leq M)$ のカードの表面には整数 $A_i$ が、裏面には整数 $B_i$ が書かれています。

整数列 $S$ の空でない全ての部分列 $T=(T_1,T_2,\dots,T_L)$ についての $f(T)$ の総和を $998244353$ で割った余りを求めてください。

ここで、$f(T)$ は以下のように定義されます。

• テーブル上に $L$ 枚のカードが表面を上、裏面を下にして左右一列に並んでおり、左から $i$ 番目に種類 $T_i$ のカードがあるとき、カードを何枚か ( $0$ 枚でも良い) 選んで裏返す方法であって、カードの上を向いている面に書かれた整数の総和が $K$ となるものの数。

ただし、整数列の部分列とは、その整数列から $0$ 個以上の要素を削除して、残った要素を順序を変えずに並べた整数列を指します。$2$ つの部分列は、削除する要素の位置が異なっても、整数列として同じならば同じ部分列とみなします。

入力

$N$ $M$ $K$
$S_1$ $S_2$ $\dots$ $S_N$
$A_1$ $A_2$ $\dots$ $A_M$
$B_1$ $B_2$ $\dots$ $B_M$

• $1 \leq N \leq 2000$
• $1 \leq S_i \leq M \leq 2000 \ (1 \leq i \leq N)$
• $1 \leq A_i,B_i \leq K \leq 2000 \ (1 \leq i \leq M)$
• 入力は全て整数である。

出力

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

サンプル

3 2 4
1 2 1
1 3
2 2

6

1 1 1
1
1
1

2

15 5 30
1 4 2 3 5 3 1 4 2 3 4 4 3 2 1
1 2 4 5 4
2 3 1 2 2

544968