You are given a incompleted bracket sequence $S$ consists of 3 types of characters `(`, `)` and `?`. Count the number of way to replace `?` with either `(` or `)` to obtain a regular bracket sequence (RBS).
Definition of RBS:
- A string of length $0$ is an RBS.
- If $A$ is an RBS, then $(A)$ is also an RBS.
- If $A$ and $B$ are RBS, then $AB$ is also an RBS.
### Input
- The first line contains the string $S$.
### Output
- Print one integer, the number of ways modulo $10^9+7$.
### Constraints
- $1 \le |S| \le 1000$.
### Example
Input:
```
(???
```
Output:
```
2
```
#### Note: There are 2 RBSs `()()` and `(())`.
