You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

In this question, we define a bracket string that meets the following requirements as a "legal bracket string":

1. () is a "legal bracket string".
2. If A is a "legal bracket string", then (A) is also a "legal bracket string".
3. If A and B are both "legal bracket strings", then AB is also a "legal bracket string".

The definition of substring and different substring in this question is as follows:

1. We use $S(l,r)$ ($1\le l \le r \le |S|$, which $|S|$ is the length of $S$) to represent a substring of $S$. It means a string consisting of any consecutive characters from $l$ to $r$ in $S$.
2. Two substrings of S are considered different if and only if their positions in S are different, (i.e. $l$ is different or $r$ is different).

Little Q has a rooted tree which rooted at node $1$ and the number of nodes is $n$. Except for node $1$, the parent node of node $u(2\le u\le n)$ is $f_u(1\le f_u < u)$.

Little Q finds that there is exactly one bracket on each node of this tree, which may be ( or ). He defines $s_i$ as a string composed of brackets on the simple path from the root node to the node $i$ and arranged in sequence according to the sequence of the nodes.

Obviously $s_i$ is a bracket string, but it may not be a "legal bracket string". So now Little Q wants to find out how many different substrings of $s_i$ are "legal bracket strings" for all $i(1\le i\le n)$.

Assuming that there are $k_i$ different substrings of $s_i$ as "legal bracket strings", you only need to tell Little Q the bitwise XOR of all $i\times k_i$, which is:

$$(1\times k_1)\operatorname{xor}(2\times k_2)\operatorname{xor}(3\times k_3)\operatorname{xor}\cdots\operatorname{xor}(n\times k_n)$$

Among them, $\text{xor}$ is bitwise XOR operation.

Input Format

The first line contains an integer $n$, which represents the number of nodes in the tree.

The second line contains an bracket string of length $n$, which the $i$-th bracket represents the bracket on the $i$-th node.

The third line contains $n-1$ integer. The $i$-th integer represents the father of $(i+1)$-th node $f_{i+1}$.

Output Format

Print one integer in a single line, which is the answer.

5
(()()
1 1 2 2

6

The shape of the tree is as follows:

• The brackets on the simple path from the root to node $1$ are arranged in order to form a string of (, and the number of substrings that are "legal bracket strings" is $0$.
• The brackets on the simple path from the root to node $2$ are arranged in order to form a string of ((, and the number of substrings that are "legal bracket strings" is $0$.
• The brackets on the simple path from the root to node $3$ are arranged in order to form a string of (), and the number of substrings that are "legal bracket strings" is $1$.
• The brackets on the simple path from the root to node $4$ are arranged in order to form a string of (((, and the number of substrings that are "legal bracket strings" is $0$.
• The brackets on the simple path from the root to node $5$ are arranged in order to form a string of ((), and the number of substrings that are "legal bracket strings" is $1$.

Sample 2

See attached files brackets2.in and brackets2.ans.

Sample 3

See attached files brackets3.in and brackets3.ans.

Constraints

#	$n\le$	Special Properties
$1\sim 2$	$8$	$f_i=i-1$
$3\sim4$	$200$
$5\sim 7$	$2\times 10^3$
$8\sim 10$		None
$11\sim 14$	$10^5$	$f_i=i-1$
$15\sim 16$		None
$17\sim 20$	$5\times 10^5$