Problem Description

In this country, there are $n$ cities initially connected by several bidirectional roads, resulting in $t \ge 2$ connected components. Specifically, the absolute difference in sizes between any two of these connected components does not exceed $0 \le k \le 1$. For the convenience of urban construction and development, $t$ cities among the $n$ cities have built at least one additional bidirectional road among these $t$ cities to make all cities connected.

Given all the roads after the additional construction, you need to calculate which sets of bidirectional roads $E'$ could be the ones that were later added. Please output the result modulo $998,244,353$.

That is, given an undirected connected graph $G = (V, E)$ with $n$ vertices and $m$ edges, you are asked to determine how many subgraphs $G' = (V', E')$ of this graph exist, such that $E' \ne \varnothing$ and $G - E'$ has exactly $|V'|$ connected components, with the absolute difference in sizes between any two components not exceeding $k$, where $0 \le k \le 1$. Please output the result modulo $998,244,353$.

Input Format

The first line of input contains three positive integers $n, m, k$, representing the number of cities, the number of roads after construction, and the upper limit of the absolute difference in sizes between any two connected components, respectively.

The next $m$ lines each contain two positive integers $u, v$, indicating that there is a bidirectional road between city $u$ and city $v$, with $u \ne v$.

Output Format

Output a single number representing the result modulo $998,244,353$.

Sample Input and Output

Input Sample #1

4 4 1
1 2
2 3
1 3
3 4

Output Sample #1

2

Input Sample #2

See attached file cities/cities2.in

Output Sample #2

See attached file cities/cities2.ans

Input Sample #3

See attached file cities/cities3.in

Output Sample #3

See attached file cities/cities3.ans

Input Sample #4

See attached file cities/cities4.in

Output Sample #4

See attached file cities/cities4.ans

Notes/Hints

[Sample 1 Explanation]

There are two possible scenarios:

• Initially, there was only one road $(3, 4)$, resulting in three connected components: $\{1\}$, $\{2\}$, and $\{3, 4\}$. Later, cities $1, 2, 3$ decided to build additional roads $(1, 2)$, $(2, 3)$, and $(1, 3)$ among themselves to connect all cities.
• Initially, there were no roads, resulting in four connected components: $\{1\}$, $\{2\}$, $\{3\}$, and $\{4\}$. Later, cities $1, 2, 3, 4$ decided to build additional roads $(1, 2)$, $(2, 3)$, $(1, 3)$, and $(3, 4)$ among themselves to connect all cities.

[Data Range]

For all data, it is guaranteed that: $3 \le n \le 10^5$, $n - 1 \le m \le 2 \times 10^5$, $0 \le k \le 1$.

见题面 Input 部分

见题面 Output 部分