题目描述

整数 $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$ で割ったあまりを求めてください。

输入格式

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

$N$ $c_{\mathrm{AA}}$ $c_{\mathrm{AB}}$ $c_{\mathrm{BA}}$ $c_{\mathrm{BB}}$

输出格式

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

题目大意

给出四个大写字母 $c_{AA}$、$c_{AB}$、$c_{BA}$、$c_{BB}$ 和一个初始字符串 $s=AB$ ，每次操作可以选择字符串中相邻的两个字母 $s_i$、$s_{i+1}$ 并按下列规则在两个字母之间插入一个新的字母。

• 若 $s_i=A$ 且 $s_{i+1}=A$，则在两者之间插入字母 $c_{AA}$。
• 若 $s_i=A$ 且 $s_{i+1}=B$，则在两者之间插入字母 $c_{AB}$。
• 若 $s_i=B$ 且 $s_{i+1}=A$，则在两者之间插入字母 $c_{BA}$。
• 若 $s_i=B$ 且 $s_{i+1}=B$，则在两者之间插入字母 $c_{BB}$。

保证 $c_{AA}$、$c_{AB}$、$c_{BA}$、$c_{BB}$ 均为 $A$ 或 $B$。

求当 $s$ 的长度被添加至 $n$ 后，所有可能的字符串共有多少种？

样例一：可能出现的有 ABAB 和 ABBB。

样例二：只可能出现 ABBBB...BBBB 一种。

4
A
B
B
A

2

1000
B
B
B
B

1

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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