У Жени есть неориентированный граф состоящий из n вершин и m рёбер. Вершины пронумерованы от 1 до n, изначально в i-й вершине записано значение vi. Также у Жени есть последовательность вершин s1, s2, ..., sk. Вершины могут встречаться в последовательности произвольным образом, соседние два элемента последовательности не обязательно являются соседними вершинами в графе, более того, соседние два элемента могут соответствовать одной и той же вершине. Любая вершина графа может появляться в последовательности произвольное (в том числе нулевое) количество раз.
Начиная с секунды номер 0 Евгений повторяет следующие действия:
. Обозначим через 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, ...
Первые несколько шагов выглядят следующим образом:
, к счёту Евгения прибавляется 2.
, к счёту Евгения прибавляется
.
, а значение счёта увеличивается на 1.
, счёт увеличивается на 0. После первой итерации прохода по последовательности si счёт Евгения равен
.
Продолжая этот процесс бесконечно мы можем заметить, что предел последовательности счёта равен 9.