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

F. Bracket Substring
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You 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.