Albuquerque's Avenues#12921

Albuquerque's Avenues

3 seconds
256 megabytes
Very hard

Albuquerque is a large city. It has crossings and n-1 one-directional roads between them. It's guaranteed that if all roads were undirected, it would be possible to get from any crossing to any other by these roads. 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:

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 .

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

Input

The first line of the input contains a single integer (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 , consisting of characters S and F. The -th character of this string denotes the initial label of crossing .

The -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 road from crossing u_i to crossing v_i. It's guaranteed that if all roads were undirected, it would be possible to get from any crossing to any other by these roads.

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 .

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first sample, all roads 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 . Resulting three configurations, together with the initial one, are the only possible configurations.