O Míope
Gustavo Gonçalves Gomes, carinhosamente apelidado de “GGG”, é um jovem estudante. Em sua mais recente aula do colégio, ele aprendeu sobre o conceito de expressões matemáticas.
Após uma rápida exposição teórica, o professor passou um desafio para os alunos: dizer para uma dada expressão se ela é válida. Infelizmente, por conta de sua miopia, GGG não conseguiu decifrar certos caracteres da expressão, particularmente quando se tratava de diferenciar ')’ de ‘(‘. Percebendo a situação, e querendo demonstrar seus conhecimentos de informática, você decide ajudá-lo, calculando quantas das 
expressões que poderíamos obter substituindo os caracteres desconhecidos (representados por ‘?’), por ‘)’ ou ‘(‘, constituem expressões válidas, onde 
é o número de caracteres desconhecidos na expressão.
Note que os termos numéricos foram removidos dessa expressão, uma vez que não são importantes para o cálculo da informação que se busca.
Uma expressão só é considerada válida se satisfaz uma das seguintes condições:
- Ela é uma expressão vazia (não contém nenhum caractere).
- Ela é formada por uma expressão válida envolvida por parênteses, ou seja, da forma
, em que 
é uma expressão válida. - Ela é formada pela concatenação de duas expressões válidas, ou seja, da forma
, em que e 
são expressões válidas.
Entrada
A entrada contém uma única linha, a expressão anotada por GGG, representada por uma string 
, formada unicamente pelos caracteres ‘(‘, ‘)’ e ‘?’.
Saída
Imprima um único inteiro, representando o número de expressões válidas que poderíamos obter substituindo os caracteres desconhecidos. Como esse número pode ser muito grande, imprima a resposta módulo 
.
Exemplo
| Entrada | Saída |
(???(? |
2 |
- Explicação para o exemplo: Pode-se formar "()()()" e "(())()", totalizando duas expressões válidas .