In this country, there are $n$ cities. Initially, there are several bidirectional roads between the cities, causing these cities to form $t \ge 2$ connected components. Specifically, the absolute difference between the sizes of any two of these connected components is at most $k$, where $0 \le k \le 1$. To facilitate urban construction and development, additional bidirectional roads were built between some $t$ cities among the $n$ cities, such that all cities became connected.

Given all the roads after the additional construction, you need to calculate how many sets of bidirectional roads $E'$ could have been the ones added later. Output the answer modulo $998,244,353$.

Formally, given an undirected connected graph $G = (V, E)$ with $n$ vertices and $m$ edges, find the number of subgraphs $G' = (V, E')$ such that $E' \neq \emptyset$, $G - E'$ has exactly $t$ connected components (where $t$ is the number of vertices in the set of cities where additional roads were built), and the difference in size between any two connected components is at most $k$, where $0 \le k \le 1$. Output the answer modulo $998,244,353$.

Input

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

The next $m$ lines each contain two positive integers $u, v$, representing a bidirectional road between city $u$ and city $v$. It is guaranteed that $u \neq v$.

Output

Output a single integer representing the answer modulo $998,244,353$.

Examples

Input 1

4 4 1
1 2
2 3
1 3
3 4

Output 1

2

Note

There are two cases: Initially, there was only the road $(3, 4)$, resulting in three connected components: $\{1\}, \{2\}, \{3, 4\}$. Later, cities $1, 2, 3$ decided to build additional roads $(1, 2), (2, 3), (1, 3)$ among them, making all cities connected. Initially, there were no roads, resulting in four connected components: $\{1\}, \{2\}, \{3\}, \{4\}$. Later, cities $1, 2, 3, 4$ decided to build additional roads $(1, 2), (2, 3), (1, 3), (3, 4)$ among them, making all cities connected.

Constraints

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$.