A boolean function is a function of the form f: B_n -> B, where B = {0, 1} and n is a non-negative integer called the arity of the function. Some Boolean functions are projections: p_n^k(x₁, ..., x_n) = x_k. And given an m-ary function f, and n-ary functions g₁, ..., g_m, we can construct another n-ary function: h(x₁, ..., x_n) = f(g1(x₁, ..., x_n), ..., gm(x₁, ..., x_n)), called their composition. A set of functions closed under composition and containing all projections is called a clone. One trivial clone is a set of all boolean functions. Some of the special clones are:

• Z is a set of 0-preserving functions: f(0, ..., 0) = 0;
• P is a set of 1-preserving functions: f(1, ..., 1) = 1;
• D is a set of self-dual functions: !f(x₁, ..., x_n) = f(!x₁, ..., !x_n);
• A is a set of affine functions: the functions satisfying that if f(a₁, ..., c, ..., a_n) = f(a₁, ..., d, ..., a_n) then f(b₁, ..., c, ..., b_n) = f(b₁, ..., d, ..., b_n), where c and d are at some position i. This should hold for every valid i, a₁, ..., a_n, b₁, ... b_n, c and d.

Now we are interested how many n-ary functions are there in some combinations of mentioned above sets. For example, for n = 2, there are exactly 8 functions in Z, 4 functions in the intersection of Z and P, 8 function in the complement of A and so on.

Input

The first line of the input file contains n - the arity of the boolean functions we are looking at. The second line contains the q - number of queries. Each of the next q lines will describe a query. The query is a set expression. The expression will contain the following characters: 'Z', 'P', 'D', 'A' denoting the sets, described above; 'v' - which is set union; '^' - which is set intersection; '!' which is complement; '\' which is set difference; and also '(' and ')' to define operations priority. Operations in brackets have higher priority. Otherwise the '!' operation has the higher priority and 'v', '^' and '\' are of the same priority. It is guaranteed that the expression will be correct. See samples for some examples of set expressions.

Constraints

1 <= n <= 100
1 <= q <= 100
The length of each expression won't exceed 100 characters.

Output

For each query in the input print how many n-ary function are in the set described by the according set expression modulo 1000003.

Example

Input:
2
6
Z
Z^P
!A
!(AvP)^D
AvZvP\A
!A^(Z\(Dv!P))

Output:
8
4
8
0
6
2