C. Бесконечная игра на графе
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Жени есть неориентированный граф состоящий из n вершин и m рёбер. Вершины пронумерованы от 1 до n, изначально в i-й вершине записано значение vi. Также у Жени есть последовательность вершин s1, s2, ..., sk. Вершины могут встречаться в последовательности произвольным образом, соседние два элемента последовательности не обязательно являются соседними вершинами в графе, более того, соседние два элемента могут соответствовать одной и той же вершине. Любая вершина графа может появляться в последовательности произвольное (в том числе нулевое) количество раз.

Начиная с секунды номер 0 Евгений повторяет следующие действия:

  1. На i-й секунде он выбирает вершину .
  2. К его счёту добавляется сумма текущих значений v по всем соседям вершины x.
  3. Значение vx делится пополам.

Обозначим через li счёт Евгения после i-й секунды. Если последовательность li не ограничена, то есть для любого x > 0 найдётся такое n, что ln > x, то выведите -1. В противном случае выведите предел этой последовательности в виде рациональной дроби , где P и Q являются взаимно простыми числами.

Гарантируется, что в рамках ограничений данной задачи значение Q никогда не делится на 109 + 7. Выведите P·Q - 1 по модулю 109 + 7, где Q - 1 означает обратное к Q по умножению по модулю 109 + 7.

Входные данные

В первой строке входных данных записаны три целых числа n, m и k (1 ≤ n, m, k ≤ 100 000).

Во второй строке записаны n целых чисел v1, v2, ..., vn (0 ≤ vi ≤ 109).

В третьей строке записаны k целых чисел s1, s2, ..., sk (1 ≤ si ≤ n).

В следующих m строках входных данных записаны пары чисел ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi), задающие рёбра неориентированного графа. Гарантируется, что любая пара вершин соединена не более, чем одним ребром.

Выходные данные

Выведите одно целое число. Если последовательность li не является ограниченной, то выведите -1, в противном случае выведите предел этой последовательности в виде P·Q - 1 по модулю 109 + 7.

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

В примере из условия Евгений будет выбирать последовательность 1, 2, 3, 4, 1, 2, 3, 4, ...

Первые несколько шагов выглядят следующим образом:

  1. Выбрать вершину 1. Её значение становится , к счёту Евгения прибавляется 2.
  2. Выбрать вершину 2. Её значение становится равным , к счёту Евгения прибавляется .
  3. Выбрать вершину 3. Её значение становится равным , а значение счёта увеличивается на 1.
  4. Выбрать вершину 4. Значение v4 становится равным , счёт увеличивается на 0.

После первой итерации прохода по последовательности si счёт Евгения равен .

Продолжая этот процесс бесконечно мы можем заметить, что предел последовательности счёта равен 9.