Counting Extra Road Configurations

In a kingdom there are (n) cities. Initially some bidirectional roads connect these cities, forming (t \ge 2) disconnected components. Moreover, the absolute difference in the sizes of any two components does not exceed (k) (with (0 \le k \le 1)). Later, extra bidirectional roads are built among a chosen set of (t) cities (that is, only these (t) cities have extra roads built between them) so that the entire graph becomes connected.

Given the final connected undirected graph (G=(V,E)) with (n) vertices and (m) edges, determine in how many ways one can choose a nonempty subset of edges (E' \subseteq E) which could possibly represent the extra roads. Let (V') be the set of vertices incident to an edge in (E'). The chosen subset (E') is valid if and only if in the graph (G - E' = (V, E \setminus E')), there are exactly (|V'|) connected components and each connected component contains exactly one vertex from (V'). Furthermore, if the sizes of these connected components are (s_1, s_2, \ldots, s_{|V'|}) then they must satisfy (\max(s_i) - \min(s_i) \le k). Output the number of valid choices modulo (998244353).

inputFormat

The first line contains three integers (n), (m) and (k) (with (1 \le n \le 15) and (0 \le k \le 1)). Each of the next (m) lines contains two integers (u) and (v) (1-indexed) representing a bidirectional edge between cities (u) and (v). It is guaranteed that the given graph is connected.

outputFormat

Output a single integer representing the number of valid subsets (E') modulo (998244353).

sample

3 3 0
1 2
2 3
3 1

1