传送的高桥 2

题目描述

有一个具有 $N$ 个顶点和 $N+M$ 条边的简单有向图 $G$。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N+M$。

边 $i$ $(1 \leq i \leq N)$ 从顶点 $i$ 指向顶点 $i+1$。（这里，顶点 $N+1$ 视为顶点 $1$。）

边 $N+i$ $(1 \leq i \leq M)$ 从顶点 $X_i$ 指向顶点 $Y_i$。

高桥在顶点 $1$。在每个顶点，他可以移动到从当前顶点出发的有向边所指向的任意顶点。

请计算他恰好移动 $K$ 次的方案数。

也就是说，求满足以下三个条件的长度为 $K+1$ 的整数序列 $(v_0, v_1, \dots, v_K)$ 的个数：

• 对 $i = 0, 1, \dots, K$，有 $1 \leq v_i \leq N$
• $v_0 = 1$
• 对 $i = 1, 2, \ldots, K$，存在从顶点 $v_{i-1}$ 指向顶点 $v_i$ 的有向边

由于这个数可能非常大，请对 $998244353$ 取模输出。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$ $K$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_M$ $Y_M$

输出格式

输出取模 $998244353$ 后的答案。

样例

6 2 5
1 4
2 5

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$

10 0 200000

1

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

451022766

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 50$
• $1 \leq K \leq 2 \times 10^5$
• $1 \leq X_i, Y_i \leq N$，$X_i \neq Y_i$
• $N+M$ 条有向边互不相同
• 输入中的所有数值均为整数