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 required answer.

Sample

Input
2
()
()()

Output:
2
3

Constraints

T < 10

0 < |S| <= 1000


Added by:Piyush Kumar
Date:2016-07-17
Time limit:0.100s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:Andrew Stankevich Contests

hide comments
2021-05-10 14:44:00 Rafail Loizou
Very nice problem. A generalization of the one below:
https://www.spoj.com/problems/DSUBSEQ/
I'm not spoiling the answer I merely suggest another similar problem for people to solve.
2016-11-06 20:23:43 Cz³owiek Z Br±zu
So, if we take this "( ( ) ) ( ) " for example, then all possible subsequences are:

" " "( )" "( ( ) )" "( ( ) ) ( )" "( ) ( )"
hence there are 5 of them, right?

Re: Correct.

Last edit: 2016-11-07 22:24:21
2016-10-20 14:38:38
Very Nice Problem. Good Work Piyush
2016-07-18 15:06:18 [Rampage] Blue.Mary
"subsequences" means continuous?

Re: No. Subsequence here is the standard definition of subsequence.

Last edit: 2016-07-18 15:23:41
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.