CODEFORCES 629-C

general
, ,
1

Can you please explain following question from Codeforces Contest 269 question “C” ?

here’s question.

OR

Famil Door and Brackets

As Famil Door’s birthday is coming, some of his friends (like Gabi) decided to buy a present for him. His friends are going to buy a string consisted of round brackets since Famil Door loves string of brackets of length n more than any other strings!

The sequence of round brackets is called valid if and only if:

the total number of opening brackets is equal to the total number of closing brackets;
for any prefix of the sequence, the number of opening brackets is greater or equal than the number of closing brackets.

Gabi bought a string s of length m (m ≤ n) and want to complete it to obtain a valid sequence of brackets of length n. He is going to pick some strings p and q consisting of round brackets and merge them in a string p + s + q, that is add the string p at the beginning of the string s and string q at the end of the string s.

Now he wonders, how many pairs of strings p and q exists, such that the string p + s + q is a valid sequence of round brackets. As this number may be pretty large, he wants to calculate it modulo 109 + 7.
Input

First line contains n and m (1 ≤ m ≤ n ≤ 100 000, n - m ≤ 2000) — the desired length of the string and the length of the string bought by Gabi, respectively.

The second line contains string s of length m consisting of characters ‘(’ and ‘)’ only.
Output

Print the number of pairs of string p and q such that p + s + q is a valid sequence of round brackets modulo 109 + 7.
Examples
Input

4 1
(

Output

4

Input

4 4
(())

Output

1

Input

4 3
(((

Output

0

Note

In the first sample there are four different valid pairs:

p = "(", q = "))"
p = "()", q = ")"
p = "", q = "())"
p = "", q = ")()"

In the second sample the only way to obtain a desired string is choose empty p and q.

In the third sample there is no way to get a valid sequence of brackets.

THANKS :slight_smile:

1 Like
2

You can go through the Editorial.

http://codeforces.com/blog/entry/43227

There is also a c++ solution. If you are still facing any problem, please let me know.

3

I couldn’t understand what is meant by following -

  1. Calculate dpi, j : How many sequences of brackets of length i has balance j and intermediate balance never goes below zero (They form a prefix of a valid sequence of brackets).
    What is ‘balance’ here ?
    Thnx.
4

If the number of opening brackets is equal to number of closing brackets, then that sequence is called a balanced sequence.