P1310 [NOIP 2011 Junior] The Value of the Expression

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$?

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 one line containing a single integer, the number of ways. Note: This number can be very large, so output the result modulo $10007$.

[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