Farmer John 通常给奶牛烙圆形标记，但烙铁坏了，只好给每头牛烙一个括号形标记——(。农场有 Holstein 和 Guernsey 两个品种，每头牛都烙了括号。随朝向不同，标记看起来可能是左括号或右括号。
FJ 的 $N$ 头奶牛排成一行，各自朝向任意方向，标记构成长度 $N$ 的括号串。他发现一个惊人规律：从左到右只看 Holstein，按出现顺序读到一个平衡括号串；Guernsey 也是如此！为了判断这是否真是罕见事件，请计算给 $N$ 头牛分配品种使此性质成立的方案数。
“平衡”有多种定义。最简单的也许是左括号和右括号总数相等，而且任意前缀中左括号不少于右括号。例如以下串都平衡：
() (()) ()(()())
而以下串不平衡：
)( ())( ((())))
输入格式
- 第 1 行：长度为 $N$ $(1 \le N \le 1000)$ 的括号串。
输出格式
- 第 1 行：一个整数，表示分配品种使 Holstein 和 Guernsey 各自形成平衡括号子序列的方案数。答案可能很大，输出除以 2012 的余数（即模 2012）。只使用一个品种的分配也是合法的。
样例
输入格式 1
(())
输出格式 1
6
说明
以下品种分配可行：
(()) HHHH
(()) GGGG
(()) HGGH
(()) GHHG
(()) HGHG
(()) GHGH
题目作者：Brian Dean，2012