J

J proqramlaşdırma dili 1990-cı illərin əvvəllərində Kenneth E. Iverson və Roger Hui tərəfindən inkişaf etdirilmişdir. Bu dil, APL (həmçinin Iverson tərəfindən yaradılmış) və John Backus tərəfindən yaradılan FP və FL funksional səviyyəli dillərin sintezidir.

APL dil ailəsi, vektorlar və massivlər üzərində inkişaf etmiş əməliyyatları dəstəkləməsi ilə tanınır və J də bu xüsusiyyəti ilə fərqlənir. Məsələn, bu dillərdəki bütün unar və binar ədədi əməliyyatlar müxtəlif ölçülü vektorlar və massivlərə tətbiq oluna bilər. Plus əməliyyatı ('+') digər dillərdə olduğu kimi yalnız skalyarları deyil, həm də skalyar və vektorları (skalyar vektorun hər bir komponentinə əlavə edilir) və ya vektorları və vektorları (vektorlar komponent üzrə əlavə edilir) əlavə edə bilər.

J-nin ifadə gücü təsir edicidir (eləcə də onun anlaşılmaz sintaksisi), lakin bu problem üçün bizə dilin yalnız kiçik bir alt hissəsi lazımdır. Biz bir ifadəni nəzərdən keçiririk, burada bir vektor dəyişəni X, bir skalyar dəyişəni N - vektorun uzunluğu X, və aşağıdakı əməliyyatlardan istifadə edə bilərik:

• Biz iki vektoru, vektor və skalyarı və ya iki skalyarı toplamaq (+), çıxmaq (-) və ya vurmaq (*) əməliyyatlarını edə bilərik.

• Biz unar mənfi (-) və unar kvadrat əməliyyatlarını (*:) skalyarlar və vektorlar üçün (komponent üzrə) istifadə edə bilərik.

• Biz vektoru plus əməliyyatı ilə qatlaya bilərik ('+/') - yəni, vektorun cəmini hesablaya bilərik (unar əməliyyat).

Əməliyyatlar sağdan sola doğru qiymətləndirilir, J-də əməliyyatların təbii üstünlüyü nəzərə alınmır. Qiymətləndirmə sırası mötərizələrlə dəyişdirilə bilər. Daha dəqiq sintaksis aşağıdakı BNF-də müəyyən edilir.

<expression> ::= <term> | <term> (‘ + ’ | ‘ - ’ | ‘ * ’) <expression> | (‘-’ | ‘*:’ | ‘+/’) <expression>

<term> ::= ‘(’<expression>‘)’ | ‘X’ | ‘N’ | <number>

<number> ::= (‘0’ | ‘1’ | . . . | ‘9’)+

İfadə sintaksisinə bir məhdudiyyət daha düzgün tətbiq etmək üçün ifadənin mürəkkəbliyini müəyyən edək:

• skalyarların (rəqəmlər, N və qatlama nəticəsi) mürəkkəbliyi sıfırdır;

• X-in mürəkkəbliyi birdir;

• toplama və çıxmanın mürəkkəbliyi operandlarının mürəkkəbliklərinin maksimumudur;

• vurmanın mürəkkəbliyi operandlarının mürəkkəbliklərinin cəmidir;

• unar kvadratın mürəkkəbliyi operandının mürəkkəbliyinin iki qatıdır.

Məsələn, "(3-+/*:*:X)-X**:X" ifadəsinin mürəkkəbliyi 3-dür, halbuki onun alt ifadəsi "*:*:X" mürəkkəbliyi 4-dür.

Proqramınıza skalyar dəyərli ifadə və vektor X-in dəyəri verilir və o, ifadənin nəticəsini 10^9 modulu ilə hesablamaq lazımdır. Verilən ifadədə hər bir alt ifadənin mürəkkəbliyi 10-u keçmir.

Giriş

Birinci sətir bir tam ədəd N (1 ≤ N ≤ 10^5) - vektorun X uzunluğunu ehtiva edir.

İkinci sətir N tam ədəd ehtiva edir - vektorun X komponentləri (0 ≤ X[i] < 10^9).

Üçüncü sətir hesablanacaq ifadəni ehtiva edir, 10^5 simvoldan çox olmayan boş olmayan bir sətir. İfadədəki hər bir rəqəm 10^9-dan kiçikdir. Qatlama heç vaxt skalyara tətbiq edilmir.

Çıxış

Tək bir tam ədəd çıxış edin - ifadənin 10^9 modulu ilə nəticəsi.