CF1015F.Bracket Substring

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$).

给你一个括号序列 $s$（不一定是合法的）。括号序列是指仅由字符 '(' 和 ')' 组成的字符串。

合法括号序列（regular bracket sequence）是指：通过在原序列的字符之间插入字符 '1' 和 '+'，可将其转化为一个正确的算术表达式。例如，括号序列 "()()" 和 "(())" 是合法的（对应的表达式分别为 "(1)+(1)" 和 "((1+1)+1)"），而 ")("、"(" 和 ")" 则不是合法的。

你的任务是：计算长度为 $2n$ 的合法括号序列中，包含给定括号序列 $s$ 作为子串（即连续的字符序列）的个数，并对 $10^9+7$（即 $1000000007$）取模。

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$).

输入的第一行包含一个整数 $n$（$1 \le n \le 100$）—— 表示所生成的合法括号序列的半长（即生成的序列长度必须等于 $2n$）。

输入的第二行包含一个字符串 $s$（$1 \le |s| \le 200$）—— 字符串 $s$ 必须是每个所生成的合法括号序列的子串（其中 $|s|$ 表示字符串 $s$ 的长度）。

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$).

仅输出一个整数——包含给定括号序列 $s$ 作为子串的合法括号序列的数量。由于该数量可能非常大，请对 $10^9+7$（即 $1000000007$）取模后输出。

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.

第一个样例中满足上述条件的所有合法括号序列：

• "(((()))())";
• "((()()))()";
• "((()))()()";
• "(()(()))()";
• "()((()))()".

第二个样例中满足上述条件的所有合法括号序列：

• "((()))";
• "(()())";
• "(())()";
• "()(())".

第三个样例中，不存在长度为 $4$ 且包含子串 "(((" 的合法括号序列。