题目描述

给一张包含 $N$ 个结点的树。

在树上，对于有些边 $(a,b)$，$a→b$ 和 $b→a$ 都无需花费，我们称这种边为无向边；对于另一些边，$a→b$ 无需花费，而 $b→a$ 需要花费，且第 $i$ 次从 $b$ 到 $a$ 时花费为 $2^{i-1}$，我们将这种边称为有向边。

给你一个长度为 $K$ 的数列 $s_1, s_2,\dots, s_K$，你要从结点 $s_1$ 前往 $s_2$，再从 $s_2$ 去往 $s_3$……一直到 $s_K$。

试求最小的花费 $\bmod (10^9+7)$。

输入格式

第一行，一个整数 $N$。

接下来的 $N-1$ 行，每行三个整数 $a,b,x$，

• 如果 $x=0$，边 $(a,b)$ 为无向边；
• 如果 $x=1$，边 $(a,b)$ 为有向边。

第 $N+1$ 行，一个整数 $K$。
下一行，$K$ 个整数 $s_1, s_2, \dots, s_K$。

$1\le N\le 10^{5}$，$1\le K\le 10^{6}$，$1\le a,b\le N$，$1\le s_{i}\le N$。

输出格式

一个整数表示答案。

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

4

$1 → 5$，路径上总花费为 $1$。
$5 → 1 → 2 → 3 → 4$，路径上无花费。
$4 → 3 → 2 → 1 → 5$，路径上总花费为 $3$。
$5 → 1 → 2$，路径上无花费。