Farmer John は普通、丸い焼印を牛に付けますが、焼印が壊れたので括弧 ( の形で代用します。品種は Holstein と Guernsey の二つです。各牛の括弧の焼印は、向きによって左括弧にも右括弧にも見えます。

$N$ 頭が任意の向きで一列に立ち、印が長さ $N$ の括弧列に見えます。FJ は、左から右へ Holstein だけを順に読むと均衡した括弧列になり、Guernsey も同じだと気付きます。この現象が珍しいか調べるため、$N$ 頭の品種を割り当ててこの性質を満たす方法数を求めてください。

均衡の定義は複数あります。最も単純なのは ( と ) の総数が等しく、どの接頭辞でも ( が ) 以上にあることです。例えば次はすべて均衡しています。

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

次は均衡していません。

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

入力

• 1 行目：長さ $N$ $(1 \le N \le 1000)$ の括弧列。

出力

• 1 行目：Holstein と Guernsey の部分列がそれぞれ均衡する品種割り当て数を表す整数。大きくなるので 2012 で割った余り、つまり 2012 を法とした値を出力します。一品種だけを使う割り当ても有効です。

入出力例

入力 1

(())

出力 1

6

注記

次の割り当てが有効です。

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

問題作成：Brian Dean、2012