J

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)

The APL family of languages is famous for its support of advanced operations on vectors and arrays, and J is no exception. All unary and binary numeric operations in these languages apply by default to vectors and arrays of different dimensions. Plus (+) adds two scalars, a scalar and a vector, or two vectors. Adding a scalar to a vector adds the scalar to every component, and adding two vectors adds them component by component.

The expressive power of J is amazing, and so is its cryptic syntax, but this problem needs only a small subset of the language. We consider a single expression built from one vector variable X, one scalar variable N (the length of X), and the following operations.

• We can add (+), subtract (-) or multiply (*) two vectors, a vector and a scalar, or two scalars.
• We can use unary minus (-) and unary squaring (*:) on scalars and on vectors, where a vector is handled component by component.
• We can fold a vector with the plus operation (+/), the unary operation that gives the sum of the vector.

J ignores the natural precedence of operations and evaluates right to left. Parentheses change the order of evaluation. The syntax is specified exactly by the following BNF.

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

One more limitation on the syntax needs the complexity of an expression, defined like this.

• The complexity of a scalar (a number, N, and the result of a fold) is zero.
• The complexity of X is one.
• The complexity of addition and of subtraction is the larger of the complexities of the two operands.
• The complexity of multiplication is the sum of the complexities of its operands.
• The complexity of unary squaring is twice the complexity of its operand.

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

You are given a scalar-valued expression and the value of the vector X. Compute the value of the expression modulo $10^9$. No subexpression of the given expression has complexity greater than 10.

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

The second line contains $N$ integers, the 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 at most $10^5$ symbols. Each number in the expression is less than $10^9$. The fold is never applied to a scalar.

Print one integer, the value of the expression modulo $10^9$. The printed remainder is always at least $0$ and less than $10^9$, so turn a negative value into its non-negative remainder before printing it.

+/*:X computes the squared length of the vector X in the Euclidean metric.

The value of N++/X-X+1 does not depend on X and is always zero.

For X equal to (11, 56, 37), the true value of +/(3-+/*:*:X)-X**:X is -35397485, and the printed answer is that value reduced modulo $10^9$.