행렬식

Um_nik은 다음 성질을 갖는 단순 연결 무방향 그래프가 있다.

그래프의 정점 $k+1$개로 이루어진 임의의 부분집합 $A$에 대해, 두 정점 $a, b \in A$와 어떤 간선 $e$가 존재하여, $a$에서 $b$로 가는 모든 경로가 간선 $e$를 지난다.

Um_nik의 그래프 인접 행렬의 행렬식을 998 244 353으로 나눈 나머지를 구하는 것을 도와 달라.

첫 줄에 정수 $n$, $m$, $k$가 주어진다. 각각 정점 수, 간선 수, 주어지는 매개변수이다 ($1 \le n \le 25\,000$, $n - 1 \le m \le 500\,000$, $1 \le k \le 25$).

다음 $m$개의 줄에 그래프의 간선이 주어진다. 각 줄에는 간선으로 연결된 두 정점 $u$와 $v$가 주어진다 ($1 \le u, v \le n$, $u \ne v$).

그래프는 연결되어 있고, 정점 $k+1$개로 이루어진 임의의 부분집합 $A$에 대해 두 정점 $a, b \in A$와 간선 $e$가 존재하여 $a$에서 $b$로 가는 모든 경로가 $e$를 지난다고 보장된다. 또한 그래프에 중복 간선이 없다고 보장된다.

Um_nik 그래프 인접 행렬의 행렬식을 998 244 353으로 나눈 나머지를 정수 하나로 출력한다.