给你一个简单的加权连通无向图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。
图中长度 $$$k$$$ 的路径是 $$$k+1$$$ 顶点 $$$v_1, v_2, \dots, v_{k+1}$$$ 的序列,使得对于每个 $$$i$$$ $$$(1 \le i \le k)$$$,边 $$$(v_i, v_{i+1})$$$ 存在于图表。从某个顶点 $$$v$$$ 开始的路径也有顶点 $$$v_1=v$$$。请注意,边和顶点允许多次包含在路径中。
路径的权重是其中边的总权重。
对于从 $$$1$$$ 到 $$$q$$$ 的每个 $$$i$$$,考虑一条从顶点 $$$1$$$ 开始、长度为最大权重 $$$i$$$ 的路径。这些 $$$q$$$ 路径的权重总和是多少?
答案可能相当大,因此打印它对 $$$10^9+7$$$ 取模。
输入
第一行包含三个整数 $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \le n \le 2000$$$; $$$n - 1 \le m \le 2000$$$; $$$m \le q \le 10^9$$$) — 图中的顶点数,边数图中的长度以及答案中应包含的长度数。
接下来的 $$$m$$$ 行包含一条边的描述:三个整数 $$$v$$$、$$$u$$$、$$$w$$$ ($$$1 \le v, u \le n$$$; $$$1 \le w \le 10^6$$$) - 两个顶点 $$$v$$$ 和 $$$u$$$ 通过权重为 $$$w$$$ 的无向边。该图不包含循环,也不包含多重边。保证给定的边形成连通图。
输出
打印单个整数 - 从顶点 $$$1$$$ 开始的路径权重总和,长度为 $$$1, 2, \dots, q$$$ 模 $$$10^9+7$$$。
示例
输入 #1
7 8 25 1 2 1 2 3 10 3 4 2 1 5 2 5 6 7 6 4 15 5 3 1 1 7 3
输出 #1
4361
输入 #2
2 1 5 1 2 4
输出 #2
60
输入 #3
15 15 23 13 10 12 11 14 12 2 15 5 4 10 8 10 2 4 10 7 5 3 10 1 5 6 11 1 13 8 9 15 4 4 2 9 11 15 1 11 12 14 10 8 12 3 6 11
输出 #3
3250
输入#4
5 10 10000000 2 4 798 1 5 824 5 2 558 4 1 288 3 4 1890 3 1 134 2 3 1485 4 5 284 3 5 1025 1 2 649
输出#4
768500592
注意
这是第一个示例的图表:
一些最大权重路径是:
- 长度 $$$1$$$:边 $$$(1, 7)$$$ — 重量 $$$3$$$;
- 长度 $$$2$$$:边 $$$(1, 2), (2, 3)$$$ — 重量 $$$1+10=11$$$;
- 长度 $$$3$$$:边 $$$(1, 5), (5, 6), (6, 4)$$$ — 重量 $$$2+7+15=24$$$;
- 长度 $$$4$$$:边 $$$(1, 5), (5, 6), (6, 4), (6, 4)$$$ — 重量 $$$2+7+15+15=39$$$;
- $$$\点$$$
所以答案是 $$$25$$$ 项的总和:$$$3+11+24+39+\dots$$$
在第二个示例中,最大权重路径的权重为 $$$4$$$、$$$8$$$、$$$12$$$、$$$16$$$ 和 $$$20$$$。