Distinct valid bracket subsequences

A valid bracket string is defined recursively.

• The empty string "" is a valid bracket string.
• If $X$ and $Y$ are valid bracket strings, then $XY$ is a valid bracket string.
• If $X$ is a valid bracket string, then $(X)$ is a valid bracket string.
• Every valid bracket string can be built with the rules above.

"()", "()()()", "(()())" and "(((())))" are all valid bracket strings.

A string $T$ is a subsequence of a string $S$ when you can delete some characters of $S$ and obtain $T$. Deleting none of them or all of them is allowed. The remaining characters keep their original order. For example, "bdf" is a subsequence of "abcdefg".

You are given a string $S$ made only of '(' and ')'. Write a program that counts how many distinct valid bracket strings occur among the non-empty subsequences of $S$. Two subsequences that spell the same string count as one, even when they delete different positions.

The first line contains the string $S$. It consists only of '(' and ')', and its length is between $1$ and $100$.

Print the number of distinct valid bracket strings among the non-empty subsequences of $S$, modulo 1,000,000,007.