Description

Define two operations on $1$-bit binary variables:

$$\begin{array}{|c|c|} \hline \qquad\qquad\quad\textsf{Operator}\qquad\qquad\quad & \qquad\qquad\quad\textsf{Operation rule}\qquad\qquad\quad \\ \hline \oplus & \begin{aligned} 0 \oplus 0 &= 0 \\ 0 \oplus 1 &= 1 \\ 1 \oplus 0 &= 1 \\ 1 \oplus 1 &= 1 \\ \end{aligned} \\ \hline \times & \begin{aligned} 0 \times 0 &= 0 \\ 0 \times 1 &= 0 \\ 1 \times 0 &= 0 \\ 1 \times 1 &= 1 \\ \end{aligned} \\ \hline \end{array}$$

The precedence of operations is:

1. Evaluate inside parentheses first, then outside.

2. The "×" operation has higher precedence than "⊕", i.e., when evaluating an expression, evaluate "×" before "⊕". For example, when evaluating the expression $A \oplus B \times C$, compute $B \times C$ first, and then perform "⊕" with $A$ on the result.

Given an incomplete expression, for example $\_+(\_ * \_)$, fill each underscore with the digit $0$ or $1$. How many ways are there to make the value of the expression equal to $0$?

Input Format

There are $2$ lines.

The first line contains an integer $L$, the number of operators and parentheses in the given expression, excluding the underscores.

The second line contains a string of $L$ characters, consisting only of (, ), +, *. Here ( and ) are the left and right parentheses, and +, * represent the operators $\oplus$ and $\times$ defined above. This line lists, in order, the operators and parentheses in the given expression, excluding variables.

Output Format

Output one line containing a single integer, the number of ways. Note: This number can be very large, so output the result modulo $10007$.

4
+(*)

3

Hint

[Explanation of the sample input and output]

The given expression, after including the underscores, is: $\_+(\_ * \_)$.

If we fill the underscores with $(0,0,0)$, $(0,1,0)$, or $(0,0,1)$, the value of the expression is $0$, so there are $3$ valid fillings.

[Constraints]

For $20\%$ of the testdata, $0 \le L \le 10$.

For $50\%$ of the testdata, $0 \le L \le 1{,}000$.

For $70\%$ of the testdata, $0 \le L \le 10{,}000$.

For $100\%$ of the testdata, $0 \le L \le 100{,}000$.

For $50\%$ of the testdata, the input expression contains no parentheses.

Translated by ChatGPT 5