#P8738. a酱的仙人掌

a酱的仙人掌

a 酱的仙人掌

题目描述

a 酱有一颗点数为nn,边数为mm 的仙人掌,这颗仙人掌没有自环和重边,且每条边有边权cc。

a 酱的仙人掌计数技巧十分高超,他很快就求出仙人掌上长度模qq为ii 的简单路径的个数fif_{i}。但是他想知道∑i=0q−1i∗fi\sum_{i=0}^{q-1} i * f_{i} 在模qq意义下的值。 请你帮帮他。

同一条无向简单路径的两个方向只计一次;不同的顶点/边序列视为不同路径。

例如样例 1 的全部 125 条无向简单路径,其长度总和模 10 为 3;若把反向再计一次会得到 6,因此本题采用前一种计数约定。

输入格式

从标准输入读入。

第一行三个整数n,m,qn,m,q。

接下来mm行,每行三个整数u,v,cu,v,c,表示有一条长度为cc的连接(u,v)(u,v) 的边,且c<qc<q。

保证不含自环和重边。

输出格式

向标准输出写出。

输出共一行,表示答案。

样例1输入

10 11 10
9 4 4
4 6 0
6 7 4
9 7 8
9 5 6
5 3 8
9 3 3
5 8 9
6 10 3
3 1 7
5 2 0

样例1输出

3

数据范围与约定

保证所有数据满足:1≤n,q≤100000,0≤m≤2n,1≤u,v≤n,0≤1\le n,q\le 100000,0\le m\le 2n,1\le u,v\le n,0\le c<qc<q。

保证 subtask1(10pts) 满足:n,q≤10:n,q\le 10。 保证 subtask2(20pts) 满足:n,q≤35:n,q\le 35。 保证 subtask3(15pts) 满足:n,q≤5000:n,q\le 5000。 保证 subtask4(15pts) 满足:n,q≤100000:n,q\le 100000,且仙人掌退化为一颗树。 保证 subtask5(40pts) 满足: 无特殊限制。