题号：NC22733
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
给你一棵n个节点的仙人掌，边有长度，小G想知道长度
为0,1,2...Q-1的路径分别有多少条。路径合法当且仅当不经过重复的点。由于过多的数字会让小G眼花缭乱，你只需要输出
对Q取模的值。其中
为长度
的路径数。
输入描述:
第一行三个正整数n,m,Q，表示仙人掌的点数和边数以及模数。
接下来m行，每行三个整数(x,y,z)，表示x和y之间有一条长度为z的边。点的编号为1~n。
输出描述:
一行一个正整数，表示答案。
示例1
输入
复制
4 4 10
1 2 1
2 3 2
3 4 5
3 1 9
备注:
，保证没有重边自环