分数: 600 点
问题陈述
给定一个整数 N 和四个字符 c_{\mathrm{AA}}, c_{\mathrm{AB}}, c_{\mathrm{BA}},和 c_{\mathrm{BB}}。
这里,保证这四个字符中的每一个都是 A or B.
Snuke 有一根绳子 s,最初是 AB.
让 |s| 表示长度 s。 Snuke 可以按任意顺序执行零次或多次以下的四种操作:
- 选择 i 这样 1 \leq i < |s|, s_{i} =
A, s_{i+1} =A并插入 c_{\mathrm{AA}} 之间 i-th 和 (i+1)第一个字符 s. - 选择 i 这样 1 \leq i < |s|, s_{i} =
A, s_{i+1} =B并插入 c_{\mathrm{AB}} 之间 i-th 和 (i+1)第一个字符 s. - 选择 i 这样 1 \leq i < |s|, s_{i} =
B, s_{i+1} =A并插入 c_{\mathrm{BA}} 之间 i-th 和 (i+1)第一个字符 s. - 选择 i 这样 1 \leq i < |s|, s_{i} =
B, s_{i+1} =B并插入 c_{\mathrm{BB}} 之间 i-th 和 (i+1)第一个字符 s.
求模数 (10^9+7),可以是 s 当 Snuke 完成操作后, s 变为 分别为 N.
约束
- 2 \leq N \leq 1000
- 每个 c_{\mathrm{AA}}, c_{\mathrm{AB}}, c_{\mathrm{BA}},和 c_{\mathrm{BB}} is
AorB.
输入
输入由标准输入按以下格式给出:
N
c_{\mathrm{AA}}
c_{\mathrm{AB}}
c_{\mathrm{BA}}
c_{\mathrm{BB}}
输出
打印数字,模数 (10^9+7),可以是 s 当 Snuke 完成操作后, s 变为 分别为 N.
示例输入 1
4 A B B A
示例输出 1
2
- 有两个字符串可以 s 当 Snuke 完成时:
ABAB和ABBB.
示例输入 2
1000 B B B B
示例输出 2
1
- 只有一个字符串可以 s 当 Snuke 完成时。