【模板】Matrix-Tree 定理
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一张 n 个结点 m 条边的带权图（可能为无向图，可能为有向图）。

定义其一个生成树 T 的权值为 T 中所有边权的乘积。

求其所有不同生成树的权值之和，对 取模。

---

注意：

1. 本题中，有向图的生成树指的是 以 1 为根的外向树；

2. 两棵生成树 T_1,T_2 不同，当且仅当存在存在一条边 e，满足 。

输入描述:

第一行：三个整数 n,m,t，分别表示图的结点数量，边的数量和图的类型（ 时为无向图， 时为有向图）。
接下来 m 行：每行三个整数 u,v,w。
如果 ，表示 u,v 之间有一条权值为 w 的无向边；
如果 ，表示从 u 到 v 有一条权值为 w 的有向边。

对于  的数据：。
图中 可能 存在重边和自环，重边算作多条边。

输出描述:

第一行：一个整数 ans，表示给定的图的生成树权值和对  取模的结果。
示例1

输入

复制 
5 8 0
2 3 1
1 2 3
4 5 1
4 2 2
3 5 2
3 4 3
3 4 1
3 3 5

输出

复制 
144
示例2

输入

复制 
5 9 1
1 2 3
3 2 1
1 3 1
2 4 2
3 5 1
4 3 4
3 5 1
5 4 1
4 4 6

输出

复制 
72

备注:

原题链接：https://www.luogu.com.cn/problem/P6178