J 编程语言由 Kenneth E. Iverson 和 Roger Hui 在 20 世纪 90 年代初开发，它是 Iverson 开发的 APL 语言与 John Backus 创建的 FP 和 FL 函数级语言的综合体。

APL 语言家族以其对向量和数组的高级运算支持而闻名，J 语言也不例外。例如，这些语言中的所有一元和二元数值运算默认都适用于不同维度的向量和数组。加法运算（‘+’）不仅可以像其他语言那样对标量进行加法，还可以对标量和向量（标量被加到向量的每个分量上）或向量和向量（向量按分量相加）进行加法。

J 语言的表达能力非常惊人（其语法也同样晦涩），但对于本题，我们只需要该语言的一小部分。我们考虑一个单一的表达式，其中可以使用一个向量变量 $X$，一个标量变量 $N$（向量 $X$ 的长度），以及以下运算：

• 我们可以对两个向量、向量和标量，或两个标量进行加法（‘+’）、减法（‘-’）或乘法（‘*’）。
• 我们可以对标量和向量（按分量）使用一元减法（‘-’）和一元平方运算（‘*:’）。
• 我们可以使用加法运算对向量进行折叠（‘+/’）——即计算向量的和（一元运算）。

运算从右向左求值，J 语言忽略自然的运算优先级。求值顺序可以通过括号改变。更准确地说，其语法由以下 BNF 指定：

$$\langle \text{expression} \rangle ::= \langle \text{term} \rangle \mid \langle \text{term} \rangle \text{ (‘+’ | ‘-’ | ‘*’) } \langle \text{expression} \rangle \mid \text{ (‘-’ | ‘*:’ | ‘+/’) } \langle \text{expression} \rangle$$ $$\langle \text{term} \rangle ::= \text{ ‘(’} \langle \text{expression} \rangle \text{‘)’ } \mid \text{ ‘X’ } \mid \text{ ‘N’ } \mid \langle \text{number} \rangle$$ $$\langle \text{number} \rangle ::= \text{ (‘0’ | ‘1’ | ... | ‘9’)}^+$$

为了对表达式语法施加进一步的限制，我们定义表达式的复杂度：

• 标量（数字、‘N’ 和折叠结果）的复杂度为零；
• ‘X’ 的复杂度为 1；
• 加法和减法的复杂度为其操作数复杂度的最大值；
• 乘法的复杂度为其操作数复杂度之和；
• 一元平方的复杂度为其操作数复杂度的两倍。

例如，表达式 “(3-+/::X)-X*:X” 的复杂度为 3，而其子表达式 “:*:X” 的复杂度为 4。

你的程序将获得一个标量值表达式和一个向量 $X$ 的值，并应计算该表达式的结果模 $10^9$。给定表达式中每个子表达式的复杂度不超过 10。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$) —— 向量 $X$ 的长度。 第二行包含 $N$ 个整数 —— 向量 $X$ 的分量 ($0 \le X_i < 10^9$)。 第三行包含要计算的表达式，是一个长度不超过 $10^5$ 个字符的非空字符串。表达式中的每个数字都小于 $10^9$。折叠运算从不应用于标量。

输出格式

输出一个整数 —— 表达式结果模 $10^9$。

样例

输入 1

5
1 2 3 4 5
+/*:X

输出 1

55

输入 2

5
1 2 3 4 5
N++/X-X+1

输出 2

0

输入 3

3
11 56 37
+/(3-+/*:*:X)-X**:X

输出 3

964602515

说明

第一个表达式计算向量 $X$ 在欧几里得度量下的平方长度。 第二个表达式的结果不依赖于 $X$，且始终等于零。 第三个表达式的实际结果为 $-35397485$。