J Expression Evaluation

The J programming language is known for its support for operations on vectors and arrays. In this problem you are given a single scalar‐valued expression written in a small subset of J. The expression may contain a vector variable X, a scalar variable N (which is the length of X), numeric literals and the following operations:

• Binary operations: addition (+), subtraction (-), and multiplication (×). These operations are defined to work on two scalars, a scalar and a vector (in which case the scalar is automatically broadcast to each component), or two vectors (applied component‐wise).
• Unary operations: unary minus (-), squaring (×:) which squares its operand component‐wise, and fold (+/) which sums up the elements of a vector.

All operators are evaluated right to left (i.e. they are right‐associative) and the usual natural precedence is ignored. Parentheses ( ) may be used to alter the evaluation order.

The grammar for the expressions is defined by the BNF below (note that any formulas must be written in LaTeX):

\(\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')^{+}\)

In addition, an expression has a complexity defined as follows:

• Complexity of scalars (numbers, N, and result of fold) is 0.
• Complexity of X is 1.
• 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.

Your program is given a scalar‐valued expression and a value for the vector X. It should compute the expression’s result modulo \(10^9\). It is guaranteed that the complexity of every subexpression does not exceed 10.

Note on evaluation order: Although programming languages often use left–to–right order, here all operators are evaluated from right to left. For example, the expression 5+X is parsed as 5 + X (with 5 computed after X). When a binary operator is encountered, first the right operand is evaluated, then the left operand is evaluated, and finally the operation is applied. This is especially important for non‐commutative operations like subtraction.

inputFormat

The input consists of three parts:

1. A line containing the J expression. The expression will contain only the tokens defined above (X, N, numbers, +, -, ×, ×:, +/, and parentheses). There are no spaces in the expression.
2. A line containing a single integer N (the length of vector X).
3. A line containing N space‐separated integers, which are the elements of vector X.

It is guaranteed that the expression is scalar–valued.

outputFormat

Output a single integer: the result of evaluating the expression modulo \(10^9\).

sample

+/X
5
1 2 3 4 5

15