Problem G. Graphword ≡

Statement

Vasya found out that his grandfather has been fond of solving crossword puzzles for a very long time.

On his anniversary, Vasya decided to present him a game, which is a generalized version of the crossword puzzle — "graphword".

A playing field in it is an undirected graph the vertices of which are assigned lowercase letters of the Latin alphabet.

In the process of solving the "graphword" the player needs to compose words by moving along the edges of such a graph.

According to the rules of the game, each edge can be visited more than once.
However, it is forbidden for the current edge to coincide with the previous one.

When developing levels for his game, Vasya was faced with the task of determining the number of all possible paths,
forming some given word in a given graph.

Since the resulting number may be too large, the answer should be the remainder of its division by 10⁹.

Input format

Input starts with the number of vertices N, followed by the set of characters assigned to each of the vertices.

Next, the number of edges M is given, followed by the edges themselves,
each of which is given by the indices of its vertices: a_i, b_i. Vertices are numbered starting from zero.

Input is finished with the string W, for which calculation should be done.

Output format

Output must contain a single integer.

Constraints

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

Sample tests

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