You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ARC108D] AB

题目描述

给出四个大写字母 $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$ 后，所有可能的字符串共有多少种？

输入格式

第一行一个整数 $n$ ，接下来四行每行一个字符分别表示 $c_{AA}$、$c_{AB}$、$c_{BA}$、$c_{BB}$。保证 $c_{AA}$、$c_{AB}$、$c_{BA}$、$c_{BB}$ 均为 $A$ 或 $B$。

输出格式

输出长度为 $n$ 的最终字符串的可能种数对 $10^9+7$ 取模的结果。

样例 #1

样例输入 #1

4
A
B
B
A

样例输出 #1

2

样例 #2

样例输入 #2

1000
B
B
B
B

样例输出 #2

1

数据范围

• $2\ \leq\ N\ \leq\ 1000$

样例解释 1

- $s$ 可以是 ABAB 或者 ABBB 。

样例解释 2

- $s$ 只能是 ABBBB...BBBB。