有 N 座城市，编号 1\sim N。起初**任意两个不同城市之间都有一条双向道路**（即完全图），

但由于年久失修，有 M 条道路已经无法使用：第 i 条失效的道路连接城市 U_i 与 V_i。

小Z要计划一个**从城市 1 出发、最终回到城市 1 的 K 天旅行**。

形式化地说，一个 K 天旅行是一个长度为 K+1 的城市序列 (A_0,A_1,\dots,A_K)，满足：

- A_0 = A_K = 1；

- 对每个 0\le i\le K-1，A_i \ne A_{i+1}（**每天必须换一座城市**，不能待在原地），

  且城市 A_i 与 A_{i+1} 之间**仍存在可用的道路**。

求不同的 K 天旅行的数量，对 998244353 取模。

（两个旅行 (A_0,\dots,A_K) 与 (B_0,\dots,B_K) 不同，当且仅当存在某个 i 使 A_i\ne B_i。）

第一行三个整数 N,M,K（2 \leq N \leq 5000，0 \leq M \leq \min\!\left(\frac{N(N-1)}{2},\,5000\right)，2 \leq K \leq 5000）。

接下来 M 行，第 i 行两个整数 U_i,V_i（1 \leq U_i < V_i \leq N），表示一条失效道路的两端。所有 (U_i,V_i) 两两不同。

输出答案对 998244353 取模的结果。

**样例1说明**：共有 4 种旅行：(1,2,1,2,1)、(1,2,1,3,1)、(1,3,1,2,1)、(1,3,1,3,1)。

数据范围与约定

- 2\le N\le 5000；

- 0\le M\le \min\!\left(\dfrac{N(N-1)}{2},\,5000\right)；

- 2\le K\le 5000；

- 1\le U_i，且所有 (U_i,V_i) 两两不同；

| 20% | 1~5 | 20 | N,M,K \le 100） | 

| 60% | 6~15 | 40 | N,M,K \le 500 | 

| 100% | 16~25 | 40 | N,M,K\le 5000 |