Description

happy 猫来到了一个城市，城市里有 $n$ 个景点，景点之间由 $n - 1$ 条道路相连。任意两个景点之间有且只有一条路径可以相互到达，每个景点都有一个小写英文字母作为地标。

happy 猫在到达一个景点时可以选择拍下地标留念（也可以不拍），它不会重复经过同一个景点。happy 猫可以选择从任意一个景点出发，它想知道会有多少种拍照方式满足：将拍下的照片上的地标字母按拍照的先后顺序连起来恰好是 $\texttt{oiiai}$。

两种拍照方式不同，当且仅当将拍照地点的编号按拍照顺序排序后有至少一处不同。

答案可能很大，请将答案对 $998244353$ 取模。

Format

Input

第一行一个正整数 $n$ $(1 \leqslant n \leqslant 10^5)$，表示城市的景点个数。

第二行一个长度为 $n$ 的仅包含小写字母的字符串，字符串中第 $i$ 个字母表示第 $i$ 个景点处的地标。

接下来 $n - 1$ 行，每行两个正整数 $u, v$ $(1 \leqslant u, v \leqslant n)$，表示景点 $u,v$ 之间有一条可直接相互到达的路径。

Output

一行一个整数，表示答案对 $998244353$ 取模的结果。

Samples

7
oiioiai
1 2
2 3
3 4
2 5
5 6
6 7

4

15
aiiiiiaooaaooii
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15

30

Notes

对于第一个样例：

图中共有 $4$ 种拍照方式可以组成 $\texttt{oiiai}$：

• $4\to 3 \to 2 \to 6 \to 7$
• $4\to 3 \to 5 \to 6 \to 7$
• $4\to 2 \to 5 \to 6 \to 7$
• $1\to 2 \to 5 \to 6 \to 7$

Limitation

1s, 1024KiB for each test case.