Algorithm

C. Famil Door and Brackets
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/629/problem/C
input
standard input
output
standard output

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:

  1. the total number of opening brackets is equal to the total number of closing brackets;
  2. 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
Copy
4 1
(
output
Copy
4
input
Copy
4 4
(())
output
Copy
1
input
Copy
4 3
(((
output
Copy
0
Note

In the first sample there are four different valid pairs:

  1. p = "(", q = "))"
  2. p = "()", q = ")"
  3. p = "", q = "())"
  4. 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.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <string>
#include <memory.h>

using namespace std;

typedef long long ll;

int const MOD = 1e9 + 7;
int n, m, o, c;
string s;
int dp[2001][6001][2];

int rec(int index, int opens, bool cut) {
	if(opens < 0 || opens > 6000)
		return 0;

	if(index == n + 1)
		return opens == 0 && cut;

	int &ret = dp[index][opens][cut];
	if(ret != -1)
		return ret;
	ret = 0;

	ret = (ret + rec(index + 1, opens + 1, cut)) % MOD;
	ret = (ret + rec(index + 1, opens - 1, cut)) % MOD;
	if(!cut && opens >= c)
		ret = (ret + rec(index + 1, opens + o - c, true)) % MOD;

	return ret %= MOD;
}

int main() {
	cin >> n >> m >> s;

	if(n % 2 == 1) {
		cout << 0 << endl;
		return 0;
	}

	for(int i = 0; i < (int)s.length(); ++i)
		s[i] == '(' ? ++o : (o > 0 ? --o : ++c);

	if(n == m) {
		if(o == 0 && c == 0)
			cout << 1 << endl;
		else
			cout << 0 << endl;
		return 0;
	}

	n -= m;
	memset(dp, -1, sizeof dp);
	cout << rec(0, 0, false) << endl;

	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4 1
(

Output

x
–
+
cmd
4
Advertisements

Demonstration

Codeforces Solution-Famil Door and Brackets-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+