括号序列 ### 题目描述 给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。 两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。 例如，对于括号序列 $((()$，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：$()()()$、$()(())$、$(())()$、$(()())$ 和 $((()))$​。 ### 输入描述 输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。 ### 输出描述 输出一个整数表示答案，答案可能很大，请输出答案除以 $1000000007$ (即 $10^9 + 7)$ 的余数。 ### 输入输出样例 #### 示例 1 >输入 ```txt ((() ``` >输出 ```txt 5 ``` ### 评测用例规模与约定 对于 $40\%$ 的评测用例，$|s| \leq 200$。 对于所有评测用例，$1 \leq |s| \leq 5000$。