6981: BZOJ2981：[Poi2002]括号

减法不满足结合率, 例如 (5-2)-1=2, 但 5-(2-1)=4, 因此 (5-2)-1<>5-(2-1). 这意味着表达式5-2-1 依赖减法操作的顺序. 如果没有扩号，假定表达式计算从左到右, 即5-2-1 等于 (5-2)-1.我们给出表达式的形式如下： x₁ +/- x₂ +/- ... +/- x_n, +/- 表示+ (加) - (减), x₁,x₂,...,x_n 表示计算变量. 对下面的表达式 x₁-x₂-...-x_n 我们想插入n-1对括号得到和表达式相同的结果.例如，我们想得到和下面表达式相等值的表达式 x₁-x₂-x₃+x₄+x₅-x₆+x₇ 可以对下面的表达式插入括号 x₁-x₂-x₃-x₄-x₅-x₆-x₇ 得到 (((x₁-x₂)-((x₃-x₄)-x₅))-(x₆-x₇)). 注意: 我们只对完整而正确的表达式有兴趣，一个完整正确的表达式必须符合

• 它可能是单个变量,
• 可能形如(w₁-w₂), 而且 w₁ 和 w₂ 都是完成而正确的表达式.

输入格式

第一行有一个整数 n, 2<=n<=1 000 000. 表示表达式变量的个数.在下面的 n-1 行有一个字符+ 或 -. 第i行 出现的字符给出了x_i-1 和 x_i 之间的操作.

输出格式

对表达式x₁-x₂-...-x_n添加n-1对括号，使得它与给出的表达式等价。在naw.out 中写入一个整数，表示插入空格的不同方案数，答案不超过1 000 000 000。

样例输入

7
-
-
+
+
-
+


 

样例输出

3

提示

没有写明提示

题目来源

没有写明来源