e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dynamic programming

Parentheses

The pattern is given. It consists of parentheses and question marks.

Find in how many ways one can replace the question marks with parentheses to obtain the correct bracket sequence.

Input

One line contains the pattern of length no more than 2000 symbols.

Output

Print the number of ways to get the correct bracket sequence by modulo 301907.

Time limit 1 second
Memory limit 128 MiB
Input example #1
????(?
Output example #1
2