题目描述

The $J$ programming language, developed in the early $1990s$ by Kenneth $E$ . Iverson and Roger Hui, is a synthesis of APL (also by Iverson) and the FP and FL function-level languages created by John Backus.

Wikipedia. $J$ (programming language)

APL language family is famous for its support of advanced operations on vectors and arrays, and $J$ is not an exception. For example, all unary and binary numeric operations in these languages by default are applicable to vectors and arrays of different dimensions. Plus operation $(‘+')$ can add not only scalars, like in other languages, but also scalars and vectors (the scalar is added to each component of the vector), or vectors and vectors (the vectors are added component-wise).

The expressive power of $J$ is amazing (as well as its cryptic syntax), but for this problem we need just a small subset of the language. We consider a single expression, where we may use one vector variable $X$ , one scalar variable $N$ -- the length of the vector $X$ , and the following operations:

We can add $(‘+'),$ subtract $(‘-')$ or multiply $(‘ \times ')$ two vectors, vector and scalar, or two scalars.

We can use unary minus $(‘-')$ and unary squaring operations $(‘ \times :')$ for scalars and vectors $(component-wise).$

We can fold a vector with plus operation $(‘+/')$ -- that is, compute the sum of a vector (unary operation).

Operations are evaluated right-to-left, natural precedence of operations is ignored in $J$ . The order of evaluation can be altered by parentheses. More precisely the syntax is specified in the following BNF.

$〈expressio_n〉 ::= 〈ter_m〉 | 〈ter_m〉 (‘+' | ‘-' | ‘ \times ') 〈expressio_n〉 | (‘-' | ‘ \times :' | ‘+/') 〈expressio_n〉$

$〈ter_m〉 ::= ‘('〈expressio_n〉‘)' | ‘X' | ‘N' | 〈number〉$

$〈number〉 ::= (‘0' | ‘1' |$ . . . $| ‘9')^{+}$

To correctly impose one more limitation on expression syntax, let us define complexity of an expression:

complexity of scalars (numbers, $‘N',$ and result of fold) is zero;

complexity of $‘X'$ is one;

complexity of addition and subtraction is the maximum of their operands' complexities;

complexity of multiplication is the sum of its operands' complexities;

complexity of unary squaring is twice the complexity of its operand.

For example, the complexity of expression $`(3-+/ \times : \times :X)-X \times \times :X`$ is $3$ , while the complexity of its subexpression $` \times : \times :X`$ is $4$ .

Your program is given a scalar-valued expression and a value of the vector $X$ , and it should compute the expression result modulo $10^{9}.$ The complexity of each subexpression in the given expression does not exceed $10$ .

输入格式

The first line contains one integer number $N (1 \le N \le 10^{5})$ -- the length of the vector $X$ .

The second line contains $N$ integers -- components of the vector $X (0 \le X_{i} < 10^{9}).$

The third line contains the expression to be computed, a non-empty string of not more than $105$ symbols. Each number in the expression is less than $109$ . The fold is never applied to a scalar.

输出格式

Output a single integer number -- the expression result modulo $10^{9}.$

题目大意

本题中，J 语言为一个表达式，满足如下的 Backus-Naur 范式：

<expression> ::= <term> | <term> ('+' | '-' | '*') <expression> | ('-' | > '*:' | '+/') <expression>
<term> ::= '(' <expression> ')' | 'X' | 'N' | <number>
<number> ::= ('0' | '1' | ... | '9')+

对于一个双目运算符，当操作数为数值和向量时，它的效果是将数值和向量中的每一维分量分别做运算；当操作数为两个向量时，它的效果是将向量中的每一维分量对应做运算。特别地，在本题中，所有的向量均相同。

Backus-Naur 范式中出现的记号解释如下：

• 加法、减法、乘法运算 '+','-','*'
• 单目运算 '-','*:','+/'。-A 表示对 A 取负，*:A 表示对 A 求平方，+/ A 称为折叠，表示对向量 A 的所有分量求和。
• 括号 '(',')'。没有括号时，所有运算符优先级相同，括号可以改变运算顺序，效果同通常的括号。
• 数字。
• 字母 'N','X'。N 在处理时等价于一个事先被给定的数字，X 则等价于一个事先被给定的向量。
• 单元。表达式、数字和字母被统称为单元。
• 表达式。若干个单元用双目和单目运算符按照符合语法规则的方式连接起来，所得到的字符串称为一个表达式。表达式中不得包含上文中没有提到的其他字符。
• 注意：J 语言的表达式是右结合的，你可以理解为从右往左计算，但是对于不满足交换律的减法操作，我们规定 A-B 仍然表示用 A 减去 B 而不是 B 减去 A。对于一个数字，我们规定它仍然是从左往右读的。比如 123 应当理解为 100+20+3 而不是 300+20+1。

每个表达式被定义了一个复杂度，我们规定所有数值（标量）的复杂度为 0，X 的复杂度为 1，加法运算和减法运算 A+B,A-B 的复杂度为 A 和 B 复杂度的最大值。A*B 的复杂度为两者复杂度之和，单目取反运算不改变表达式的复杂度，平方运算将表达式的复杂度变成它的两倍，折叠运算将表达式的复杂度变成 0。

你首先需要读入 $N,X(N\le10^5)$，保证 N 等于 X 的长度。X 中所有分量全为不超过 $10^9$ 的正整数。然后一行读入一个表达式 expr，保证它的复杂度不超过 10，并且长度不超过 $10^5$ 个字符，且完全符合语法规则。你需要求出 expr 的值模 $10^9$ 的结果（保证值一定是个标量而不是向量）。

translated by @Starlight237

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

提示

Time limit: 2 s, Memory limit: 256 MB.