Mötrəklər
Gənc proqramçı Aqnesa informatika dərsində arifmetik ifadələr haqqında yeni məlumatlar öyrəndi. O, arifmetik ifadədən mötərizələrdən başqa hər şeyi sildikdə nə baş verəcəyini maraqlandı. Sevimli axtarış sistemində sorğu edərək öyrəndi ki, riyaziyyatçılar bəzi arifmetik ifadələrdə rast gəlinə biləcək mötərizə ardıcıllıqlarını düzgün mötərizə ardıcıllıqları adlandırırlar.
Məsələn, ()(()) ardıcıllığı düzgün mötərizə ardıcıllığıdır, çünki o, məsələn, (2+2):(3–(5–2)+4) ifadəsində rast gələ bilər, amma (() və ())( ardıcıllıqları belə deyil. Asanlıqla görmək olar ki, altı mötərizədən (hər tipdən üç mötərizə - açan və bağlayan) ibarət olan beş düzgün mötərizə ardıcıllığı mövcuddur: ((())), (()()), (())(), ()(()) və ()()().
Aqnesa düzgün mötərizə ardıcıllıqlarının ən sadə çevrilmələri ilə maraqlandı. Əvvəlcə Aqnesa ardıcıllığa mötərizələr əlavə etməklə məhdudlaşmağa qərar verdi. O, çox tez başa düşdü ki, bir mötərizə əlavə etdikdən sonra ardıcıllıq düzgün olmur, amma iki mötərizə əlavə etmək bəzən düzgünlük xüsusiyyətini saxlayır. Məsələn, ()() ardıcıllığına müxtəlif yerlərdə iki mötərizə əlavə edərək (()()), (())(), ()(()) və ()()() ardıcıllıqlarını əldə etmək olar. Asanlıqla görmək olar ki, düzgünlük xüsusiyyətini saxlayaraq iki mötərizə əlavə etməyin istənilən üsulunda yeni mötərizələrdən biri açan, digəri isə bağlayan olmalıdır.
Aqnesa verilmiş düzgün mötərizə ardıcıllığına iki mötərizə əlavə etməyin müxtəlif yollarının sayını hesablamaq istəyir ki, yenidən düzgün mötərizə ardıcıllığı əldə edilsin. Təəssüf ki, bəzi hallarda bu say çox böyük ola bilər. Aqnesa ardıcıllığın əldə edilməsi üsullarını əlavə edilmiş mötərizələrin əldə edilən ardıcıllıqda yerləşdiyi mövqelərə görə fərqləndirir. Məsələn, ən sadə () ardıcıllığına mötərizələr əlavə edərək yeddi fərqli düzgün mötərizə ardıcıllığı əldə etmək olar: ()(), (()), (()), (()), (()), ()(), ()(). Burada əlavə edilmiş mötərizələr qalın şriftlə göstərilmişdir.
Beləliklə, əgər əldə edilən ardıcıllıqda əlavə edilmiş açan mötərizə i mövqeyində, bağlayan mötərizə isə j mövqeyində yerləşirsə, (i_1, j_1) və (i_2, j_2) cütlərinə uyğun olan iki üsul fərqli hesab olunur, əgər i_1≠i_2 və ya j_1≠j_2.
Verilmiş düzgün mötərizə ardıcıllığına iki mötərizə əlavə etməyin yuxarıda təsvir edilən müxtəlif yollarının sayını müəyyən edən proqram yazmaq lazımdır.
Giriş verilənləri
Giriş faylı 2n simvoldan ibarət olan bir boş olmayan sətirdən ibarətdir: n açan və n bağlayan dairəvi mötərizələr. Bu sətirin düzgün mötərizə ardıcıllığı olduğu təmin edilir.
n (hər tipdən olan mötərizələrin sayı) 50000-dən çox deyil.
Çıxış verilənləri
Verilmiş ardıcıllığa iki mötərizə əlavə etməyin müxtəlif yollarının sayını çıxış faylına yazın ki, başqa düzgün mötərizə ardıcıllığı əldə edilsin.