Вам надано простий неорієнтований граф із \(N\) вершинами та \(M\) ребрами. Вершини пронумеровані \(1, \dots, N\), а \(i\)-те (\(1 \leq i \leq M\)) ребро з'єднує вершини \(U_i\) і \(V_i\).

Є \(2^N\) способи зафарбувати кожну вершину червоним або синім кольором.

Знайдіть число за модулем 998244353 таких шляхів, які задовольняють усі наступні умови:

• Є рівно \(K\) вершин, пофарбовані червоним кольором.

• Існує парна кількість ребер, що з'єднують вершини, пофарбовані в різні кольори.

Обмеження

• \(2 \leq N \leq 2 \times 10^5\)
• \(1 \leq M \leq 2 \times 10^5\)
• \(0 \leq K \leq N\)
• \(1 \leq U_i \lt V_i \leq N\), (\(1 \leq i \leq M\))
• \((U_i, V_i) \neq (U_j, V_j)\), \((I \neq j)\)
• Усі значення у вхідних даних є цілими числами.

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

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

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

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

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

У вихідний потік виведіть відповідь.

Примітка

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

Наступні два шляхи задовольняють умови.

• Зафарбуйте вершини 1 і 2 червоним кольором, а вершини 3 і 4 — синім.
• Зафарбуйте вершини 3 і 4 червоним кольором, а вершини 1 і 2 — синім.

У будь-якому з описаних вище способів 2-е і 3-е ребра з'єднують вершини, пофарбовані в різні кольори.

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

4 4 2
1 2
1 3
2 3
3 4

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

2

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

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

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

64