A22497.平衡奶牛品种

普及+/提高

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

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

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

显然这些不是:

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

输入格式

  • 第 1 行:长度为 N (1 <= N <= 1000) 的括号字符串。

输出格式

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

输入输出样例

  • 输入#1

    (()) 
    

    输出#1

    6 
    

说明/提示

以下品种分配有效:

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

首页