CF575B.Bribes

Ruritania is a country with a very badly maintained road network, which is not exactly good news for lorry drivers that constantly have to do deliveries. In fact, when roads are maintained, they become one-way. It turns out that it is sometimes impossible to get from one town to another in a legal way – however, we know that all towns are reachable, though illegally!

Fortunately for us, the police tend to be very corrupt and they will allow a lorry driver to break the rules and drive in the wrong direction provided they receive ‘a small gift’. There is one patrol car for every road and they will request 1000 Ruritanian dinars when a driver drives in the wrong direction. However, being greedy, every time a patrol car notices the same driver breaking the rule, they will charge double the amount of money they requested the previous time on that particular road.

Borna is a lorry driver that managed to figure out this bribing pattern. As part of his job, he has to make K stops in some towns all over Ruritania and he has to make these stops in a certain order. There are N towns (enumerated from 1 to N) in Ruritania and Borna’s initial location is the capital city i.e. town 1. He happens to know which ones out of the N - 1 roads in Ruritania are currently unidirectional, but he is unable to compute the least amount of money he needs to prepare for bribing the police. Help Borna by providing him with an answer and you will be richly rewarded.

鲁里坦尼亚是一个公路网络维护状况极差的国家，这对需要频繁送货的卡车司机而言绝非好消息。事实上，每当某条道路进行维修时，它就会变成单向道路。结果发现，有时根本无法以合法方式从一个城镇到达另一个城镇——然而，我们确知所有城镇都是可达的，只是必须违反交通规则！

幸运的是，当地警察普遍腐败，只要卡车司机向他们赠送“一点小礼物”，他们就允许司机逆向行驶。每条道路上都有一辆巡逻车，当司机逆向行驶时，巡逻车会索要 1000 鲁里坦尼亚第纳尔。但这些警察极其贪婪：每当一辆巡逻车再次发现同一司机在同一条道路上违规时，其索要的贿赂金额将是此前在该道路上索要金额的两倍。

博尔纳是一名卡车司机，他已摸清了这种行贿规律。作为工作的一部分，他必须按特定顺序在鲁里坦尼亚各地的若干城镇中完成 K 次停靠。鲁里坦尼亚共有 N 个城镇（编号为 1 至 N），而博尔纳的初始位置是首都，即城镇 1。他恰好知道当前 N − 1 条道路中哪些已变为单向，但却无法算出自己为贿赂警察所需准备的最少金额。请帮助博尔纳计算出这个最小金额，你将因此获得丰厚回报。

The first line contains N, the number of towns in Ruritania. The following N - 1 lines contain information regarding individual roads between towns. A road is represented by a tuple of integers (a,b,x), which are separated with a single whitespace character. The numbers a and b represent the cities connected by this particular road, and x is either 0 or 1: 0 means that the road is bidirectional, 1 means that only the a → b direction is legal. The next line contains K, the number of stops Borna has to make. The final line of input contains K positive integers _s_1, …, s__K: the towns Borna has to visit.

• 1 ≤ N ≤ 105
• 1 ≤ K ≤ 106
• 1 ≤ a, b ≤ N for all roads
• for all roads
• 1 ≤ s__i ≤ N for all 1 ≤ i ≤ K

第一行包含整数 $N$，表示鲁里坦尼亚的城镇数量。接下来的 $N-1$ 行描述了各条连接城镇的道路信息。每条道路由一个三元组整数 $(a,b,x)$ 表示，各整数之间以单个空格分隔。其中，整数 $a$ 和 $b$ 表示该道路所连接的两个城市，$x$ 的值为 $0$ 或 $1$：若 $x=0$，表示该道路是双向通行的；若 $x=1$，则仅允许从城市 $a$ 到城市 $b$ 的单向通行。
下一行包含整数 $K$，表示博尔纳必须停靠的站点数量。输入的最后一行包含 $K$ 个正整数 $s_1,\ldots,s_K$：即博尔纳需要依次访问的城镇编号。

• $1\leq N\leq 10^5$
• $1\leq K\leq 10^6$
• 对所有道路，满足 $1\leq a,b\leq N$
• 对所有道路，满足
• 对所有 $1\leq i\leq K$，满足 $1\leq s_i\leq N$

The output should contain a single number: the least amount of thousands of Ruritanian dinars Borna should allocate for bribes, modulo 109 + 7.

输出应为一个数字：Borna 为行贿所需分配的最少里图尼亚第纳尔（单位：千）数量，对 $10^9 + 7$ 取模。

Borna first takes the route 1 → 5 and has to pay 1000 dinars. After that, he takes the route 5 → 1 → 2 → 3 → 4 and pays nothing this time. However, when he has to return via 4 → 3 → 2 → 1 → 5, he needs to prepare 3000 (1000+2000) dinars. Afterwards, getting to 2 via 5 → 1 → 2 will cost him nothing. Finally, he doesn't even have to leave town 2 to get to 2, so there is no need to prepare any additional bribe money. Hence he has to prepare 4000 dinars in total.

博尔纳首先走路线 $1\to5$，需支付 1000 第纳尔。之后，他走路线 $5\to1\to2\to3\to4$，此次无需支付任何费用。然而，当他必须经由 $4\to3\to2\to1\to5$ 返回时，则需准备 $3000$（$1000+2000$）第纳尔。随后，他经由 $5\to1\to2$ 到达城市 2 将不产生任何费用。最后，他甚至无需离开城市 2 即可到达城市 2，因此无需额外准备任何贿赂资金。因此，他总共需准备 4000 第纳尔。