题目描述

减法不满足结合率，例如 $(5-2)-1=2$，但 $5-(2-1)=4$，因此 $(5-2)-1 \neq 5-(2-1)$。这意味着表达式 $5-2-1$ 依赖减法操作的顺序。如果没有括号，假定表达式计算从左到右，即$5-2-1$ 等于 $(5-2)-1$。我们给出表达式的形式如下：

$+/-$ 表示 $+$ (加) $-$ (减)，$x_{1},x_{2},...,x_{n}$ 表示计算变量。对下面的表达式 $x_{1}-x_{2}- \cdots -x_{n}$ 我们想插入 $n-1$ 对括号得到和表达式相同的结果。例如，我们想得到和下面表达式相等值的表达式 $x_{1}-x_{2}-x_{3}+x_{4}+x_{5}-x_{6}+x_{7}$ 可以对下面的表达式插入括号 $x_{1}-x_{2}-x_{3}-x_{4}-x_{5}-x_{6}-x_{7}$ 得到 $(((x_{1}-x_{2})-((x_{3}-x_{4})-x_{5}))-(x_{6}-x_{7}))$。

注意: 我们只对完整而正确的表达式有兴趣，一个完整正确的表达式必须符合

1. 它可能是单个变量,
2. 可能形如 $(w_{1}-w_{2})$，而且 $w_{1}$ 和 $w_{2}$ 都是完整而正确的表达式。

通常来说，我们对如下空括号形式不感兴趣：$(), (x_{i}), ((...))$。而表达式 $x_{1}-(x_{2}-x_{3})$ 不是完整的，因为它缺少最外层的括号。

输入格式

第一行有一个整数 $n$，表示表达式变量的个数。在下面的 $n-1$ 行有一个字符 $+$ 或 $-$。第 $i$ 行出现的字符给出了$x_{i-1}$ 和 $x_{i}$ 之间的操作。

输出格式

对表达式 $x_{1}-x_{2}-...-x_{n}$ 添加 $n-1$ 对括号，使得它与给出的表达式等价，表示插入空格的不同方案数，答案不超过 $1\times 10^9$。

样例输入

7
-
-
+
+
-
+

样例输出

3

数据规模与约定

对于 $100\%$的数据，$2\leq n\leq 1\times 10^6$。