Вам надано простий неорієнтований граф із \(N\) вершинами та \(M\) ребрами. Вершини пронумеровані від 1 до \(N\), а ребра пронумеровані від 1 до \(M\). Ребро \(i\) з’єднує вершину \(U_i\) і вершину \(V_i\). Вам задано цілі числа \(K, S, T\) і \(X\). Скільки є послідовностей \(A = (A_0, A_1, \dots, A_K)\) що виконуються такі умови?

• \(A_i\) є цілим числом від 1 до \(N\) (включно).

• \(A_0 = S\)

• \(A_K = T\)

• Існує ребро, яке безпосередньо з’єднує вершину \(A_i\) і \(A_{i+1}\).

• Ціле число \(X\) (\(X≠S,X≠T\)) з’являється парну кількість разів (можливо, нуль) у послідовності \(A\).

  Оскільки відповідь може бути дуже великою, знайдіть її за модулем 998244353.

Обмеження

• Усі значення у вхідних даних є цілими числами.

• 2 ≤ N ≤ 2000

• 1 ≤ M ≤ 2000

• 1 ≤ K ≤ 2000

• 1 ≤ S,T,X ≤ N

• X ≠ S

• X≠T

• 1 ≤ \(U_i\) < \(V_i\) ≤ N

• Якщо i ≠ j, тоді (\(U_i, V_i\)) ≠ (\(U_j, V_j\)).

Формат вхідних даних

Перший рядок містить цілі числа \(N,M,K,S,T,X\)

Наступний  рядок містить \(N\) цілих чисел \(A_i\) (\(1 \le A_i \le 10^9\))

Наступні  \(M\) рядків містять цілі числа \(U_i, V_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану кількість.

Примітка

До прикладу 1:

Наступні 4 послідовності задовольняють умови:

• (1, 2, 1, 2, 3)

• (1, 2, 3, 2, 3)

• (1, 4, 1, 4, 3)

• (1, 4, 3, 4, 3)

(1, 2, 3, 4, 3) і (1, 4, 1, 2, 3) не підходять - кількість 2 непарна.

Приклад вхідних даних

4 4 4 1 3 2
1 2
2 3
3 4
1 4

Приклад вихідних даних

4

Приклад вхідних даних

6 5 10 1 2 3
2 3
2 4
4 6
3 6
1 5

Приклад вихідних даних

0

Приклад вхідних даних

10 15 20 4 4 6
2 6
2 7
5 7
4 5
2 4
3 7
1 7
1 4
2 9
5 10
1 3
7 8
7 9
1 6
1 2

Приклад вихідних даних

952504739