Description

有一个有向图 $G$，它包含 $N$ 个顶点和 $N + M$ 条边。顶点从 $1$ 到 $N$ 编号，边从 $1$ 到 $N + M$ 编号。

图中的边如下构造：

• 对于每个 $1 \le i \le N$，存在一条从顶点 $i$ 指向顶点 $i+1$ 的边。若 $i = N$，则这条边从顶点 $N$ 指向顶点 $1$。
• 对于每个 $1 \le i \le M$，存在一条从顶点 $X_i$ 指向顶点 $Y_i$ 的边。

现在，你位于顶点 $1$。你每次可以沿一条从当前位置出发的有向边移动到另一个顶点。请你计算恰好移动 $K$ 次的不同方式数量。

也就是说，你需要计算满足以下所有条件的整数序列 $(v_0, v_1, \ldots, v_K)$ 的个数：

• 对所有 $0 \le i \le K$，有 $1 \le v_i \le N$；
• $v_0 = 1$；
• 对所有 $1 \le i \le K$，图中存在一条从 $v_{i-1}$ 到 $v_i$ 的有向边。

由于答案可能很大，请输出答案对 $998244353$ 取模的结果。

Format

Input

输入第一行包含三个整数 $N, M, K$（$2 \le N \le 10^5$, $0 \le M \le 50$, $1 \le K \le 10^5$）。

接下来 $M$ 行，每行包含两个整数 $X_i, Y_i$（$1 \le X_i, Y_i \le N, X_i \ne Y_i$），表示一条从 $X_i$ 到 $Y_i$ 的有向边。

Output

输出一个整数，表示你恰好移动 $K$ 次的路径数量，对 $998244353$ 取模。

Samples

6 2 5
1 4
2 5

5

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

451022766