Determinant

Um_nik has a simple connected undirected graph with the following property:

For any subset $A$ of $k+1$ vertices of the graph, there exist two vertices $a, b \in A$ and some edge $e$, such that all paths from $a$ to $b$ contain edge $e$.

Please help him find the determinant of the adjacency matrix of his graph modulo 998 244 353.

The first line contains three integers $n$, $m$, $k$: the number of vertices and edges in the graph and the given parameter ($1 \le n \le 25\,000$, $n - 1 \le m \le 500\,000$, $1 \le k \le 25$).

The next $m$ lines describe the edges of the graph. Each line contains two integers $u$ and $v$, the two vertices connected by an edge ($1 \le u, v \le n$, $u \ne v$).

It is guaranteed that the graph is connected and that for any subset $A$ of $k+1$ vertices, there exist two vertices $a, b \in A$ and an edge $e$ such that all paths from $a$ to $b$ contain edge $e$. It is also guaranteed that the graph has no multiple edges.

Print a single integer: the determinant of the adjacency matrix of Um_nik's graph modulo 998 244 353.