3420. 括号序列

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

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

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

输入格式

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

输出格式

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

数据范围

对于 $40\%$ 的评测用例,$|s| ≤ 200$。
对于所有评测用例,$1 ≤ |s| ≤ 5000$。

输入样例:

((()

输出样例:

5