【题目描述】

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

给定$k$，求有多少个**.有.序**路径对$(P_1,P_2)$（不要求是简单路径）满足：

•每个点至少被两条路径中的一条覆盖。

•每个点被两条路径覆盖的次数和不超过$k$。

答案对$998244353$取模。

【输入格式】

第一行三个整数$n,m,k$。

接下来m行，每行两个整数$u,v$，表示存在一条$u$连向$v$的有向边。

【输出格式】

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

【样例1输入】

5 5 1 
1 2 
2 3 
3 1 
2 4 
3 5 

【样例1输出】

6

【样例1解释】

合法的$6$种路径对分别是：

•$(1→2→4;3→5)，(3→5;1→2→4)$，

•$(1→2→3→5;4)，(4;1→2→3→5)$，

•$(3→1→2→4;5)，(5;3→1→2→4)$。

【样例2输入】

3 2 2 
1 2 
2 3 

【样例2输出】

19 

【样例3输入】

3 3 2 
1 2 
2 3 
3 1 

【样例3输出】

105

【数据范围】

对于所有数据$，2≤n≤2000，1≤m≤4000，0≤k<998244353$。

特殊性质A：图不存在环。