配点 : $600$ 点

問題文

整数 $N$ と $4$ つの文字 $c_{\mathrm{AA}},c_{\mathrm{AB}},c_{\mathrm{BA}},c_{\mathrm{BB}}$ が与えられます。 ここで、与えられる $4$ つの文字はいずれも A か B であることが保証されます。

すぬけ君は文字列 $s$ を持っています。 $s$ ははじめ AB です。

$s$ の長さを $|s|$ と書くことにします。 すぬけ君は以下の $4$ 種類の操作を任意の順序で $0$ 回以上行うことができます。

1. $1 \leq i < |s|, s_{i}$ = A, $s_{i+1}$ = A なる $i$ を選んで、$s$ の $i$ 文字目と $i+1$ 文字目の間に $c_{\mathrm{AA}}$ を挿入する。
2. $1 \leq i < |s|,s_{i}$ = A, $s_{i+1}$ = B なる $i$ を選んで、$s$ の $i$ 文字目と $i+1$ 文字目の間に $c_{\mathrm{AB}}$ を挿入する。
3. $1 \leq i < |s|,s_{i}$ = B, $s_{i+1}$ = A なる $i$ を選んで、$s$ の $i$ 文字目と $i+1$ 文字目の間に $c_{\mathrm{BA}}$ を挿入する。
4. $1 \leq i < |s|,s_{i}$ = B, $s_{i+1}$ = B なる $i$ を選んで、$s$ の $i$ 文字目と $i+1$ 文字目の間に $c_{\mathrm{BB}}$ を挿入する。

$s$ の長さが $N$ になるまで操作を行ったあとの $s$ としてありうる文字列の個数を $10^9+7$ で割ったあまりを求めてください。

制約

• $2 \leq N \leq 1000$
• $c_{\mathrm{AA}},c_{\mathrm{AB}},c_{\mathrm{BA}},c_{\mathrm{BB}}$ は A か B

入力

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

$N$

$c_{\mathrm{AA}}$

$c_{\mathrm{AB}}$

$c_{\mathrm{BA}}$

$c_{\mathrm{BB}}$

出力

$s$ の長さが $N$ になるまで操作を行ったあとの $s$ としてありうる文字列の個数を $10^9+7$ で割ったあまりを出力せよ。

4
A
B
B
A

2

• $s$ としてありうる文字列は ABAB と ABBB の $2$ 通りです。

1000
B
B
B
B

1

• $s$ としてありうる文字列は $1$ 通りです。