Problem K
Cobweb

You are given $n$ cards, the $i$-th of which has a character $c_ i$ written on it. You want to arrange some or all of these cards so that they form a sequence. However, you cannot arrange them arbitrarily, as you are also given $n - 1$ rules in the form of $(i, j)$, meaning you are allowed to put the $i$-th card and the $j$-th card next to each other. It is guaranteed that the given rules will allow you to make a sequence that starts with any card and ends with any card.

Each sequence $t$ you make represents a string $s_ t = c_{t_1} c_{t_2} \dots $. You are also given a string $s$ and your goal is to find the number of different sequences you can make out of the cards such that the strings they represent are lexicographically greater than or equal to the given string.

Two sequences $a$ and $b$ are considered different if they have different lengths or $a_ i \neq b_ i$ for some $i$ where $a_ i$ represents the i-th card of sequence $a$ and $b_ i$ represents the i-th card in sequence $b$. Sequences that represent the same string but are made from different cards are considered different.

String $a$ is lexicographically greater than or equal to string $b$ if either $b$ is a prefix of $a$ (possibly $b = a$) or there exists $i$ $(1 \leq i \leq \min (|a|, |b|))$ such that $b_ i < a_ i$ and for any $j$ $(1 \leq j < i)$, $a_ j = b_ j$. Here $|a|$ denotes the length of the string $a$.

For example, in the second sample case (pictured below), the given sequence is $ah$. In the given tree, any sequence starting with an $e$, $h$, and $f$ are going to be lexicographically greater than $ah$, which accounts for $15$ sequences. Furthermore, the sequences $a - h - e$ and $a - h - f$ are lexicographically greater than $ah$ and the string $a - h$ is lexicographically equal to $ah$, so we find a total of $18$ sequences that satisfy the given constraints.

Input

The first line contains two space-separated integers $n$ ($1 \leq n \leq 2 \cdot 10^5$) and $m$ ($1 \leq m \leq 100$), the number of cards and the length of $s$ respectively.

The second line is the string $c$ of $n$ lowercase latin letters, where $c_ i$ is written on the $i$-th card.

The third line is the string $s$ of length $m$.

Finally, $n - 1$ lines follow in the format of “i j”, each representing a rule $(i, j)$.

Output

Print the number of sequences that satisfy the given constraints.

5 3
stoaq
toe
1 4
2 4
2 3
4 5

0

5 2
feaha
ah
1 4
2 4
3 5
4 5

18