Problem E
Hackenbush Purplehearts

Sample input 2

Hackenbush is a game played on edges of three colours which all connect to each other or the ground. The edges are all red, green or blue. The first player can hack red and green edges and the second blue and green edges. When a player hacks an edge it is deleted. Any edges that can’t reach the ground are discarded.

The value of a Hackenbush game with red and blue edges can be defined in a few steps. We say that a blue edge is $+1$ and a red edge is $-1$. We also regard any position where whoever plays first loses as having value $0$. By repeating, combining and comparing games we can figure when the value becomes $0$ to determine the value of a given game. Consider as an example the game with one blue edge attached to a single red edge which is attached to the ground. If we take two copies of this game and a single blue edge attached to the ground, we get a game with value $0$. Thus the value of the game we are considering is $-1/2$.

You are given a position of Hackenbush Purpleheart. This is a position in the game Hackenbush where all edges are red or blue and there are no cycles.

You need to determine the value of the game. It can be shown that this is always an integer fraction.

Input

The first line contains a single integer $0 \leq n \leq 10^5$, the number of edges. The next line contains $n$ integers $-1 \leq e_i \leq n$, $e_i \neq 0$. The number $e_i$ denotes which edge is directly below edge $i$ on the unique path to the ground. If $e_i = -1$ the edge touches the ground. The index $e_i$ will always be an an edge that has already appeared in the input, or be the ground. The last line contains a string of $n$ characters, each character being either B or R. If the $i$-th character is R then the $i$-th edge is red, otherwise it is blue. No edge is more than $10^3$ edges away from the ground.

Output

If the value of the game is $p/2^q$ print p/2q where $p/2^q$ is a fully reduced fraction. If the fraction is an integer, print just that integer without /20. The value of the game is always of this form.

12
-1 1 2 3 3 5 5 7 -1 -1 10 10
BRBBRBBRRBRR

5/2^6

39
-1 1 2 3 4 4 4 7 7 9 9 1 12 13 13 15 16 16 18 18 15 21 21 12 24 25 25 24 28 28 24 31 12 33 34 34 2 37 37
BRRRBBRRBBRRRBBRRBRRBBBRBRRBRRBRRBRRRBR

65/2^12