Shù Yìn

Zhège chángshù shì duì shù ma? - 霍里卡·马卡雷纳

Let a valid tree be a rooted tree with $N$ nodes distinctly labeled with integers from $1$ to $N$, with node $1$ as the root. Two valid trees are considered distinct if there exist two nodes $u$ and $v$ such that $v$ is a child of $u$ in one tree but not in the other.

We define the yìn of such a tree using the following function:

function DFS(v):
begin
    result = "("
    for each child u of v, in increasing order of label:
        result += DFS(u)
    result += ")"
    return result
end

The yìn of the tree is the string returned by DFS(1).

Task

Given a yìn, determine the number of distinct valid trees with $N$ nodes that produce this yìn, modulo $10^9 + 7$.

Input data

The first line contains a valid yìn of length $2 \cdot N$, consisting only of the characters $\text{(}$ and $\text{)}$.

Output data

Print a single integer: the number of distinct valid trees with $N$ nodes (where $2 \cdot N$ is the length of the given yìn) that produce this yìn, modulo $10^9 + 7$.

Constraints and clarifications

• $1 \leq N \leq 10^6$
• It is guaranteed that there exists at least one valid tree that produces this yìn.

Example 1

stdin

((())) 

stdout

2

Explanation

The $2$ valid labelings are shown below.

Example 2

stdin

(()(()))

stdout

3

Explanation

The $3$ valid labelings are shown below.