图上慢跑

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个包含 $n$ 个顶点、$m$ 条边的简单带权无向连通图。路径允许重复经过顶点和边。

对每个 $i=1,2,\ldots,q$，考虑所有从顶点 $1$ 出发、恰好经过 $i$ 条边的路径，记其中最大的边权和为 $F_i$。

求

输入格式

第一行包含三个整数 $n,m,q$。

接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示顶点 $u,v$ 之间有一条权值为 $w$ 的无向边。图中无自环、无重边，且保证连通。

输出格式

输出所求和对 $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

数据范围

$2\le n\le2000$，$n-1\le m\le2000$，$m\le q\le10^9$，$1\le w\le10^6$。