题目描述

小Z想去一个城市旅行，他将这个城市抽象为 $n$ 个节点 , $m$ 条边的有向图，每条边有长度。

小Z想知道有多少条不同的旅行路线，路线中经过边的长度之和恰好为 $k$ 。

小Z可以以任意节点为起点，两条路径相同当且仅当经过边的序列完全相同 。

你只需要输出答案模 $998244353$ 意义下的结果。

输入格式

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

接下来 $m$ 行每行三个整数 $u_i,v_i,w_i$ 表示一条边从 $u_i$ 出发，到达 $v_i$ ，长度为 $w_i$ 。

输出格式

输出一个整数表示答案模 $998244353$ 意义下的结果。

输入输出样例 #1

输入 #1

3 6 3
1 2 1
2 3 1
3 1 2
2 1 1
3 2 1
1 3 2

输出 #1

12

输入输出样例 #2

输入 #2

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

输出 #2

694

说明/提示

对于第一个样例,有 $12$ 条路径分别是:

1,2,3,2

1,2,1,2

1,3,2

2,3,2,1

2,3,2,3

2,1,2,1

2,1,2,3

2,1,3

2,3,1

3,2,3,2

3,2,1,2

3,1,2

对于 $30\%$ 的数据 : $1 \le n \le 5 , 1 \le m \le 10 ,1 \le w_i \le 10 , 1 \le k \le 10$

对于另外 $40\%$ 的数据 : $1 \le n \le 10^2 , 1 \le m \le 10^3 ,w_i=1 , 1 \le k \le 10^6$

对于 $100\%$ 的数据 : $1 \le n \le 10^2 , 1 \le m \le 10^3 ,1 \le w_i \le 100 ,\sum w_i \le max(n+m,100) , 1 \le k \le 10^9$

可以有重边,可以有自环,只满足 $1 \le u_i,v_i \le n$ 什么边都可以有

数据有梯度