問題文

整数 $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$ で割ったあまりを出力せよ。

入力例 1

4
A
B
B
A

出力例 1

2

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

入力例 2

1000
B
B
B
B

出力例 2

1

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