题目描述

农夫约翰通常用圆形标记给他的奶牛打上烙印，但他的烙铁坏了，所以他必须满足于给每头奶牛打上括号形状的标记$\red{--（}$。他的农场有两种奶牛：荷斯坦奶牛和根西奶牛。他给他的每头奶牛都打上了烙印

括号形标记。根据奶牛所面对的方向，这可能看起来像左括号或右括号。

$\red{FJ}$的$\red{N}$头奶牛都排成一排，每头奶牛都面向任意方向，所以奶牛上的标记看起来就像一串长度为$\red{N}$的括号。看着这个阵容，$\red{FJ}$看到了一个非凡的模式：如果他从左到右扫视仅通过$\red{Holsteins（}$按照它们在序列中出现的顺序），这给出了平衡的括号串；此外，根西岛也是如此！要查看这是否真的是一个罕见的事件，请帮助 $\red{FJ }$计算他可以将品种分配给他的 $\red{N }$头奶牛的可能方式的数量，以便该属性成立。

有几种方法可以定义一串括号"平衡"的含义。也许最简单的定义是 $\red{(}$'$\red{s }$和 $\red{)}$'$\red{s }$的总数必须相同，并且对于字符串的任何前缀，$\red{(}$'$\red{s }$和 $\red{)}$'$\red{s }$的数量必须至少一样多。例如，以下字符串都是平衡的：

$\red{() (()) ()(()())}$

虽然这些不是：

$\red{)( ())( ((())))}$

给一个只有左右括号的字符串，然后用 $\red{H}$、$\red{G }$两种字符来标记这个序列，所有标记 $\red{H }$的括号可以组成一个正确的括号序列，所有 $\red{G }$标记的括号也组成一个正确的括号序列，然后 输出这种标记方案的总数 $\red{ \_ 2012 }$的值。

输入格式

第 $\red{1 }$行：一串长度为 $\red{N (1 <= N <= 1000) }$的括号。

输出格式

第 $\red{1 }$行：单个整数，指定 $\red{FJ }$可以将品种分配给奶牛的方式数量，以便荷斯坦奶牛形成括号的平衡子序列，对于根西奶牛也是如此。由于答案可能是一个非常大的数字，请打印除以 $\red{2012 }$后的余数（即打印数字$\red{mod 2012）}$。仅涉及一种品种类型的品种分配是有效的。

样例

输入样例

(())

输出样例

6

提示

以下品种分配有效：

$\red{（（））HHHH（（））}$$\red{GGGG（（））}$$\red{HGGH（（））}$$\red{GHHG（（））}$$\red{HGHG（（））}$$\red{GHGH}$