农夫约翰通常会给他的奶牛打上圆形标记，但他的烙铁坏了，所以他必须为每个奶牛打上带有圆括号形状的标记-（。他的农场有两种奶牛：荷斯坦（Holsteins）和根西岛（Guernseys）。

圆括号形的标记。根据母牛所面对的方向，这看起来像是左括号还是右括号。

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

有几种方法可以定义使括号字符串“平衡”的含义。也许最简单的定义是必须有相同的总数（'s和），并且对于字符串的任何前缀，必须至少有（'s个）与's'一样多。例如，以下字符串都是平衡的：

() (()) ()(()())

这些不是：

)( ())( ((())))

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

输入格式 *第1行：一串长度为N（1 <= N <= 1000）的括号。

输出格式 *第1行：单个整数，指定FJ可以给母牛分配品种的方式的数量，以使荷斯坦犬形成一个括号内的平衡子序列，而对于根西岛来说也是如此。由于答案可能是非常大的数字，因此请在除以2012时打印该数字的其余部分（即，打印数字mod 2012）。仅涉及一种品种类型的品种分配有效。