$\bullet$ Mały Aniołek Yi Ai $\bullet$: Wow, czego szukasz w grupie UOJ zupełnie sam?

「1. Szukam wielomianów」

「2. Szukam Małego Aniołka」

Mamy siatkę o wymiarach $n\times m$, w której każdą komórkę można pomalować na jeden z $k$ kolorów. Dla danych zbiorów $S$ oraz $T$, oblicz liczbę sposobów pokolorowania siatki, takich że:

• Dla każdego wiersza, jeśli weźmiemy jego wzór i policzymy, ile wierszy w całej siatce ma identyczny wzór (wliczając w to dany wiersz), to liczba ta $r$ musi należeć do zbioru $S$.
• Dla każdej kolumny, jeśli weźmiemy jej wzór i policzymy, ile kolumn w całej siatce ma identyczny wzór (wliczając w to daną kolumnę), to liczba ta $c$ musi należeć do zbioru $T$.

Wynik należy podać modulo $P = 998244353$.

Aby kod do tego zadania wyglądał na zdrowy, gwarantuje się, że $1\in S \cap T$.

Wejście

W pierwszej linii podano pięć liczb całkowitych dodatnich: $n, m, k, a, b$.

W kolejnej linii podano $a$ liczb całkowitych dodatnich, rosnąco, reprezentujących zbiór $S$. Gwarantuje się, że liczby są unikalne.

W kolejnej linii podano $b$ liczb całkowitych dodatnich, rosnąco, reprezentujących zbiór $T$. Gwarantuje się, że liczby są unikalne.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą liczbę sposobów pokolorowania spełniających warunki, modulo $P$.

Przykłady

Przykład 1

Wejście:

2 2 2 1 1
1
1

Wyjście:

10

Wyjaśnienie do przykładu 1:

Oznacza to, że każde dwa wiersze muszą mieć różne kolory, a każde dwie kolumny muszą mieć różne kolory.

Spośród $2^4 = 16$ możliwych sposobów pokolorowania, następujące $6$ jest niedozwolonych:

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

Przykład 2

Wejście:

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

Wyjście:

132764272

Przykład 3

Wejście:

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

Wyjście:

208881352

Podzadania

• $10\%$ danych wejściowych: $n, m\le 50$.
• $40\%$ danych wejściowych: $n, m\le 3000$.
• Kolejne $10\%$ danych wejściowych: $S = T = \{1\}$.
• $100\%$ danych wejściowych: $1\le n, m\le 10^5, 1\le k\le P - 1, 1\le a, b\le5, 1\in S \cap T, S \subseteq [1, n], T \subseteq [1, m]$.