Möhtərizələr#4045
Gəlin mötərizələrin düzgün ardıcıllığını belə müəyyən edək:
() və [] mötərizələr düzgün ardıcıllıqlardır;
əgər A düzgün mötərizə ardıcıllığıdırsa, onda (A) və [A] da düzgün mötərizə ardıcıllıqlarıdır;
əgər A və B hər ikisi düzgün mötərizə ardıcıllıqlarıdırsa, onda onların birləşməsi AB də düzgün mötərizə ardıcıllığıdır;
Ən azı bir cüt kvadrat mötərizə: [ və uyğun ] olan düzgün mötərizə ardıcıllığında, hər bir kvadrat mötərizə (həm açılan, həm də bağlanan) açılan dairəvi mötərizə ilə əvəz edilmişdir, beləliklə qırıq mötərizə ardıcıllığı əldə edilmişdir.
Məsələn, (( və ((((())) hər ikisi qırıq mötərizə ardıcıllığıdır. Birinci ardıcıllıq düzgün mötərizə ardıcıllığından [] əldə edilir. İkinci ardıcıllıq yalnız aşağıdakı dörd düzgün mötərizə ardıcıllığından əldə edilə bilər: []((())), ([](())), (([]())) və ya ((([]))).
Sizin vəzifəniz verilmiş qırıq mötərizə ardıcıllığından hansı düzgün mötərizə ardıcıllığının əldə edilə biləcəyini hesablamaqdır.
Giriş faylının birinci sətri verilmiş qırıq mötərizə ardıcıllığının uzunluğu olan tək bir cüt ədəd N (2 ≤ N ≤ 30000) ehtiva edir. İkinci sətir N simvoldan '(' və ')' ibarətdir - verilmiş qırıq mötərizə ardıcıllığı.
Çıxış faylının tək sətri bir ədəd ehtiva etməlidir - verilmiş qırıq mötərizə ardıcıllığından əldə edilə biləcək düzgün mötərizə ardıcıllığının tələb olunan sayı. Düzgün mötərizə ardıcıllığının sayı böyük ola biləcəyi üçün cavabı 1000000009 modulu ilə çıxarmalısınız.
Nümunə 1