{"raw_statement":[{"iden":"statement","content":"As 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 \"_(_\" and \"_)_\" (without quotes)).\n\nOn the last lesson Anton learned about the regular simple bracket sequences (RSBS). A bracket sequence _s_ of length _n_ is an RSBS if the following conditions are met:\n\n*   It is not empty (that is _n_ ≠ 0).\n*   The length of the sequence is even.\n*   First charactes of the sequence are equal to \"_(_\".\n*   Last charactes of the sequence are equal to \"_)_\".\n\nFor example, the sequence \"_((()))_\" is an RSBS but the sequences \"_((())_\" and \"_(()())_\" are not RSBS.\n\nElena Ivanovna, Anton's teacher, gave him the following task as a homework. Given a bracket sequence _s_. Find the number of its distinct subsequences such that they are RSBS. Note that a subsequence of _s_ is a string that can be obtained from _s_ by deleting some of its elements. Two subsequences are considered distinct if distinct sets of positions are deleted.\n\nBecause the answer can be very big and Anton's teacher doesn't like big numbers, she asks Anton to find the answer modulo 109 + 7.\n\nAnton thought of this task for a very long time, but he still doesn't know how to solve it. Help Anton to solve this task and write a program that finds the answer for it!"},{"iden":"input","content":"The only line of the input contains a string _s_ — the bracket sequence given in Anton's homework. The string consists only of characters \"_(_\" and \"_)_\" (without quotes). It's guaranteed that the string is not empty and its length doesn't exceed 200 000."},{"iden":"output","content":"Output one number — the answer for the task modulo 109 + 7."},{"iden":"examples","content":"Input\n\n)(()()\n\nOutput\n\n6\n\nInput\n\n()()()\n\nOutput\n\n7\n\nInput\n\n)))\n\nOutput\n\n0"},{"iden":"note","content":"In the first sample the following subsequences are possible:\n\n*   If we delete characters at the positions 1 and 5 (numbering starts with one), we will get the subsequence \"_(())_\".\n*   If we delete characters at the positions 1, 2, 3 and 4, we will get the subsequence \"_()_\".\n*   If we delete characters at the positions 1, 2, 4 and 5, we will get the subsequence \"_()_\".\n*   If we delete characters at the positions 1, 2, 5 and 6, we will get the subsequence \"_()_\".\n*   If we delete characters at the positions 1, 3, 4 and 5, we will get the subsequence \"_()_\".\n*   If we delete characters at the positions 1, 3, 5 and 6, we will get the subsequence \"_()_\".\n\nThe rest of the subsequnces are not RSBS. So we got 6 distinct subsequences that are RSBS, so the answer is 6."}],"translated_statement":[{"iden":"statement","content":"正如你所知，Anton 上学。Anton 学习的科目之一是括号学（Bracketology）。在括号学课上，学生们通常学习由圆括号（字符 \"_(_\" 和 \"_)_\"）组成的序列。\n\n在上一节课中，Anton 学习了正则简单括号序列（RSBS）。一个长度为 #cf_span[n] 的括号序列 #cf_span[s] 是 RSBS，当且仅当满足以下条件：\n\n例如，序列 \"_((()))_\" 是 RSBS，但序列 \"_((())_\" 和 \"_(()())_\" 不是 RSBS。\n\nAnton 的老师 Elena Ivanovna 给了他如下作业：给定一个括号序列 #cf_span[s]，求出其不同的子序列中，有多少个是 RSBS。注意，#cf_span[s] 的子序列是通过删除其中某些元素得到的字符串。如果删除的位置集合不同，则两个子序列被视为不同。\n\n由于答案可能非常大，而 Anton 的老师不喜欢大数，她要求 Anton 将答案对 #cf_span[109 + 7] 取模。\n\nAnton 思考了很长时间，但仍不知道如何解决。请帮助 Anton 解决这个问题，编写一个程序找出答案！\n\n输入仅包含一行，为一个字符串 #cf_span[s] —— Anton 作业中给出的括号序列。该字符串仅由字符 \"_(_\" 和 \"_)_\" 组成（不含引号）。保证字符串非空，且长度不超过 #cf_span[200 000]。\n\n请输出一个数 —— 该任务的答案对 #cf_span[109 + 7] 取模的结果。\n\n在第一个样例中，以下子序列是可能的：\n\n其余子序列都不是 RSBS。因此我们得到了 #cf_span[6] 个不同的 RSBS 子序列，答案为 #cf_span[6]。\n\n"},{"iden":"input","content":"输入仅包含一行，为一个字符串 #cf_span[s] —— Anton 作业中给出的括号序列。该字符串仅由字符 \"_(_\" 和 \"_)_\" 组成（不含引号）。保证字符串非空，且长度不超过 #cf_span[200 000]。"},{"iden":"output","content":"请输出一个数 —— 该任务的答案对 #cf_span[109 + 7] 取模的结果。"},{"iden":"examples","content":"输入\n)(()()\n输出\n6\n输入\n()()()\n输出\n7\n输入\n)))\n输出\n0"},{"iden":"note","content":"在第一个样例中，以下子序列是可能的：如果删除位置 #cf_span[1] 和 #cf_span[5] 上的字符（编号从 1 开始），我们将得到子序列 \"_(())_\"。如果删除位置 #cf_span[1]、#cf_span[2]、#cf_span[3] 和 #cf_span[4] 上的字符，我们将得到子序列 \"_()_\"。如果删除位置 #cf_span[1]、#cf_span[2]、#cf_span[4] 和 #cf_span[5] 上的字符，我们将得到子序列 \"_()_\"。如果删除位置 #cf_span[1]、#cf_span[2]、#cf_span[5] 和 #cf_span[6] 上的字符，我们将得到子序列 \"_()_\"。如果删除位置 #cf_span[1]、#cf_span[3]、#cf_span[4] 和 #cf_span[5] 上的字符，我们将得到子序列 \"_()_\"。如果删除位置 #cf_span[1]、#cf_span[3]、#cf_span[5] 和 #cf_span[6] 上的字符，我们将得到子序列 \"_()_\"。其余子序列都不是 RSBS。因此我们得到了 #cf_span[6] 个不同的 RSBS 子序列，答案为 #cf_span[6]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s $ be a string of length $ n $ over the alphabet $ \\{ (, ) \\} $.  \nA **regular simple bracket sequence (RSBS)** is a non-empty string of the form $ (^a )^a $ for some integer $ a \\geq 1 $, i.e., $ a $ opening brackets followed by $ a $ closing brackets.\n\nLet $ \\mathcal{S} $ be the set of all distinct subsequences of $ s $ that are RSBS.\n\n**Constraints**  \n- $ 1 \\leq n \\leq 200{,}000 $  \n- $ s \\in \\{ (, ) \\}^n $, non-empty  \n\n**Objective**  \nCompute $ |\\mathcal{S}| \\mod (10^9 + 7) $, where $ |\\mathcal{S}| $ is the number of distinct subsequences of $ s $ that form an RSBS.","simple_statement":null,"has_page_source":false}