A22497.平衡奶牛品种

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

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

FJ 的 N 头奶牛都站成一排，每头都面向任意方向，因此奶牛上的标记看起来像一串长度为 N 的括号。 这给出了一个平衡的括号字符串;而且，根西岛也是如此！要了解这是否真的是一个罕见的事件，请帮助 FJ 计算他可以为他的 N 头奶牛分配品种的可能方法的数量，以便该属性成立。
有几种方法可以定义一串括号“平衡”的含义。也许最简单的定义是，（'s 和 ）的总数必须相同，并且对于字符串的任何前缀，必须至少有与 ） 一样多的 （'s）。例如，以下字符串都是平衡的：

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

显然这些不是：

)( ())( ((())))
结果 mod 2012

• 第 1 行：长度为 N （1 <= N <= 1000） 的括号字符串。

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

以下品种分配有效：

(()) HHHH (()) GGGG (()) HGGH (()) GHHG (()) HGHG (()) GHGH