We have a rooted tree indexed in post-order (parent after all nodes in subtree), and want to find the group A_{n} (the group can contain the same element multiple times). A_{j} is defined as follows:

For a leaf with index j, A_{j} = [j]

For a node j with k children c_{1}, c_{2}, \cdots, c_{k}, let v_{j} = min(\cup_{i = 1}^{k} A_{c_{i}}). Now:

A_{j} = A_{c_{1}} + \cdots + A_{c_{k}} - [v_{j}] + [v_{j} \oplus j] + [j].

Where + makes a group that contains the elements of both groups, and - makes a group with a copy of every element from the second group removed from the first group. Note that a group can contain multiples of the same element. [3, 3] - [3] = [3].

Can you calculate the sum of all elements in A_{n} (that is, the root node)?

Input

Since the input is very large, it is given in a special form.

The tree is represented as a bracket sequence of length 2n. A node starts with a opening bracket, then children follow, and then the node is closed by a closing bracket. For example, a node with no children is (), and a node with two children, the second of which has one child, is (()(())). The child that appears first is first in the postorder traversal too.

The first line of input contains the integer n.

Then you are given \left\lceil \frac{2n}{64} \right\rceil unsigned 64-bit integers. The i'th bit (representing 2^{i}) of the j'th integer is 1 if the (64j + i)'th character in the bracket sequence is "(", and 0 if it's ")". After the end of the bracket sequence all bits are 0.

Output

Output the sum of all elements in A_{n}.

Constraints

• 1 \leq n \leq 10^{7}

Example

Input:

4
39

Output:

16

Explanation: