AT_abc372_f [ABC372F] Teleporting Takahashi 2

有一张有 $N$ 个顶点和 $N+M$ 条边的简单有向图 $G$。顶点从 $1$ 到 $N$ 标号，边从 $1$ 到 $N+M$ 标号。 第 $i(1\le i\le N)$ 条边从 $i$ 连向 $i+1$。（这里的 $N+1$ 号点是 $1$ 号点。） 第 $N+i(1\le i\le M)$ 条边从 $X_i$ 连向 $Y_i$。 高桥在 $1$ 号点。在每个顶点，他可以移动到任何与这个顶点有边相连的点。 计算出他有多少种方式能够移动 $K$ 次。 也就是说，找到满足以下条件的长度为 $K+1$ 的序列 $(v_0,v_1,\dots,v_K)$ 的数量： - 对于 $i=0,1,\dots,K$，$1\le v_i\le N$。 - $v_0=1$。 - 对于 $i=1,2,\dots,K$ 存在一条从 $v_{i-1}$ 到 $v_i$ 的边。 因为答案可能很大，所以你需要输出答案对 $998244353$ 取模后的值。

第一行，三个整数 $N,M,K$。 第 $2$ 行到第 $M+1$ 行，每行两个整数 $X_i,Y_i$。

输出一个整数，表示答案对 $998244353$ 取模后的值。 ### 样例 1 解释  上图为图 $G$。以下是高桥的 $5$ 种移动方式： - 顶点 $1\to$ 顶点 $2\to$ 顶点 $3\to$ 顶点 $4\to$ 顶点 $5\to$ 顶点 $6$。 - 顶点 $1\to$ 顶点 $2\to$ 顶点 $5\to$ 顶点 $6\to$ 顶点 $1\to$ 顶点 $2$。 - 顶点 $1\to$ 顶点 $2\to$ 顶点 $5\to$ 顶点 $6\to$ 顶点 $1\to$ 顶点 $4$。 - 顶点 $1\to$ 顶点 $4\to$ 顶点 $5\to$ 顶点 $6\to$ 顶点 $1\to$ 顶点 $2$。 - 顶点 $1\to$ 顶点 $4\to$ 顶点 $5\to$ 顶点 $6\to$ 顶点 $1\to$ 顶点 $4$。

- $2\le N\le 2\times10^5$ - $0\le M\le 50$ - $1\le K\le 2\times 10^5$ - $1\le X_i,Y_i\le N,X_i\not=Y_i$ - 所有的 $N+M$ 条边都是不同的。 - 所有输入都为整数。