$\bullet$ Little Angel Yi Ai $\bullet$: Wow, what are you looking for in the UOJ group all by yourself?

「1. Looking for polynomials」

「2. Looking for the little angel」

There is an $n \times m$ grid, where each cell can be colored with one of $k$ colors. Given two sets $S$ and $T$, you need to count the number of coloring schemes such that:

• For every row, if we extract its pattern and count how many rows in the grid have the same pattern (including itself), this count $r$ must satisfy $r \in S$.
• For every column, if we extract its pattern and count how many columns in the grid have the same pattern (including itself), this count $c$ must satisfy $c \in T$.

The answer should be modulo $P = 998244353$.

To ensure the code for this problem remains healthy, it is guaranteed that $1 \in S \cap T$.

Input

The first line contains five positive integers: $n, m, k, a, b$.

The next line contains $a$ positive integers, given in increasing order, representing the elements of set $S$. It is guaranteed that the numbers are distinct.

The next line contains $b$ positive integers, given in increasing order, representing the elements of set $T$. It is guaranteed that the numbers are distinct.

Output

Output a single integer representing the number of valid coloring schemes modulo $P$.

Examples

Input 1

2 2 2 1 1
1
1

Output 1

10

Note 1

This means every two rows must have different colors, and every two columns must have different colors.

Out of $2^4 = 16$ possible coloring schemes, the following $6$ are invalid:

11 00 01 10 00 11
00 11 01 10 00 11

Input 2

49 50 666 5 4
1 2 6 9 19
1 2 3 5

Output 2

132764272

Input 3

10492 11451 1122334 5 5
1 2 600 9700 10492
1 2 301 3131 4921

Output 3

208881352

Subtasks

For $10\%$ of the data, $n, m \le 50$.

For $40\%$ of the data, $n, m \le 3000$.

For another $10\%$ of the data, $S = T = \{1\}$.

For $100\%$ of the data, $1 \le n, m \le 10^5$, $1 \le k \le P - 1$, $1 \le a, b \le 5$, $1 \in S \cap T$, $S \subseteq [1, n]$, $T \subseteq [1, m]$.