题目描述

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

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

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

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

${() (()) ()(()())}$

虽然这些不是：

${)( ())( ((())))}$

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

输入格式

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

输出格式

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

样例

输入样例

(())

输出样例

6

提示

以下品种分配有效：

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