Problem Statement

There is an integer sequence $S=(S_1,S_2,\dots,S_N)$ of length $N$. There are also $M$ kinds of cards, with $10^{100}$ cards of each kind. A card of type $i \ (1 \leq i \leq M)$ has the integer $A_i$ written on its front and the integer $B_i$ written on its back.

Find the sum of $f(T)$ over all non-empty subsequences $T=(T_1,T_2,\dots,T_L)$ of the integer sequence $S$, modulo $998244353$.

Here, $f(T)$ is defined as follows.

• Suppose $L$ cards are arranged in a left-to-right row on a table, front side up and back side down, with the $i$-th card from the left being a card of type $T_i$. The value is the number of ways to choose some cards (possibly $0$) and flip them so that the sum of the integers written on the upward-facing sides of the cards is $K$.

A subsequence of an integer sequence is an integer sequence obtained by deleting $0$ or more elements from it and arranging the remaining elements without changing their order. $2$ subsequences are considered the same subsequence if they are equal as integer sequences, even if the positions of the deleted elements differ.

Input

$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)$
• All input values are integers.

Output

Print the answer to standard output on $1$ line.

Sample

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