Expected Change

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/FEB20/hindi/EXPCH.pdf), [Bengali](http://www.codechef.com/download/translated/FEB20/bengali/EXPCH.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/FEB20/mandarin/EXPCH.pdf), [Russian](http://www.codechef.com/download/translated/FEB20/russian/EXPCH.pdf), and [Vietnamese](http://www.codechef.com/download/translated/FEB20/vietnamese/EXPCH.pdf) as well. Chef has a string $A$ with length $N$. It contains only characters '(', ')' and '*'. Chef wants to perform the following process:  Uniformly randomly choose a pair of integers $(l, r)$ such that $1 \le l \le r \le N$.  Consider the substring $S = [A_l, A_{l+1}, \ldots, A_r]$. Process the characters of this string from left to right.  Let's denote the current number of closing brackets in $S$ up to the currently processed character (inclusive) by $n_c$. Similarly, let's denote the number of opening brackets by $n_o$. Note that the string $S$ may change; $n_c$ and $n_o$ correspond to the current state of $S$, not its initial state.  Whenever $n_c$ becomes greater than $n_o$, the currently processed character must be ')'. Then, change it from ')' to '(' and continue processing the remaining characters of $S$. Chef would like to know the expected number of characters that he would change in this process. Can you help him? It can be proved that this expected value can be expressed as a fraction $P/Q$, where $P$ and $Q$ are nonnegative integers and $Q$ is coprime to $10^9+7$. You should find $P \cdot Q^{1}$ modulo $10^9+7$, where $Q^{1}$ denotes the multiplicative inverse of $Q$ modulo $10^9+7$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains a single string $A$ with length $N$. ### Output For each test case, print a single line containing one integer $P \cdot Q^{1}$ modulo $10^9+7$. ### Constraints  $1 \le T \le 10$  $1 \le N \le 10^7$  the sum of $N$ over all test cases does not exceed $10^7$ ### Subtasks **Subtask #1 (5 points):** $N \le 100$ **Subtask #2 (15 points):** $N \le 5,000$ **Subtask #3 (30 points):** $N \le 10^5$ **Subtask #4 (50 points):** original constraints ### Example Input ``` 1 5 ((()) ``` ### Example Output ``` 866666673 ```Author:  foyaz05 
Editorial  https://discuss.codechef.com/problems/EXPCH 
Tags  combinatorics, dynamicprogramming, feb20, foyaz05, medium, tmwilliamlin 
Date Added:  31122019 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 