MOD = 10007 def xor_op(a0, a1, b0, b1): # a⊕b=0: (0,0)+(1,1) cnt0 = (a0 * b0 + a1 * b1) % MOD # a⊕b=1: (0,1)+(1,0) cnt1 = (a0 * b1 + a1 * b0) % MOD return cnt0, cnt1 def mul_op(a0, a1, b0, b1): # a×b=0: (0,0)+(0,1)+(1,0) cnt0 = (a0*b0 + a0*b1 + a1*b0) % MOD # a×b=1: (1,1) cnt1 = (a1 * b1) % MOD return cnt0, cnt1 def main(): import sys L = int(sys.stdin.readline()) if L == 0: print(1) return s = sys.stdin.readline().strip() # 第一步：解析表达式结构，统计变量个数和运算顺序 # 用两个栈：操作数栈（存储(0的数量, 1的数量)）、运算符栈 num_stack = [] op_stack = [] # 运算符优先级：* > +，括号最高 prio = {'(':0, '+':1, '*':2} # 标记是否需要生成新变量 need_var = True for c in s: if c == '(': op_stack.append(c) need_var = True elif c == ')': # 计算到左括号 while op_stack[-1] != '(': op = op_stack.pop() b0, b1 = num_stack.pop() a0, a1 = num_stack.pop() if op == '+': res0, res1 = xor_op(a0,a1,b0,b1) else: res0, res1 = mul_op(a0,a1,b0,b1) num_stack.append( (res0, res1) ) op_stack.pop() # 弹出左括号 need_var = False else: # + 或 * # 生成变量（因为运算符前面需要变量） if need_var: num_stack.append( (1,1) ) # 0和1各1种 need_var = False # 处理优先级 while op_stack and prio[op_stack[-1]] >= prio[c]: op = op_stack.pop() b0, b1 = num_stack.pop() a0, a1 = num_stack.pop() if op == '+': res0, res1 = xor_op(a0,a1,b0,b1) else: res0, res1 = mul_op(a0,a1,b0,b1) num_stack.append( (res0, res1) ) op_stack.append(c) need_var = True # 处理最后一个变量 if need_var: num_stack.append( (1,1) ) # 处理剩余运算符 while op_stack: op = op_stack.pop() b0, b1 = num_stack.pop() a0, a1 = num_stack.pop() if op == '+': res0, res1 = xor_op(a0,a1,b0,b1) else: res0, res1 = mul_op(a0,a1,b0,b1) num_stack.append( (res0, res1) ) # 输出结果为0的数量 print(num_stack[0][0] % MOD) if __name__ == '__main__': main()