[Poi2002]括号

时间限制：1s 空间限制：128MB

减法不满足结合率, 例如 (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₇)).

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

通常来说，我们对如下空括号形式不感兴趣: (), (x_i), ((...)). 而表达式 x₁-(x₂-x₃) 不是完整的，因为它缺少最外层的括号.

第一行有一个整数 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
-
-
+
+
-
+