来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 06 套，第 3 题。原题标号：C；原本地编号：Z4P1-06-C。

题目背景

小 D 上初中了，他迷上了一款有趣的游戏。

题目描述

游戏规则是这样的：一共有 $n$ 个能量节点，每个节点的初始能量值为 $1$。有 $m$ 种充能方式，每一种充能方式由 $u,v,c$ 组成，表示 $v$ 节点可以获得 $u$ 节点 $c$ 倍的能量，最后要让每个点都获得最大的能量。

其中有一些节点对于小 D 很重要，因此小 D 很好奇，这些节点的最大能量是多少呢？

由于答案可能很大，因此要输出答案对 $10^9+7$ 取模后的结果。

输入格式

第 $1$ 行 $3$ 个整数 $n,m,T$，分别表示能量节点的数量，充能方式的数量，以及询问的数量。

第 $2$ 行到第 $m+1$ 行，一行三个整数 $u,v,c$ 表示一种充能方式。

接下来一行 $T$ 个整数，一个整数表示一个询问。

输出格式

共 $T$ 行：每行一个整数，表示每次询问的答案，答案对 $10^9 + 7$ 取模。

输入输出样例 #1

输入 #1

3 2 2
1 2 2000000
2 3 2000000
2 3

输出 #1

2000001
1972001

说明/提示

样例 $1$ 解释：三个节点初始有 $1$ 的能量，节点 $2$ 获得了由 $1$ 贡献的 $2000000$ 的能量，共有$2000001$ 的能量；节点 $3$ 在获得节点 $2$ 的能量后，共有 $4000002000001$ 的能量，取模后为 $1972001$。

数据范围

对于 $30\%$ 的数据：

$1\le n,T\le 1000,m\le 2000$。

对于 $100\%$ 的数据：

$1\le n,T \le 10^6,m \le 2 \times 10^6$

$u\neq v,1\le u,v\le n$

$p \le 2\times 10^6$

$s\le n$。