现在给出了一个简单无向加权图.你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树.(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的).由于不同的最小生成树可能很多,所以你只需要输出方案数对 310113101131011 的模就可以了.
对于 100%100\%100% 的数据,1≤n≤1001 \le n \le 1001≤n≤100,1≤m≤1031 \le m \le 10^31≤m≤103,1≤c≤1091 \le c \le 10^91≤c≤109.数据保证不会出现自回边和重边,具有相同权值的边不会超过 101010 条.