{"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\u003eAs you probably know, Anton goes to school. One of the school subjects that Anton studies is Bracketology. On the Bracketology lessons students usually learn different sequences that consist of round brackets (characters \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)\u003c/span\u003e\" (without quotes)).\u003c/p\u003e\u003cp\u003eOn the last lesson Anton learned about the regular simple bracket sequences (RSBS). A bracket sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e of length \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e is an RSBS if the following conditions are met:\u003c/p\u003e\u003cul\u003e \u003cli\u003e It is not empty (that is \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e ≠ 0\u003c/span\u003e). \u003c/li\u003e\u003cli\u003e The length of the sequence is even. \u003c/li\u003e\u003cli\u003e First \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/ed74413ac01097b3027d8ce92eaa57a7?v\u003d1725616889\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e charactes of the sequence are equal to \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(\u003c/span\u003e\". \u003c/li\u003e\u003cli\u003e Last \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/ed74413ac01097b3027d8ce92eaa57a7?v\u003d1725616889\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e charactes of the sequence are equal to \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)\u003c/span\u003e\". \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eFor example, the sequence \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e((()))\u003c/span\u003e\" is an RSBS but the sequences \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e((())\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(()())\u003c/span\u003e\" are not RSBS.\u003c/p\u003e\u003cp\u003eElena Ivanovna, Anton\u0027s teacher, gave him the following task as a homework. Given a bracket sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e. Find the number of its distinct subsequences such that they are RSBS. Note that a subsequence of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e is a string that can be obtained from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e by deleting some of its elements. Two subsequences are considered distinct if distinct sets of positions are deleted.\u003c/p\u003e\u003cp\u003eBecause the answer can be very big and Anton\u0027s teacher doesn\u0027t like big numbers, she asks Anton to find the answer modulo \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eAnton thought of this task for a very long time, but he still doesn\u0027t know how to solve it. Help Anton to solve this task and write a program that finds the answer for it!\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe only line of the input contains a string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e\u0026nbsp;— the bracket sequence given in Anton\u0027s homework. The string consists only of characters \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)\u003c/span\u003e\" (without quotes). It\u0027s guaranteed that the string is not empty and its length doesn\u0027t exceed \u003cspan class\u003d\"tex-span\"\u003e200 000\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one number\u0026nbsp;— the answer for the task modulo \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Examples","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\n"}},{"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\n"}},{"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\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample the following subsequences are possible:\u003c/p\u003e\u003cul\u003e \u003cli\u003e If we delete characters at the positions \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e (numbering starts with one), we will get the subsequence \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(())\u003c/span\u003e\". \u003c/li\u003e\u003cli\u003e If we delete characters at the positions \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 and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, we will get the subsequence \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\". \u003c/li\u003e\u003cli\u003e If we delete characters at the positions \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 and \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e, we will get the subsequence \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\". \u003c/li\u003e\u003cli\u003e If we delete characters at the positions \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 and \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e, we will get the subsequence \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\". \u003c/li\u003e\u003cli\u003e If we delete characters at the positions \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 and \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e, we will get the subsequence \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\". \u003c/li\u003e\u003cli\u003e If we delete characters at the positions \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 and \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e, we will get the subsequence \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\". \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe rest of the subsequnces are not RSBS. So we got \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e distinct subsequences that are RSBS, so the answer is \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e.\u003c/p\u003e"}}]}