题目描述

给出无向带权图，每个点都有一个人，每个人有独立的价值，初始为 $0$，进行如下 $q$ 次操作。

对于第 $i$ 次操作：

• 若 $i \bmod 3 \neq 0$，每个人走到相邻点中下标最小的一个；否则，每个人走到相邻点中下标最大的一个。
• 设边权为 $w$，对于某个人，若同时同向经过他所走的这一条边的人数为 $p$，则他的价值增加 $w p$。
• 若某个人没有相邻点，则他不需要移动，价值也不会改变。

给出 $k$ 个关键人，求 $q$ 次操作后 $k$ 个关键人的价值和对 $10^9 + 7$ 取模后的值。

输入格式

第一行三个整数 $n, m, q$，表示无向图的点数、边数与操作次数。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示一条连接点对 $(u, v)$ 的无向边，边权为 $w$。

一行一个整数 $k$，表示关键人数。

接下来一行 $k$ 个不同的整数，表示每个关键人的最初的位置。

输出格式

一行一个整数，表示所求答案。

样例1

样例输入

3 3 2
1 2 1
2 3 1
1 3 1
2
1 2

样例输出

5

样例2

样例输入

5 6 4
1 4 3
2 5 1
3 1 2
1 2 3
5 4 0
3 4 3
3
1 4 5

样例输出

58

数据范围

本题开启捆绑测试。

各测试点的附加限制及分值如下表所示。

对于全部数据保证：$1 \le n,m \le 10^6$，$1 \le u,v,k \le n$，$0 \le w,q \le 10^9$，并且图中无重边、自环。