Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Bracket Substring

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a bracket sequence $$$s$$$ (not necessarily a regular one). A bracket sequence is a string containing only characters '(' and ')'.

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"), and ")(", "(" and ")" are not.

Your problem is to calculate the number of regular bracket sequences of length $$$2n$$$ containing the given bracket sequence $$$s$$$ as a substring (consecutive sequence of characters) modulo $$$10^9+7$$$ ($$$1000000007$$$).

Input

The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the half-length of the resulting regular bracket sequences (the resulting sequences must have length equal to $$$2n$$$).

The second line of the input contains one string $$$s$$$ ($$$1 \le |s| \le 200$$$) — the string $$$s$$$ that should be a substring in each of the resulting regular bracket sequences ($$$|s|$$$ is the length of $$$s$$$).

Output

Print only one integer — the number of regular bracket sequences containing the given bracket sequence $$$s$$$ as a substring. Since this number can be huge, print it modulo $$$10^9+7$$$ ($$$1000000007$$$).

Examples

Input

5

()))()

Output

5

Input

3

(()

Output

4

Input

2

(((

Output

0

Note

All regular bracket sequences satisfying the conditions above for the first example:

- "(((()))())";
- "((()()))()";
- "((()))()()";
- "(()(()))()";
- "()((()))()".

All regular bracket sequences satisfying the conditions above for the second example:

- "((()))";
- "(()())";
- "(())()";
- "()(())".

And there is no regular bracket sequences of length $$$4$$$ containing "(((" as a substring in the third example.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 11:50:38 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|