#P8738. a酱的仙人掌
a酱的仙人掌
a 酱的仙人掌
题目描述
a 酱有一颗点数为,边数为 的仙人掌,这颗仙人掌没有自环和重边,且每条边有边权。
a 酱的仙人掌计数技巧十分高超,他很快就求出仙人掌上长度模为 的简单路径的个数。但是他想知道 在模意义下的值。 请你帮帮他。
同一条无向简单路径的两个方向只计一次;不同的顶点/边序列视为不同路径。
例如样例 1 的全部 125 条无向简单路径,其长度总和模 10 为 3;若把反向再计一次会得到 6,因此本题采用前一种计数约定。
输入格式
从标准输入读入。
第一行三个整数。
接下来行,每行三个整数,表示有一条长度为的连接 的边,且。
保证不含自环和重边。
输出格式
向标准输出写出。
输出共一行,表示答案。
样例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
数据范围与约定
保证所有数据满足: 。
保证 subtask1(10pts) 满足。 保证 subtask2(20pts) 满足。 保证 subtask3(15pts) 满足。 保证 subtask4(15pts) 满足,且仙人掌退化为一颗树。 保证 subtask5(40pts) 满足: 无特殊限制。