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.