鲁里塔尼亚是一个道路网络维护非常糟糕的国家,这对于经常需要送货的卡车司机来说并不是一个好消息。事实上,当道路得到维护时,它们就会变成单行道。事实证明,有时不可能以合法方式从一个城镇到达另一个城镇 - 然而,我们知道所有城镇都是可以到达的,尽管是非法的!
对我们来说幸运的是,警察往往非常腐败,只要他们收到“一份小礼物”,他们就会允许卡车司机违反规则并朝错误的方向行驶。每条路都有一辆巡逻车,当司机逆向行驶时,他们会索要 1000 鲁里塔尼亚第纳尔。然而,由于贪婪,巡逻车每次发现同一个司机违反规则时,都会收取上一次在该特定道路上要求的双倍费用。
博尔纳是一名卡车司机,他成功地弄清楚了这种贿赂模式。作为工作的一部分,他必须在鲁里塔尼亚各地的一些城镇进行 K 次停留,并且必须按一定的顺序进行这些停留。鲁里塔尼亚有 N 个城镇(从 1 到 N 列举),博尔纳的初始位置是首都,即城镇 1。他恰好知道鲁里塔尼亚的 N - 1 条道路中目前有哪些是单向的,但他无法计算出准备贿赂警察至少需要多少钱。为博纳提供答案来帮助他,你将获得丰厚的回报。
输入
第一行包含 N,即鲁里塔尼亚的城镇数量。以下 N - 1 行包含有关城镇之间的各个道路的信息。道路由整数元组 (a,b,x) 表示,它们之间用单个空格字符分隔。数字a和b代表该特定道路连接的城市,x为0或1:0表示该道路是双向的,1表示仅a→b方向是合法的。下一行包含 K,即博尔纳必须停靠的次数。输入的最后一行包含 K 个正整数 s1, …, sK:Borna 必须访问的城镇。
- 1 ≤ N ≤ 105
- 1 ≤ K ≤ 106
- 所有道路 1 ≤ a, b ≤ N
- $$x \in \{0, 1\}$$ 对于所有道路
- 对于所有 1 ≤ i ≤ K,1 ≤ si ≤ N
输出
输出应包含一个数字:博尔纳应分配用于贿赂的最少数千鲁里塔尼亚第纳尔,模 109 + 7。
示例
输入 #1
5 1 2 0 2 3 0 5 1 1 3 4 1 5 5 4 5 2 2
输出 #1
4
注意
博尔纳首先走路线1→5,需要支付1000第纳尔。之后,他选择路线 5 → 1 → 2 → 3 → 4,这次无需支付任何费用。然而,当他必须通过4→3→2→1→5返回时,他需要准备3000(1000+2000)第纳尔。之后,通过5 → 1 → 2到达2将不会花费他任何费用。最后,他甚至不需要离开2号城镇就可以到达2号,所以不需要准备任何额外的贿赂钱。所以他总共要准备4000第纳尔。