字符串

题目描述

给定整数 $N$ 和四个字符 $c_{AA},c_{AB},c_{BA},c_{BB}$。这四个字符均为 A 或 B。

初始时有一个字符串 $s=$ AB。

你可以进行若干次操作。每次操作选择字符串中相邻的两个字符，并根据这两个字符在它们中间插入一个新字符：

1. 若相邻字符为 AA，则在中间插入 $c_{AA}$。
2. 若相邻字符为 AB，则在中间插入 $c_{AB}$。
3. 若相邻字符为 BA，则在中间插入 $c_{BA}$。
4. 若相邻字符为 BB，则在中间插入 $c_{BB}$。

请你求当字符串长度恰好变为 $N$ 时，可能得到多少种不同的字符串。答案对 $10^9+7$ 取模。

如果不同的操作顺序产生了相同的最终字符串，只计为一种。$N=2$ 时可以不操作。

输入格式

输入共五行，依次为：

N
c_AA
c_AB
c_BA
c_BB

其中第 $2$ 至第 $5$ 行各包含一个字符 A 或 B。

输出格式

输出一行一个整数，表示不同字符串数量对 $10^9+7$ 取模后的结果。

样例 1

4
A
B
B
A

2

可能得到的字符串有 ABAB 和 ABBB 两种。

样例 2

见下发文件：string2.in 与 string2.out。

样例 3

见下发文件：string3.in 与 string3.out。

数据范围

对于 $100\%$ 的数据，$2\le N\le10^6$，$c_{AA},c_{AB},c_{BA},c_{BB}\in\{\mathrm{A},\mathrm{B}\}$。

更多样例

以下 2 组样例取自原题附件：

• string-down1.in / string-down1.out
• string-down2.in / string-down2.out