2017年份表达式的结果：第四题

题目描述

针对单个二进制变量，规定了两种运算方式：

运算的优先级规则如下：

首先处理括号内部的内容，随后处理括号外部的部分。

在运算过程中，“×”的优先级高于“⊕”，即在解析表达式时，应先执行“×”运算，再进行“⊕”运算。例如，在计算表达式A⊕B × C时，应当先计算B × C的结果，并将该结果与A进行“⊕”运算。

现在给出一个未完成的表达式，例如_+(*)，请在横线处填入数字0或1，问有多少种填法可以让整个表达式的最终结果为0。

输入输出格式说明：

输入格式：
共2行。

第一行是一个整数L，表示给定表达式中除横线外所包含的运算符和括号的数量。

第二行是一个字符串，其中包含L个字符。这些字符仅包括’（’、’）’、’+’、’ ’这四种类型。其中,’（’和’）’分别代表左右括号；‘+’和‘ ’则对应前面定义的运算符“⊕”和“×”。该字符串按顺序描述了给定表达式中除变量以外的部分内容。

输出格式：
共1行。输出一个整数，表示所有可能的方案总数。注意：该数值可能非常大，请将其对10007取模后输出结果。

输入输出样例：

输入样例