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.