H. Highway Hoax
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You think this is something? You think this is bad? This? This chicanery?
—Chuck McGill, Better Call Saul

Albuquerque is a large city. It has $$$n$$$ crossings and $$$n-1$$$ one-directional highways between them. It's guaranteed that if all highways were undirected, it would be possible to get from any crossing to any other by these highways. Additionally, every crossing has a label: S or F, indicating start and finish correspondingly.

Saul and Kim are going to do another chicanery. They can perform the following operation any number of times:

  • Choose any highway $$$(u, v)$$$ such that the following conditions hold:

    • This highway is directed from crossing $$$u$$$ to crossing $$$v$$$

    • Crossing $$$u$$$ has label S
    • Crossing $$$v$$$ has label F

  • Change the direction of the highway and swap labels on $$$u$$$ and $$$v$$$.

What is the total number of different configurations that Saul and Kim can achieve by applying this operation any number of times? As this number can be very large, output it modulo $$$998244353$$$.

Two configurations are called different if some crossing has different labels in them, or if some highway has different orientation in them.

Input

The first line of the input contains a single integer $$$n$$$ $$$(2 \leq n \leq 2\cdot 10^5)$$$  — the number of crossings in Albuquerque.

The second line of the input contains a string of length $$$n$$$, consisting of characters S and F. The $$$i$$$-th character of this string denotes the initial label of crossing $$$i$$$.

The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$u_i, v_i$$$ $$$(1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$)  — denoting a directed highway from crossing $$$u_i$$$ to crossing $$$v_i$$$. It's guaranteed that if all highways were undirected, it would be possible to get from any crossing to any other by these highways.

Output

Output a single integer  — the total number of different configurations that Saul and Kim can achieve by applying this operation any number of times, modulo $$$998244353$$$.

Examples
Input
5
SFSFS
2 1
2 3
4 3
4 5
Output
1
Input
4
SFFF
1 2
1 3
1 4
Output
4
Input
7
SSSSFFF
1 2
3 2
4 3
4 5
4 6
2 7
Output
13
Note

In the first sample, all highways are directed from crossings with F on them to crossings with S on them, so it's impossible to do any operations.

In the second sample, for each $$$v = 2, 3, 4$$$ it's possible to do an operation with nodes $$$1, v$$$. Resulting three configurations, together with the initial one, are the only possible configurations.