F. Bracket Substring

Codeforces

IDCF1015F

Time1000ms

Memory256MB

Difficulty—

dpstrings

English · Original

Chinese · Translation

Formal · Original

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$). [samples] ## 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.

你被给定一个括号序列 $s$（不一定是合法的）。括号序列是仅包含字符 '_(_' 和 '_)_' 的字符串。一个合法括号序列是指可以通过在原序列的字符之间插入字符 '_1_' 和 '_+_' 而转换为正确算术表达式的括号序列。例如，括号序列 "_()()_" 和 "_(())_" 是合法的（对应表达式分别为 "_(1)+(1)_" 和 "_((1+1)+1)_"），而 "_)(_"、"_(_" 和 "_)_" 则不是。你的任务是计算长度为 $2 n$ 的合法括号序列中，包含给定括号序列 $s$ 作为子串（连续字符序列）的个数，结果对 $10^9 + 7$（$1000000007$）取模。输入的第一行包含一个整数 $n$（$1 lt.eq n lt.eq 100$）——表示最终合法括号序列的半长度（最终序列长度必须为 $2 n$）。第二行包含一个字符串 $s$（$1 lt.eq | s | lt.eq 200$）——该字符串必须作为子串出现在每个最终的合法括号序列中（$| s |$ 表示 $s$ 的长度）。仅输出一个整数——包含给定括号序列 $s$ 作为子串的合法括号序列的个数。由于这个数可能很大，请输出其对 $10^9 + 7$（$1000000007$）取模的结果。第一个示例中满足条件的所有合法括号序列：第二个示例中满足条件的所有合法括号序列：在第三个示例中，不存在长度为 $4$ 且包含 "_(((_" 作为子串的合法括号序列。 ## Input 输入的第一行包含一个整数 $n$（$1 lt.eq n lt.eq 100$）——表示最终合法括号序列的半长度（最终序列长度必须为 $2 n$）。第二行包含一个字符串 $s$（$1 lt.eq | s | lt.eq 200$）——该字符串必须作为子串出现在每个最终的合法括号序列中（$| s |$ 表示 $s$ 的长度）。 ## Output 仅输出一个整数——包含给定括号序列 $s$ 作为子串的合法括号序列的个数。由于这个数可能很大，请输出其对 $10^9 + 7$（$1000000007$）取模的结果。 [samples] ## Note 第一个示例中满足条件的所有合法括号序列： "_(((()))())_"； "_((()()))()_"； "_((()))()()_"； "_(()(()))()_"； "_()((()))()_"。第二个示例中满足条件的所有合法括号序列： "_((()))_"； "_(()())_"； "_(())()_"； "_()(())_"。在第三个示例中，不存在长度为 $4$ 且包含 "_(((_" 作为子串的合法括号序列。

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 100 $. Let $ s \in \{ (, ) \}^* $ be a given bracket string with $ 1 \leq |s| \leq 200 $. Let $ \mathcal{R}_{2n} $ denote the set of all regular bracket sequences of length $ 2n $. **Constraints** 1. 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. 2. Each sequence must contain $ s $ as a contiguous substring. **Objective** Compute: $$ \left| \left\{ r \in \mathcal{R}_{2n} \mid s \text{ is a substring of } r \right\} \right| \mod 10^9 + 7 $$

Samples

Input #1

5
()))()

Output #1

Input #2

3
(()

Output #2

Input #3

2
(((

Output #3

API Response (JSON)

{
  "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 ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一个括号序列 $s$（不一定是合法的）。括号序列是仅包含字符 '_(_' 和 '_)_' 的字符串。\n\n一个合法括号序列是指可以通过在原序列的字符之间插入字符 '_1_' 和 '_+_' 而转换为正确算术表达式的括号序列。例如，括号序列 \"_()()_\" 和 \"_(())_\" 是合法的（对应表达式分别为 \"_(1)+(1)_\" 和 \"_((1+1)+1)_\"），而 \"_)(_\"、\"_(_\"...",
      "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 ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments