#include <iostream> #include <stack> #include <string> #include <utility> using namespace std; const int MOD = 10007; // 定义⊕运算（+）：计算两个子表达式组合后结果为0/1的数量 pair<int, int> xor_op(int a0, int a1, int b0, int b1) { // 结果为0：(0,0) + (1,1) int cnt0 = (1LL * a0 * b0 + 1LL * a1 * b1) % MOD; // 结果为1：(0,1) + (1,0) int cnt1 = (1LL * a0 * b1 + 1LL * a1 * b0) % MOD; return {cnt0, cnt1}; } // 定义×运算（*）：计算两个子表达式组合后结果为0/1的数量 pair<int, int> mul_op(int a0, int a1, int b0, int b1) { // 结果为0：(0,0) + (0,1) + (1,0) int cnt0 = (1LL * a0 * b0 + 1LL * a0 * b1 + 1LL * a1 * b0) % MOD; // 结果为1：(1,1) int cnt1 = (1LL * a1 * b1) % MOD; return {cnt0, cnt1}; } // 获取运算符优先级：* > + > ( int get_priority(char op) { if (op == '*') return 2; if (op == '+') return 1; return 0; // '(' 的优先级最低 } // 执行一次运算：弹出右操作数、运算符、左操作数，计算后压回操作数栈 void calc(stack<pair<int, int>>& num_stack, stack<char>& op_stack) { if (num_stack.size() < 2 || op_stack.empty()) return; auto b = num_stack.top(); num_stack.pop(); auto a = num_stack.top(); num_stack.pop(); char op = op_stack.top(); op_stack.pop(); pair<int, int> res; if (op == '+') { res = xor_op(a.first, a.second, b.first, b.second); } else { // '*' res = mul_op(a.first, a.second, b.first, b.second); } num_stack.push(res); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int L; string s; cin >> L >> s; // 空表达式（L=0）：只有1个变量，填0的情况1种 if (L == 0) { cout << 1 << endl; return 0; } stack<pair<int, int>> num_stack; // 存储(结果0的数量, 结果1的数量) stack<char> op_stack; bool need_var = true; // 标记是否需要生成新变量 for (char c : s) { if (c == '(') { op_stack.push(c); need_var = true; } else if (c == ')') { // 计算括号内的所有运算，直到遇到左括号 while (!op_stack.empty() && op_stack.top() != '(') { calc(num_stack, op_stack); } // 弹出左括号 if (!op_stack.empty()) { op_stack.pop(); } need_var = false; } else { // '+' 或 '*' // 运算符前需要生成变量 if (need_var) { // 单个变量：0和1各1种填法 num_stack.push({1, 1}); need_var = false; } // 处理优先级：栈顶运算符优先级 >= 当前运算符时先计算 while (!op_stack.empty() && op_stack.top() != '(' && get_priority(op_stack.top()) >= get_priority(c)) { calc(num_stack, op_stack); } op_stack.push(c); need_var = true; } } // 处理最后一个变量（表达式以变量结尾的情况） if (need_var) { num_stack.push({1, 1}); } // 处理栈中剩余的运算符 while (!op_stack.empty()) { calc(num_stack, op_stack); } // 输出结果为0的填法数（对10007取模） cout << num_stack.top().first % MOD << endl; return 0; }