407411: GYM102785 G Non-random numbers

G. Non-random numberstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

For generating pseudo-random numbers, various methods are used. One of such methods is the use of Boolean recurrent expressions. In such a case, the pseudo-random number is represented as a bit sequence, such that each next bit is calculated from the previous ones using a certain formula. However, such a task actually determines the sequence of its first members.

An alternative is the use of Boolean equations. We will say that the bit sequence x₁, x₂, x₃, ..., x_n satisfies some equation

F(x_i, x_i - 1, ..., x_i - k) = 1, if this equation is true for any x_i, x_i - 1, ... x_i - k, for i > k. Write a program that, using a given equation, will find the number of sequences of length n that satisfy this equation.Input

The first line of the input file contains an integer n (2 ≤ n ≤ 10³).

The second line contains the left side of the equation, encoded in the following way:

• the bit with the index x_i - r (0 ≤ r ≤ 9, r < n) is denoted as r, that is, x_i - 5 will be denoted as 5.
• operation «and» (conjunction) is denoted as «&»
• the operation «or» (disjunction) is denoted as «|»
• the operation «exclusive or» (addition on module 2) is denoted as «+»
• the operation «not» (negation) is denoted as «-»
• brackets are allowed in the equation, operations in brackets are executed earlier than others
• binary operations that are not in brackets are considered peer-to-peer and are performed strictly from left to right
• spaces inside the relationship are not allowed

The length of left side of the equation is not longer 1000 characters.

Output

The output file contains a single number — the number of bit sequences of length n that satisfy the equation. The number should be modulo 2⁶⁰.

ExamplesInput

3
(0+2)|(0&2)

Output

6

Input

4
(0+2)|-(0&2)

Output

9

Note

The first example encodes the equation (x_i + x_i - 2)|(x_i&x_i - 2) = 1, which satisfies the following sequence: 001, 011, 100, 101, 110, 111.

The second example encodes the equation (x_i + x_i - 2)|( - (x_i&x_i - 2)) = 1, which is satisfied by the sequence: 0000, 0001, 0010, 0011, 0100, 0110, 1000, 1001, 1100.