Four-Paw Chase

Time limit: 2000 msMemory limit: 256 MB

Gats oversees $N$ rooms connected by $N-1$ bidirectional passages. The rooms are numbered $1,2,\ldots,N$ , and the passage network is connected and contains no cycles. Exactly one cat occupies each room, wearing a badge colored R, G, or B.

Let $\operatorname{dist}(x,y)$ be the number of passages on the unique route between rooms $x$ and $y$ .

An unordered set of three cats forms a four-paw chase team if all of the following conditions hold:

The team contains exactly one cat of each badge color.
None of the three cats' rooms lies on the unique route between the rooms of the other two cats.
If the red, green, and blue cats occupy rooms $r$ , $g$ , and $b$ , respectively, then

4 \mid \left(\operatorname{dist}(r,g)+\operatorname{dist}(g,b)+\operatorname{dist}(b,r)\right).

Count the number of four-paw chase teams.

Input

The first line contains an integer $N$ ( $3 \le N \le 2 \times 10^5$ ), the number of rooms.

The second line contains a string $C$ of length . For each , the character is one of , , or , representing the badge color of the cat in room .

Output

Print one integer: the number of unordered sets of three cats that form a four-paw chase team.

Samples

Sample 1

Input

5
RRGBB
1 2
1 3
1 4
4 5

Output

The only valid team occupies rooms $2$ , $3$ , and $5$ . Its three pairwise distances total $2+3+3=8$ , which is divisible by .

Four-Paw Chase

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2