减法运算不满足结合律，例如 $(5-2)-1=2$，而 $5-(2-1)=4$，因此 $(5-2)-1 \ne 5-(2-1)$。这意味着形如 $5-2-1$ 的表达式的值取决于执行减法的顺序。在没有括号的情况下，我们假设运算是从左到右执行的，即表达式 $5-2-1$ 表示 $(5-2)-1$。给定一个形如

$$x_1 \pm x_2 \pm \ldots \pm x_n$$

的表达式，其中每个 $\pm$ 表示 $+$（加号）或 $-$（减号），且 $x_1, x_2, \ldots, x_n$ 表示（两两）不同的变量。我们希望在形如

$$x_1-x_2- \ldots - x_n$$

的表达式中插入括号，以获得与给定表达式等价的表达式。例如，如果我们想要获得与表达式

$$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))$$

注意：我们只对完全且正确加括号的表达式感兴趣。当一个表达式满足以下条件时，它是完全且正确加括号的：

• 它是一个单独的变量，
• 或者它是形如 $(w_1-w_2)$ 的表达式，其中 $w_1$ 和 $w_2$ 是完全且正确加括号的表达式。

通俗地说，我们对包含多余括号的表达式不感兴趣，例如：$()$，$ (x_i)$，$ ((\ldots ))$。此外，表达式 $x_1-(x_2-x_3)$ 因为缺少最外层的括号，所以不是完全加括号的。

任务

编写一个程序：

• 从标准输入读取给定表达式 $x_1 \pm x_2 \pm \ldots \pm x_n$ 的描述，
• 计算在表达式 $x_1-x_2-\ldots -x_n$ 中插入 $n-1$ 对括号，以明确减法执行顺序并同时获得与给定表达式等价的表达式的不同方式数量（模 $1\,000\,000\,000$），
• 将结果写入标准输出。

输入格式

标准输入的第一行包含一个整数 $n$，$2 \le n \le 5\,000$。这是给定表达式中变量的数量。在接下来的 $n-1$ 行中，每行包含一个字符 $+$ 或 $-$。第 $i$ 行表示给定表达式中 $x_i$ 和 $x_{i+1}$ 之间的符号。

输出格式

在标准输出的第一行，你的程序应输出一个整数，等于在表达式 $x_1-x_2- \ldots - x_n$ 中插入 $n-1$ 对括号，以明确减法执行顺序并同时获得与给定表达式等价的表达式的不同方式数量（模 $1\,000\,000\,000$）。

样例

输入格式 1

7
-
-
+
+
-
+

输出格式 1

3