Reina is interested in colourful trees. In particular, she currently has her eyes on a tree with nodes, each coloured either red or blue. By definition, this tree has edges, the th of which connecting nodes and . 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 .

#### Constraints

In all subtasks,

##### Subtask 1 [10%]

##### Subtask 2 [20%]

The degree of each node is at most .

##### Subtask 3 [30%]

##### Subtask 4 [40%]

No additional constraints.

#### Input Specification

The first line contains one separated integer, .

The next line contains a string with characters. The th character is `R`

if node is red and `B`

if it is blue.

lines follow, each one containing two space-separated integers, and , describing a bi-directional road connecting nodes and .

**Note: the nodes are -indexed.**

#### Output Specification

The number of subgraphs of the given tree that form trees where all its leaves are the same color modulo .

#### Sample Input

```
6
BBRRRB
5 4
1 6
2 1
5 2
1 3
```

#### Sample Output

`12`

#### Explanation for Sample Input

There are 12 subgraphs with same coloured leaves.

#### Sample Input 2

```
5
BBBRB
5 3
3 2
5 1
5 4
```

#### Sample Output 2

`11`

## Comments

I really don't understand sample 1, can anyone explain it please?

For sample 1, the vertices of the valid subgraphs are

(Red Leaves)

(Blue Leaves)

Thank you!