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:
Choose any road such that the following conditions hold:
This road is directed from crossing to crossing
Crossing has label S
Crossing has label F
Change the direction of the road and swap labels on and .
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.
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 a single integer — the total number of different configurations that Saul and Kim can achieve by applying this operation any number of times, modulo .
Example
Example 1
Example 2
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.