牛牛学括号
题号：NC21579
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

牛牛最近在学习括号匹配问题

给你一个合法的括号序列，每次操作分两步，第一步删除第一个左括号，第二步删除某一个右括号，要保证删除之后的括号序列还是合法的,求将括号删到空为止一共有多少种不同的删除方法，两种方法不同当且仅当存在某一步右括号的删除位置不同，答案膜1e9+7

输入描述:

输入一个字符串s只包含左右括号, 2 ≤ |s| ≤ 2500

输出描述:

输出一个整数
示例1

输入

复制 
()()()()()

输出

复制 
1
示例2

输入

复制 
(((())))

输出

复制 
24
示例3

输入

复制 
((()))(()(()))((()))

输出

复制 
432

备注:

子任务一30分：n<=20

子任务二30分：n<=100

子任务三40分：n<=2500