B. Взятки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В стране Руритании дорожная сеть организована из рук вон плохо, это не радует дальнобойщиков, которым постоянно надо что-то перевозить. Некоторые дороги являются односторонними, некоторые — двусторонними. Оказывается, что иногда невозможно добраться из одного города до другого законно — однако взятка, данная правильному человеку, может помочь добраться куда угодно!

К счастью для нас, полицейские позволят дальнобойщику нарушить правила и проехать в запрещённом направлении при условии, что машине ДПС будет предоставлено соответствующее вознаграждение. На каждой дороге расположено по одной машине ДПС и они просят 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: города, которые надо посетить Борне.

  • 1 ≤ N ≤ 105
  • 1 ≤ K ≤ 106
  • 1 ≤ a, b ≤ N для всех дорог
  • для всех дорог
  • 1 ≤ si ≤ N для всех 1 ≤ i ≤ K
Выходные данные

Выведите единственное целое число: наименьшее количество тысяч Руританских динаров, необходимое Борне для взяток, по модулю 109 + 7.

Примеры
Входные данные
5
1 2 0
2 3 0
5 1 1
3 4 1
5
5 4 5 2 2
Выходные данные
4
Примечание

Борна сперва идет по пути 1 → 5 и должен оплатить 1000 динаров. Затем он идет по пути 5 → 1 → 2 → 3 → 4 и в этот раз ничего не платит. Однако когда ему придется вернуться через 4 → 3 → 2 → 1 → 5, ему нужно подготовить 3000 (1000+2000) динаров. Затем дорога до 2 через 5 → 1 → 2 ничего не будет ему стоить. Наконец, ему не даже надо выезжать из города 2, чтобы добраться до 2, так что дополнительную взятку готовить не надо. Таким образом, всего он подготовит 4000 динаров.