Description

$J$ 编程语言由 Kenneth E. Iverson 和 Roger Hui 在 1990 年代早期开发，是 APL（也是由 Iverson 开发）与 John Backus 创建的 FP 和 FL 函数级语言的综合体。

Wikipedia. $J$ (编程语言)

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

$J$ 的表达能力令人惊叹（以及它的神秘语法），但对于这个问题，我们只需要语言的一个小子集。我们考虑一个单一表达式，其中可以使用一个向量变量 $X$，一个标量变量 $N$——向量 $X$ 的长度，以及以下操作：

我们可以对两个向量、向量和标量或两个标量进行加法（‘+’）、减法（‘-’）或乘法（‘\times’）运算。

我们可以对标量和向量（按分量）使用一元负号（‘-’）和一元平方运算（‘\times:’）。

我们可以使用加法折叠向量（‘+/’）——即计算向量的和（一元运算）。

运算从右到左进行评估，$J$ 中忽略运算的自然优先级。可以通过括号改变评估顺序。更准确地说，语法在以下 BNF 中指定。

$\langle expression \rangle ::= \langle term \rangle | \langle term \rangle (‘+’ | ‘-’ | ‘\times’) \langle expression \rangle | (‘-’ | ‘\times:’ | ‘+/’) \langle expression \rangle$

$\langle term \rangle ::= ‘(’\langle expression \rangle‘)’ | ‘X’ | ‘N’ | \langle number \rangle$

$\langle number \rangle ::= (‘0’ | ‘1’ | \ldots | ‘9’)^{+}$

为了正确施加对表达式语法的一个限制，让我们定义表达式的复杂度：

标量（数字，‘N’，以及折叠的结果）的复杂度为零；

‘X’ 的复杂度为一；

加法和减法的复杂度是其操作数复杂度的最大值；

乘法的复杂度是其操作数复杂度的和；

一元平方的复杂度是其操作数复杂度的两倍。

例如，表达式 (3-+/ \times: \times:X)-X \times \times:X 的复杂度是 3，而其子表达式 \times: \times:X 的复杂度是 4。

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

Input Format

第一行包含一个整数 $N (1 \le N \le 10^{5})$——向量 $X$ 的长度。

第二行包含 $N$ 个整数——向量 $X$ 的分量 $(0 \le X_{i} < 10^{9})$。

第三行包含要计算的表达式，一个不超过 105 个符号的非空字符串。表达式中的每个数字都小于 109。折叠从不应用于标量。

Output Format

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

5
1 2 3 4 5
+/*:X

55

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

0

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

964602515

Hint

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。