Parentheses
Very easy
Execution time limit is 1 second
Runtime memory usage limit is 128 megabytes
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.
Examples
Input #1
Answer #1
Submissions 1K
Acceptance rate 37%