{"problem":{"name":"F. Bracket Substring","description":{"content":"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1015F"},"statements":[{"statement_type":"Markdown","content":"You are given a bracket sequence $s$ (not necessarily a regular one). A bracket sequence is a string containing only characters '_(_' and '_)_'.\n\nA 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.\n\nYour 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$).\n\n## Input\n\nThe 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$).\n\nThe 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\n## Output\n\nPrint 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$).\n\n[samples]\n\n## Note\n\nAll regular bracket sequences satisfying the conditions above for the first example:\n\n*   \"_(((()))())_\";\n*   \"_((()()))()_\";\n*   \"_((()))()()_\";\n*   \"_(()(()))()_\";\n*   \"_()((()))()_\".\n\nAll regular bracket sequences satisfying the conditions above for the second example:\n\n*   \"_((()))_\";\n*   \"_(()())_\";\n*   \"_(())()_\";\n*   \"_()(())_\".\n\nAnd there is no regular bracket sequences of length $4$ containing \"_(((_\" as a substring in the third example.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定一个括号序列 $s$（不一定是合法的）。括号序列是仅包含字符 '_(_' 和 '_)_' 的字符串。\n\n一个合法括号序列是指可以通过在原序列的字符之间插入字符 '_1_' 和 '_+_' 而转换为正确算术表达式的括号序列。例如，括号序列 \"_()()_\" 和 \"_(())_\" 是合法的（对应表达式分别为 \"_(1)+(1)_\" 和 \"_((1+1)+1)_\"），而 \"_)(_\"、\"_(_\" 和 \"_)_\" 则不是。\n\n你的任务是计算长度为 $2 n$ 的合法括号序列中，包含给定括号序列 $s$ 作为子串（连续字符序列）的个数，结果对 $10^9 + 7$（$1000000007$）取模。\n\n输入的第一行包含一个整数 $n$（$1 lt.eq n lt.eq 100$）——表示最终合法括号序列的半长度（最终序列长度必须为 $2 n$）。\n\n第二行包含一个字符串 $s$（$1 lt.eq | s | lt.eq 200$）——该字符串必须作为子串出现在每个最终的合法括号序列中（$| s |$ 表示 $s$ 的长度）。\n\n仅输出一个整数——包含给定括号序列 $s$ 作为子串的合法括号序列的个数。由于这个数可能很大，请输出其对 $10^9 + 7$（$1000000007$）取模的结果。\n\n第一个示例中满足条件的所有合法括号序列：\n\n第二个示例中满足条件的所有合法括号序列：\n\n在第三个示例中，不存在长度为 $4$ 且包含 \"_(((_\" 作为子串的合法括号序列。\n\n## Input\n\n输入的第一行包含一个整数 $n$（$1 lt.eq n lt.eq 100$）——表示最终合法括号序列的半长度（最终序列长度必须为 $2 n$）。第二行包含一个字符串 $s$（$1 lt.eq | s | lt.eq 200$）——该字符串必须作为子串出现在每个最终的合法括号序列中（$| s |$ 表示 $s$ 的长度）。\n\n## Output\n\n仅输出一个整数——包含给定括号序列 $s$ 作为子串的合法括号序列的个数。由于这个数可能很大，请输出其对 $10^9 + 7$（$1000000007$）取模的结果。\n\n[samples]\n\n## Note\n\n第一个示例中满足条件的所有合法括号序列：\n\"_(((()))())_\"；\n\"_((()()))()_\"；\n\"_((()))()()_\"；\n\"_(()(()))()_\"；\n\"_()((()))()_\"。\n\n第二个示例中满足条件的所有合法括号序列：\n\"_((()))_\"；\n\"_(()())_\"；\n\"_(())()_\"；\n\"_()(())_\"。\n\n在第三个示例中，不存在长度为 $4$ 且包含 \"_(((_\" 作为子串的合法括号序列。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 100 $.  \nLet $ s \\in \\{ (, ) \\}^* $ be a given bracket string with $ 1 \\leq |s| \\leq 200 $.  \nLet $ \\mathcal{R}_{2n} $ denote the set of all regular bracket sequences of length $ 2n $.  \n\n**Constraints**  \n1. Each sequence in $ \\mathcal{R}_{2n} $ is a balanced string of $ n $ opening and $ n $ closing brackets, with every prefix having at least as many opening as closing brackets.  \n2. Each sequence must contain $ s $ as a contiguous substring.  \n\n**Objective**  \nCompute:  \n$$\n\\left| \\left\\{ r \\in \\mathcal{R}_{2n} \\mid s \\text{ is a substring of } r \\right\\} \\right| \\mod 10^9 + 7\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1015F","tags":["dp","strings"],"sample_group":[["5\n()))()","5"],["3\n(()","4"],["2\n(((","0"]],"created_at":"2026-03-03 11:00:39"}}