给定一个仅包含'('、')'和'?'三种字符构成的字符串，'?'字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列？ 提示：建议python考生使用pypy提交代码！

输入描述:

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

输出描述:

合法序列的数量。由于数量可能过大，请对取模。

备注: