给你 $n$ 张卡片，其中第 $i$ 张卡片上写有一个字符 $c_i$。你想将其中部分或全部卡片排列成一个序列。然而，你不能任意排列它们，因为你还得到了 $n - 1$ 条形如 $(i, j)$ 的规则，表示你允许将第 $i$ 张卡片和第 $j$ 张卡片相邻放置。保证给定的规则允许你制作一个以任意卡片开始并以任意卡片结束的序列。

你制作的每个序列 $t$ 都代表一个字符串 $s_t = c_{t_1} c_{t_2} \dots$。同时还会给你一个字符串 $s$，你的目标是求出可以用这些卡片制作出多少个不同的序列，使得它们代表的字符串在字典序上大于或等于给定的字符串。

两个序列 $a$ 和 $b$ 被认为是不同的，如果它们的长度不同，或者对于某个 $i$，有 $a_i \neq b_i$，其中 $a_i$ 表示序列 $a$ 中的第 $i$ 张卡片，而 $b_i$ 表示序列 $b$ 中的第 $i$ 张卡片。代表相同字符串但由不同卡片构成的序列被认为是不同的。

字符串 $a$ 在字典序上大于或等于字符串 $b$，如果 $b$ 是 $a$ 的前缀（可能 $b = a$），或者存在 $i$ ($1 \le i \le \min(|a|, |b|)$) 使得 $b_i < a_i$，且对于任意 $j$ ($1 \le j < i$) 都有 $a_j = b_j$。这里 $|a|$ 表示字符串 $a$ 的长度。

例如，在第二个样例（如下图所示）中，给定的字符串是 $ah$。在给定的树中，任何以 $e$、$h$ 和 $f$ 开头的序列在字典序上都大于 $ah$，这贡献了 15 个序列。此外，序列 $a - h - e$ 和 $a - h - f$ 在字典序上大于 $ah$，而字符串 $a - h$ 在字典序上等于 $ah$，因此我们总共找到了 18 个满足给定约束的序列。

第二个样例的示意图

输入格式

第一行包含两个空格分隔的整数 $n$ ($1 \le n \le 2 \cdot 10^5$) 和 $m$ ($1 \le m \le 100$)，分别表示卡片的数量和 $s$ 的长度。

第二行是一个由 $n$ 个小写英文（拉丁）字母组成的字符串 $c$，其中 $c_i$ 写在第 $i$ 张卡片上。

第三行是长度为 $m$ 的字符串 $s$。

最后 $n - 1$ 行，每行格式为 i j，代表一条规则 $(i, j)$。

输出格式

输出满足给定约束的序列数量。

样例

输入格式 1

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

输出格式 1

0

输入格式 2

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

输出格式 2

18