UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2981. [Poi2002]括号

统计 下载数据

Description

减法不满足结合率, 例如 (5-2)-1=2, 但 5-(2-1)=4, 因此 (5-2)-1<>5-(2-1). 这意味着表达式5-2-1 依赖减法操作的顺序. 如果没有扩号,假定表达式计算从左到右, 即5-2-1 等于 (5-2)-1.我们给出表达式的形式如下:
x1 +/- x2 +/- ... +/- xn,
+/- 表示+ (加) - (减), x1,x2,...,xn 表示计算变量. 对下面的表达式
x1-x2-...-xn
我们想插入n-1对括号得到和表达式相同的结果.例如,我们想得到和下面表达式相等值的表达式
x1-x2-x3+x4+x5-x6+x7
可以对下面的表达式插入括号
x1-x2-x3-x4-x5-x6-x7
得到
(((x1-x2)-((x3-x4)-x5))-(x6-x7)).
注意: 我们只对完整而正确的表达式有兴趣,一个完整正确的表达式必须符合
  • 它可能是单个变量,
  • 可能形如(w1-w2), 而且 w1w2 都是完成而正确的表达式.
通常来说,我们对如下空括号形式不感兴趣: (), (xi), ((...)). 而表达式 x1-(x2-x3) 不是完整的,因为它缺少最外层的括号.

Input

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

Output

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

Sample Input

7
-
-
+
+
-
+



Sample Output

3

Hint

Source