题目思路

经典的合法括号统计模型。观察到题目数据只有$2000$ , 那么考虑动态规划:

$dp_{i,j}$ 代表填完前i个数，并且左括号比右括号多$j$个的方案数。最后的答案是$dp_{n,0}$

为什么要这么定义:一个合法括号序列，他的充分必要条件是:每个前缀的左括号个数都不少于右括号个数，且整体的左括号个数 = 右括号个数

转移就很简单了:

题目内容

有一个叫小红的程序员，他正在为他的新项目编写代码。这个项目需要验证一个字符串是否为合法的括号序列。

小红正在编写一个函数来实现这个功能。但是他遇到了一个问题：字符串中有些字符是问号 ? ，可以代替左括号 ( 或者右括号 ) 。他不知道该如何处理这些问号。

于是他决定询问你，给定的字符串可以代表多少种不同的合法括号序列？

输入描述

一个仅包含( 、) 和 ? 的字符串，长度不超过 $2000$ 。

输出描述

合法序列的数量。由于数量可能过大，请对 $10^9 + 7$ 取模。

样例

输入

(??(??

输出

2