F. Bracket Substringtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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).InputThe 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).OutputPrint 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).ExamplesInput5()))()Output5Input3(()Output4Input2(((Output0NoteAll 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.
Input5()))()
Output5
['dp', 'strings', '*2300']