Задача G. Graphword ≡

Условие

Вася узнал, что его дедушка с очень давних пор любит разгадывать кроссворды.

На его юбилей Вася решил подарить ему игру, представляющую собой обобщенный вариант кроссворда — "графворд".

В качестве игрового поля в ней выступает некоторый неориентированный граф,
вершинам которого приписаны строчные буквы латинского алфавита.

В процессе разгадывания "графворда" игроку требуется составлять слова, перемещаясь по ребрам такого графа.

Согласно правилам игры каждое ребро можно посещать более одного раза.
Однако запрещается, чтобы текущее ребро совпадало с предыдущим.

При разработке уровней для своей игры Вася столкнулся с задачей определения числа всех возможных путей,
формирующих некоторое заданное слово в данном графе.

Так как полученное число может оказаться слишком большим,
в качестве ответа следует вывести остаток от его деления на 10⁹.

Формат входных данных

В начале входных данных находится число вершин N,
за которым следует набор символов, приписанных каждой из вершин.

Далее указано число ребер M, за которым следуют сами ребра,
каждое из которых задается индексами своих вершин: a_i, b_i.
Нумерация вершин начинается с нуля.

В окончании входных данных хранится строка W,
для которой нужно выполнить подсчет.

Формат выходных данных

Выходные данные должны содержать единственное число.

Ограничения

1 ≤ N ≤ 10⁴, 0 ≤ M ≤ 10⁴, a_i ≠ b_i, 1 ≤ |W| ≤ 10

Примеры тестов

6
a b c a b c

8
0 1
1 2
1 4
4 3
5 0
2 4
4 5
0 4

abba

4

6
a b c a b c

8
0 1
2 3
0 4
3 4
2 1
4 2
0 2
5 4

abc

5