G. Non-random numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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 x1, x2, x3, ..., xn satisfies some equation

F(xi, xi - 1, ..., xi - k) = 1,
if this equation is true for any xi, xi - 1, ... xi - 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 ≤ 103).

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

  • the bit with the index xi - r (0 ≤ r ≤ 9, r < n) is denoted as r, that is, xi - 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 260.

Examples
Input
3
(0+2)|(0&2)
Output
6
Input
4
(0+2)|-(0&2)
Output
9
Note

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

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