普及模拟赛 6 - C

题目背景

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

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

每一种充能方式至多使用一次，且保证不会出现循环充能的情况，即如果对于每种充能方式，看作一条从 $u$ 到 $v$ 的有向边，这张图中不会存在环。

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

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

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

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

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

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

3 2 2
1 2 2000000
2 3 2000000
2 3

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$ 。