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$。

输入输出样例 #1

输入 #1

6 2 5
1 4
2 5

输出 #1

5

输入输出样例 #2

输入 #2

10 0 200000

输出 #2

1

输入输出样例 #3

输入 #3

199 10 1326
122 39
142 49
164 119
197 127
188 145
69 80
6 120
24 160
18 154
185 27

输出 #3

451022766

说明/提示

• $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$ 条边都是不同的。
• 所有输入都为整数。