\textit{The J programming language, developed in the early} \textit{1990s by Kenneth E. Iverson and Roger Hui, is} \textit{a synthesis of APL (also by Iverson) and the FP and FL} \textit{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 ('\textbf{+}') 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 \textbf{X}, one scalar variable \textbf{N} --- the length of the vector \textbf{X}, and the following operations: \begin{itemize} \item We can add ('\textbf{+}'), subtract ('\textbf{-}') or multiply ('\textbf{*}') two vectors, vector and scalar, or two scalars. \item We can use unary minus ('\textbf{-}') and unary squaring operations ('\textbf{*:}') for scalars and vectors (component-wise). \item We can \textit{fold} a vector with plus operation ('\textbf{+/}') --- that is, compute the sum of a vector (unary operation). \end{itemize} 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. \textbf{hexpressioni ::= htermi j htermi (‘+’ j ‘-’ j ‘*’) hexpressioni j (‘-’ j ‘*:’ j ‘+/’) hexpressioni} \textbf{htermi ::= ‘(’hexpressioni‘)’ j ‘X’ j ‘N’ j hnumberi} \textbf{hnumberi ::= (‘0’ j ‘1’ j . . . j ‘9’)+} To correctly impose one more limitation on expression syntax, let us define complexity of an expression: \begin{itemize} \item complexity of scalars (numbers, '\textbf{N}', and result of fold) is zero; \item complexity of '\textbf{X}' is one; \item complexity of addition and subtraction is the maximum of their operands’ complexities; \item complexity of multiplication is the sum of its operands’ complexities; \item complexity of unary squaring is twice the complexity of its operand. \end{itemize} For example, the complexity of expression "\textbf{(3-+/*:*:X)-X**:X}" is \textbf{3}, while the complexity of its subexpression "\textbf{*:*:X}" is \textbf{4}. Your program is given a scalar-valued expression and a value of the vector X, and it should compute the expression result modulo \textbf{10^9}. The complexity of each subexpression in the given expression does not exceed \textbf{10}. \InputFile The first line contains one integer number \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^5}) --- the length of the vector \textbf{X}. The second line contains \textbf{N} integers --- components of the vector \textbf{X} (\textbf{0} ≤ \textbf{X_i} < \textbf{10^9}). The third line contains the expression to be computed, a non-empty string of not more than \textbf{10^5} symbols. Each number in the expression is less than \textbf{10^9}. The fold is never applied to a scalar. \OutputFile Output a single integer number --- the expression result modulo \textbf{10^9}.