問題文

あなたは特別講演「括弧列と塗り分け」の講演者です。今日は(と)だけからなる文字列 $S$ に対する色の塗り分け方を紹介することにしました。 $S$ は括弧の対応に矛盾がないことが保証されます。

$S$ 中の全ての文字を赤色か青色に塗ることを考えます。 その際 $i$ 番目の文字である(と $j$ 番目の文字である)が対応しているならば、 $S$ の $i$ 文字目から $j$ 文字目までの 部分文字列 S\[i,j\] に含まれる赤色の文字の数を $R$、青色の文字の数を $B$ としたときに、 $|R-B|≦K$ を満たすように塗らなくてはなりません。

条件を満たす色の塗り方の総数を $1,000,000,007$ で割った余りを求めてください。

この問題において、括弧の対応に矛盾がない文字列とは以下のように定義されます。

1. 空文字列は括弧の対応に矛盾がない文字列である。
2. 括弧の対応に矛盾がない文字列 $A,B$ に対し、 $A$ と $B$ を結合してできる文字列 $AB$ も括弧の対応に矛盾がない文字列である。
3. 括弧の対応に矛盾がない文字列 $A$ に対し、文字列($A$) は括弧の対応に矛盾がない文字列である。また、この両端の(と)は対応していると呼ばれる。
4. 上記のいずれも満たさない文字列は括弧の対応に矛盾がある文字列である。

---

入力

入力は以下の形式で標準入力から与えられる。

$S$ $K$

• $1$ 行目に括弧列 $S (2≦|S|≦3,000)$ が与えられる。 $S$ は括弧の対応に矛盾がないことが保証される。
• $2$ 行目に塗りわける際の制約を表す整数 $K(0≦K≦3,000)$ が与えられる。

出力

条件を満たす色の塗り方の総数を $1,000,000,007$ で割った余りを出力せよ。末尾の改行を忘れないこと。

部分点

この問題には部分点が設定されている。

• $2≦|S|≦8$ を満たすようなデータセットに正解した場合 $10$ 点が与えられる。
• $2≦|S|≦100$ を満たすようなデータセットに正解した場合上記の部分点とは別に $10$ 点が与えられる。
• 追加制約のないデータセットに正解した場合さらに $50$ 点が得られ合計 $70$ 点が得られる。

---

入力例 1

()()
0

出力例 1

4

• $1$ 文字目の(と $2$ 文字目の)が、$3$ 文字目の(と $4$ 文字目の)が対応関係にあります。
• 便宜上赤色で塗られた括弧を<>、青色で塗られた括弧を[]で表すことにします。
• 答えは<]<]、<][>、[><]、[>[>の $4$ 通りです。
• <><]のような塗り方は、S\[1,2\] において $|R-B|≦K$ の制約を満たしません。
• このケースは $1$ つ目の部分点制約を満たします。

---

入力例 2

()()
2

出力例 2

16

• 答えは<><>、<><]、<>[]、<>[>、<]<>、<]<]、<][]、<][>、[><>、[><]、[>[]、[>[>、[]<>、[]<]、[][]、[][>の $16$ 通りです。
• このケースは $1$ つ目の部分点制約を満たします。

---

入力例 3

(()())
2

出力例 3

50

• $1$ 文字目の(と $6$ 文字目の)、$2$ 文字目の(と $3$ 文字目の)、$4$ 文字目の(と $5$ 文字目の)が対応関係にあります。
• このケースは $1$ つ目の部分点制約を満たします。

---

入力例 4

()()()()()()()()()()()()()()()()
2

出力例 4

294967268

• 塗り分け方の総数は $4,294,967,296$ ですが、 $1,000,000,007$ で割った余りである $294,967,268$ を出力してください。
• このケースは $2$ つ目の部分点制約を満たします。

---