|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #24Ended |
F - Brackets I
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
Alan adora jugar con brackets. Como todos sabemos una secuencia balaceada de brackets puede ser definida recursivamente de la siguiente manera:
• Una secuencia vacía de brackets es balanceada.
• Si S es una secuencia balanceada entonces, ( S ) es balanceada también.
• Si S y T son secuencias de brackets balanceadas entonces, ST es una secuencia balanceada también.
Alan tiene una secuencia de brackets(que no tiene por que estar balanceada) de longitud n. Sabemos que existen 2^n subsecuencias de esta secuencia. El quiere saber de estas cuantas estan balanceadas. Ayudenlo a calcular este numero, modulo 10^9 + 7.
• Una secuencia vacía de brackets es balanceada.
• Si S es una secuencia balanceada entonces, ( S ) es balanceada también.
• Si S y T son secuencias de brackets balanceadas entonces, ST es una secuencia balanceada también.
Alan tiene una secuencia de brackets(que no tiene por que estar balanceada) de longitud n. Sabemos que existen 2^n subsecuencias de esta secuencia. El quiere saber de estas cuantas estan balanceadas. Ayudenlo a calcular este numero, modulo 10^9 + 7.
Input
La primera línea de la entrada contiene la longitud
n
de la secuencia. La segunda línea contiene la secuencia de Alan formada solo por caracteres '(' y ')'.
• En el subproblema
I
se cumple (1 ≤
N
≤ 20);
• En el subproblema
II
se cumple (1 ≤
N
≤ 500);
Output
Imprima solamente el numero deseado en una linea.
Sample test(s)
Input
2
()
Output
1
Input
4
()()
Output
4