F - Brackets I

Time limit: 1 s
Memory limit: 256 MiB
Languages: C, C++, Java, Python, ... (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.

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