问题描述

给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。

两个结果是本质不同的是指存在某个位置的一个结果是左括号，而另一个是右括号。

例如，对于括号序列$((()$，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：$()()()、()(())、(()())$和$((()))$。

输入格式

输入一行包含一个字符串$s$,表示给定的括号序列，序列中只有左括号和右括号。

输出格式

输出一个整数表示答案，答案可能很大，请输出答案除以$1000000007(即10^9+7)$的余数。

样例输入输出

((()

5

评测用例规模与规定

对于$40\%$的评测样例,$\mid s\mid \leqslant 200$。

对于$100\%$的评测样例，$1 \leqslant \mid s \mid \leqslant 5000$。

运行限制

• 最大运行时间：$5s$
• 最大运行内存：$512M$