J
Язык программирования J, разработанный в начале 1990-х годов Кеннетом Е. Айверсоном и Роджером Хуи, является синтезом APL (также созданного Айверсоном) и языков уровня функций FP и FL, созданных Джоном Бэкусом.
Википедия. J (язык программирования)
Семейство языков APL известно своей поддержкой сложных операций с векторами и массивами, и J не является исключением. Например, все унарные и бинарные числовые операции в этих языках по умолчанию применимы к векторам и массивам различных размеров. Операция сложения ('+') может складывать не только скаляры, как в других языках, но и скаляры и векторы (скаляр добавляется к каждому компоненту вектора), или векторы и векторы (векторы складываются поэлементно).
Выразительная мощность J впечатляет (как и его загадочный синтаксис), но для этой задачи нам нужен лишь небольшой подмножество языка. Мы рассматриваем одно выражение, где мы можем использовать одну векторную переменную X, одну скалярную переменную N - длину вектора X, и следующие операции:
Мы можем складывать (+), вычитать (-) или умножать (*) два вектора, вектор и скаляр, или два скаляра.
Мы можем использовать унарные операции минус (-) и возведение в квадрат (*:) для скаляров и векторов (поэлементно).
Мы можем свернуть вектор с помощью операции сложения ('+/') - то есть вычислить сумму вектора (унарная операция).
Операции вычисляются справа налево, естественный приоритет операций в J игнорируется. Порядок вычисления может быть изменен с помощью скобок. Более точно синтаксис указан в следующей BNF.
<выражение> ::= <терм> | <терм> (‘ + ’ | ‘ - ’ | ‘ * ’) <выражение> | (‘-’ | ‘*:’ | ‘+/’) <выражение>
<терм> ::= ‘(’<выражение>‘)’ | ‘X’ | ‘N’ | <число>
<число> ::= (‘0’ | ‘1’ | . . . | ‘9’)+
Чтобы правильно наложить еще одно ограничение на синтаксис выражения, давайте определим сложность выражения:
сложность скаляров (чисел, N и результата свертки) равна нулю;
сложность X равна единице;
сложность сложения и вычитания равна максимуму из сложностей их операндов;
сложность умножения равна сумме сложностей его операндов;
сложность унарного возведения в квадрат равна удвоенной сложности его операнда.
Например, сложность выражения "(3-+/*:*:X)-X**:X" равна 3, в то время как сложность его подвыражения "*:*:X" равна 4.
Ваша программа получает скалярное выражение и значение вектора X, и должна вычислить результат выражения по модулю 10^9. Сложность каждого подвыражения в данном выражении не превышает 10.
Входные данные
Первая строка содержит одно целое число N (1 ≤ N ≤ 10^5) - длина вектора X.
Вторая строка содержит N целых чисел - компоненты вектора X (0 ≤ X[i] < 10^9).
Третья строка содержит выражение для вычисления, непустую строку длиной не более 10^5 символов. Каждое число в выражении меньше 10^9. Свертка никогда не применяется к скаляру.
Выходные данные
Выведите одно целое число - результат выражения по модулю 10^9.