阿尔伯克基（Albuquerque）是一座大城市。它有 $n$ 个路口和 $n - 1$ 条单向公路。题目保证如果将所有公路视为无向边，那么从任意路口出发都可以到达其他任何路口。此外，每个路口都有一个标签：$\texttt{S}$ 或 $\texttt{F}$，分别代表起点和终点。

索尔（Saul）和金（Kim）打算再搞点花招。他们可以执行以下操作任意多次：

• 选择任意一条公路 $(u, v)$，需满足以下条件：
  • 该公路的方向是从路口 $u$ 指向路口 $v$
  • 路口 $u$ 的标签为 $\texttt{S}$
  • 路口 $v$ 的标签为 $\texttt{F}$
• 改变该公路的方向，并交换 $u$ 和 $v$ 的标签。

请问索尔和金通过执行该操作任意多次，总共能得到多少种不同的配置？由于这个数字可能非常大，请输出其对 $998244353$ 取模的结果。

如果两种配置中某个路口的标签不同，或者某条公路的方向不同，则称这两种配置是不同的。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)，表示阿尔伯克基的路口数量。

第二行包含一个长度为 $n$ 的字符串，由字符 $\texttt{S}$ 和 $\texttt{F}$ 组成。字符串的第 $i$ 个字符表示路口 $i$ 的初始标签。

接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示一条从路口 $u_i$ 指向路口 $v_i$ 的单向公路。题目保证如果将所有公路视为无向边，那么从任意路口出发都可以到达其他任何路口。

输出格式

输出一个整数，表示索尔和金通过执行该操作任意多次所能达到的不同配置的总数，对 $998244353$ 取模。

样例

样例输入 1

5
SFSFS
2 1
2 3
4 3
4 5

样例输出 1

1

样例输入 2

4
SFFF
1 2
1 3
1 4

样例输出 2

4

样例输入 3

7
SSSSFFF
1 2
3 2
4 3
4 5
4 6
2 7

样例输出 3

13

说明

在第一个样例中，所有公路的方向都是从标签为 $\texttt{F}$ 的路口指向标签为 $\texttt{S}$ 的路口，因此无法执行任何操作。

在第二个样例中，对于每个 $v = 2, 3, 4$，都可以对节点 $1$ 和 $v$ 执行一次操作。由此产生的三个配置，加上初始配置，就是所有可能的配置。