Московские, осень' 13: Тур 08.11.13

Язык J известен удобством работы с векторами и массивами. Например, все унарные и бинарные операции по умолчанию применимы к векторам и массивам различных размерностей. Операция плюс (‘+’) применима не только к скалярам (как в других языках), но и скаляру и вектору (скаляр добавляется к каждой компоненте вектора) и вектору и вектору (вектора складываются покомпонентно)

Выразительность языка J превосходна, но нам в этой задаче будет нужно только небольшое подмножество этого языка. Мы будем рассматривать одно выражение, в котором будут использоваться одна переменная-вектор \(X\), одна переменная-скаляр \(N\) - длина вектора \(X\) и следующие операции:

• Мы можем складывать ('+'), вычитать ('-') или умножать ('*') два вектора, вектор и скаляр или два скаляра.
• Мы можем использовать унарный минус ('-') и операцию унарного возведения в квадрат ('*:') для скаляров и векторов.
• Мы можем свернуть вектор с помощью унарной операции ('+/'), вычисляющей сумму элементов вектора.

Операции вычисляются справа налево, естественный порядок операторов в J игнорируется. Порядок может быть задан с помощью скобок. Более формально, синтактис определяется с помощью следующей БНФ:

‹expression›::= ‹term›|‹term›('+'|'-'|'*')‹expression›|('-'|'*:'|'+/')‹expression›

‹term›::= '('‹expression›')' | 'X' | 'N' | ‹number›

‹number›::= ('0' | '1' | ... | '9')+

Для формального ограничения на синтаксис выражения, определим сложность выражения:

• Сложность скаляров (чисел, 'N', результатов сверки) равна нулю;
• Сложность 'X' равна единице;
• Сложность сложения и вычитания есть максимум из сложностей слагаемых;
• Сложность умножения есть сумма сложностей множителей;
• Сложность унарного возведения в квадрат равна удвоенной сложности операнда.

Например, сложность выражения "(3-+/*:*:X)-X**:X" равна 3, а сложность подвыражения *:*:X равна четырем.

Вам дано выражение, результатом которого является скаляр, и значение вектора \(X\). Вычислите значение выражения по модулю \(10^9\). Сложность всех подвыражений не превосходит \(10\).