题目描述

给你一张 $n$ 个点 $m$ 条边的有向图 $G$，保证每个点最多在一个简单环内。

给定 $k$，我们想知道有多少组路径对 $(P_1,P_2)$ 满足：

• 对于每个点 $v$，$v$ 至少被 $P_1$ 和 $P_2$ 中的一条覆盖；
• 对于每个点 $v$，$v$ 在 $P_1,P_2$ 中出现的次数的总和不超过 $k$。

注意这里的 $P_1,P_2$ 可以经过一个点多次，且可以为空。

由于答案可能很大，输出答案模 $P=998244353$ 的值。

输入格式

输入的第一行包含三个正整数 $n,m,k$，分别表示节点个数、边数和参数。

接下来 $m$ 行，第 $i$ 行两个正整数 $x_i,y_i$，描述一条从 $x_i$ 指向 $y_i$ 的有向边。

输出格式

一行一个整数，表示答案。

样例输入

2 2 1
1 2
2 1

样例输出

6

样例解释

所有方案如下：

P1 = (1, 2)   P2 = ()
P1 = (2, 1)   P2 = ()
P1 = (1)      P2 = (2)
P1 = (2)      P2 = (1)
P1 = ()       P2 = (1, 2)
P1 = ()       P2 = (2, 1)

数据范围

对于所有数据，保证：

• $1\le n\le2000$
• $0\le m\le4000$
• $0\le k\le10^9$
• $1\le x_i,y_i\le R\le n\land x_i\ne y_i$