众所周知，delicious 老师非常喜欢树，同时有着高超的造题能力。因此，好吃老师打算用树来为你的 2023 最后涂上一抹绚丽的颜色 他温我哭 ~

题目描述

在一棵树 $T$ 上每个结点都标有一个字母，求有多少个有向简单路径，其上字母存在子序列构成字符串 $S$。

字符串的子序列指的是删除部分（可以没有）字符，保持剩下字符顺序得到的字符串。

输入格式

输入的第一行有两个正整数 $C,|T|$ 和字符串 $S$，分别表示测试点编号、树的结点数和需要找的子序列。样例中的 $C$ 表示满足对应测试点的性质。

第二行有一个长 $|T|$ 的字符串，其中第 $i$ 个字母表示点 $i$ 上的字母。

之后 $|T-1|$ 行，每行有两个正整数 $u,v$ 表示一条边连接的两个结点。

输出格式

输出一行一个自然数表示答案。

样例 #1

样例输入 #1

2 7 yuu
yuuyyuu
1 4
2 4
2 5
2 7
3 6
4 6

样例输出 #1

11

提示

【样例解释】

符合条件的路径有（按字典序排序）：

• $3\to 7$、$7\to 3$（uuyuu）
• $2\to 3$、$6\to 7$（uyuu）
• $4\to 3$、$4\to 7$、$5\to 7$（yuu）
• $5\to 6$（yuyu）
• $5\to 3$（yuyuu）
• $1\to 3$、$1\to 7$（yyuu）

一些不符合条件的路径包括 $7\to 6$（uuyu）。

【数据范围】

本题共 $20$ 个测试点，每个 $5$ 分。

特殊性质中，“一条链”表示第 $i$ 条边连接 $i$ 和 $i+1$；“是菊花图”表示对任意 $i<|T|$ 有边连接 $i$ 和 $|T|$。

对于全体数据，保证 $3\le |T|\le 10^5$，$2\le |S|\le 20$，字符串只有小写字母，所有边构成一棵树。