← 返回题目列表

AtCoder · arc108_d

D. 甲乙

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给定一个整数 N 和四个字符 c_{\mathrm{AA}}, c_{\mathrm{AB}}, c_{\mathrm{BA}},和 c_{\mathrm{BB}}。 这里,保证这四个字符中的每一个都是 A or B.

Snuke 有一根绳子 s,最初是 AB.

让 |s| 表示长度 s。 Snuke 可以按任意顺序执行零次或多次以下的四种操作:

  1. 选择 i 这样 1 \leq i < |s|, s_{i} = A, s_{i+1} = A 并插入 c_{\mathrm{AA}} 之间 i-th 和 (i+1)第一个字符 s.
  2. 选择 i 这样 1 \leq i < |s|, s_{i} = A, s_{i+1} = B 并插入 c_{\mathrm{AB}} 之间 i-th 和 (i+1)第一个字符 s.
  3. 选择 i 这样 1 \leq i < |s|, s_{i} = B, s_{i+1} = A 并插入 c_{\mathrm{BA}} 之间 i-th 和 (i+1)第一个字符 s.
  4. 选择 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 A or B.

输入

输入由标准输入按以下格式给出:

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 完成时。