Reina is interested in colourful trees. In particular, she currently has her eyes on a tree with ~N~ nodes, each coloured either red or blue. By definition, this tree has ~N-1~ edges, the ~i~th of which connecting nodes ~u_i~ and ~v_i~. Looking at this tree, Reina wonders, "how many connected vertex-induced subgraphs of this tree form trees where all its leaves are the same colour?" Being unable to solve this problem, she has come to you for help. Since the answer may be large, she would be satisfied knowing it modulo ~10^9+7~.
In all subtasks,
~1 \le N \le 300\,000~
~1 \le u_i,v_i \le N~
Subtask 1 [10%]
~N \le 20~
Subtask 2 [20%]
The degree of each node is at most ~2~.
Subtask 3 [30%]
~N \le 3000~
Subtask 4 [40%]
No additional constraints.
The first line contains one integer, ~N~.
The next line contains a string with ~N~ characters. The ~i~th character is
R if node ~i~ is red and
B if it is blue.
~N-1~ lines follow, each one containing two space-separated integers, ~u_i~ and ~v_i~, describing a bi-directional road connecting nodes ~u_i~ and ~v_i~.
Note: the nodes are ~1~-indexed.
The number of subgraphs of the given tree that form trees where all its leaves are the same colour modulo ~10^9+7~.
Sample Input 1
6 BBRRRB 5 4 1 6 2 1 5 2 1 3
Sample Output 1
Explanation for Sample Output 1
There are 12 subgraphs with same coloured leaves.
Sample Input 2
5 BBBRB 5 3 3 2 5 1 5 4
Sample Output 2