Competitions

# Dynamic programming O(n^3)

# 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**.

Input example #1

????(?

Output example #1

2