AB

时间限制：2s
空间限制：1024MB

题目描述

给定整数 $N$ 以及四个字符 $c_{\mathrm{AA}},c_{\mathrm{AB}},c_{\mathrm{BA}},c_{\mathrm{BB}}$，每个字符均为 A 或 B。

初始字符串 $s$ 为 AB。若相邻两个字符为 $x,y\in\{\texttt{A},\texttt{B}\}$，你可以在它们之间插入字符 $c_{xy}$。可以按任意顺序进行操作，直到字符串长度变为 $N$。

求最终可能得到的不同字符串数量，对 $10^9+7$ 取模。

输入格式

N
c_AA
c_AB
c_BA
c_BB

输出格式

输出答案对 $10^9+7$ 取模后的值。

样例输入 1

4
A
B
B
A

样例输出 1

2

样例输入 2

1000
B
B
B
B

样例输出 2

1

数据范围

• $2\le N\le1000$；
• $c_{\mathrm{AA}},c_{\mathrm{AB}},c_{\mathrm{BA}},c_{\mathrm{BB}}\in\{\texttt{A},\texttt{B}\}$。