SP27450 VECTAR14 - Changu with subsequences

Changu likes to play with string and subsequences. He has thought of a puzzle for you. Can you answer him? He gives you a sequence of '(' and ')' . Your task is to find out the number of its **different subsequences** that are regular bracket sequences. For example, the sequence “()()” has 3 such subsequences: “()()”, “()”, and “”. As the number can be large, you have to output answer modulus 1000000007. **Input:** The first line contains T, the number of test cases. T lines follow, each containing a sequence of '(' and ')'. ****Output:**** For each test case, print the requires answer. Sample Input: 2 () ()() **Sample Output:** 2 3 **Constraints:** **T

N/A

N/A