{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e正如你可能知道的那样，安东去上学。安东学习的学科之一是括号学。在括号学课程中，学生通常学习由圆括号（字符 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(\u003c/span\u003e\" 和 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)\u003c/span\u003e\"（不带引号））组成的不同序列。\u003c/p\u003e\u003cp\u003e在上一堂课上，安东学习了关于正则简单括号序列（RSBS）的知识。如果满足以下条件，则长度为 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 的括号序列 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e 是 RSBS：\u003c/p\u003e\u003cul\u003e \u003cli\u003e 它不为空（即 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e ≠ 0\u003c/span\u003e）。 \u003c/li\u003e\u003cli\u003e 序列的长度是偶数。 \u003c/li\u003e\u003cli\u003e 序列的前 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/ed74413ac01097b3027d8ce92eaa57a7?v\u003d1715925154\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 个字符都等于 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(\u003c/span\u003e\"。 \u003c/li\u003e\u003cli\u003e 序列的最后 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/ed74413ac01097b3027d8ce92eaa57a7?v\u003d1715925154\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 个字符都等于 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)\u003c/span\u003e\"。 \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e例如，序列 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e((()))\u003c/span\u003e\" 是 RSBS，但序列 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e((())\u003c/span\u003e\" 和 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(()())\u003c/span\u003e\" 不是 RSBS。\u003c/p\u003e\u003cp\u003e安东的老师叶连娜·伊万诺夫娜给了他以下作业任务。给定一个括号序列 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e。找出其不同子序列的数量，使得它们是 RSBS。请注意，\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e 的子序列是可以通过删除其中一些元素而获得的字符串。如果删除的位置集不同，则认为两个子序列是不同的。\u003c/p\u003e\u003cp\u003e由于答案可能非常大，而安东的老师不喜欢大数字，她要求安东找出答案对 \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e 取模的结果。\u003c/p\u003e\u003cp\u003e安东思考了很长时间，但他仍然不知道如何解决这个问题。帮助安东解决这个问题，并编写一个程序来找到答案！\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的唯一一行包含一个字符串 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e\u0026nbsp;— 安东作业中给出的括号序列。该字符串仅包含字符 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(\u003c/span\u003e\" 和 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)\u003c/span\u003e\"（不带引号）。保证该字符串非空且长度不超过 \u003cspan class\u003d\"tex-span\"\u003e200 000\u003c/span\u003e。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个数字\u0026nbsp;— 问题的答案对 \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e 取模的结果。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e)(()()\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e()()()\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e)))\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中，可能的子序列如下：\u003c/p\u003e\u003cul\u003e \u003cli\u003e 如果我们删除位置 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e 处的字符（编号从一开始），我们将得到子序列 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(())\u003c/span\u003e\"。 \u003c/li\u003e\u003cli\u003e 如果我们删除位置 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e 处的字符，我们将得到子序列 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\"。 \u003c/li\u003e\u003cli\u003e 如果我们删除位置 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e 处的字符，我们将得到子序列 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\"。 \u003c/li\u003e\u003cli\u003e 如果我们删除位置 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e 处的字符，我们将得到子序列 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\"。 \u003c/li\u003e\u003cli\u003e 如果我们删除位置 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e 处的字符，我们将得到子序列 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\"。 \u003c/li\u003e\u003cli\u003e 如果我们删除位置 \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e 处的字符，我们将得到子序列 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\"。 \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e其余的子序列不是 RSBS。因此，我们得到了 \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e 个不同的 RSBS 子序列，因此答案是 \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e。\u003c/p\u003e"}}]}