正しい括弧列 VB(Beta)編（paizaランク A 相当）

正しい括弧列を次のように定義します。
・空文字列 (長さ 0 の文字列)
・正しい括弧列 A が存在し、左括弧 (, A, 右括弧 ) をこの順に結合した文字列
・正しい括弧列 A, B が存在し、A, B をこの順に結合した文字列

長さ L の正しい括弧列の数を求めてください。
ただし、非常に大きな数になる可能性があるので、(10^10)で割った余りを出力してください。

例えば、長さ 6 の正しい括弧列は ((())), (()()), (())(), ()(()), ()()()の 5 つです。
長さ 7 の正しい括弧列は 1 つもありません。

・ヒント
正しい括弧列となるための条件として次の 2 つがあります。
条件 1: ある括弧列を左から順に読み込むとする。このとき、既に出てきた左括弧の数よりも右括弧の数が多くなった場合は正しい括弧列にはならない。
条件 2: 正しい括弧列の左括弧の数と右括弧の数は必ず同じになる。