D - AB Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

整数 N と 4 つの文字 c_{\mathrm{AA}},c_{\mathrm{AB}},c_{\mathrm{BA}},c_{\mathrm{BB}} が与えられます。 ここで、与えられる 4 つの文字はいずれも A か B であることが保証されます。

すぬけ君は文字列 s を持っています。 s ははじめ AB です。

s の長さを |s| と書くことにします。 すぬけ君は以下の 4 種類の操作を任意の順序で 0 回以上行うことができます。

  1. 1 \leq i < |s|, s_{i} = A, s_{i+1} = A なる i を選んで、s の i 文字目と i+1 文字目の間に c_{\mathrm{AA}} を挿入する。
  2. 1 \leq i < |s|,s_{i} = A, s_{i+1} = B なる i を選んで、s の i 文字目と i+1 文字目の間に c_{\mathrm{AB}} を挿入する。
  3. 1 \leq i < |s|,s_{i} = B, s_{i+1} = A なる i を選んで、s の i 文字目と i+1 文字目の間に c_{\mathrm{BA}} を挿入する。
  4. 1 \leq i < |s|,s_{i} = B, s_{i+1} = B なる i を選んで、s の i 文字目と i+1 文字目の間に c_{\mathrm{BB}} を挿入する。

s の長さが N になるまで操作を行ったあとの s としてありうる文字列の個数を 10^9+7 で割ったあまりを求めてください。

制約

  • 2 \leq N \leq 1000
  • c_{\mathrm{AA}},c_{\mathrm{AB}},c_{\mathrm{BA}},c_{\mathrm{BB}} は A か B

入力

入力は以下の形式で標準入力から与えられる。

N
c_{\mathrm{AA}}
c_{\mathrm{AB}}
c_{\mathrm{BA}}
c_{\mathrm{BB}}

出力

s の長さが N になるまで操作を行ったあとの s としてありうる文字列の個数を 10^9+7 で割ったあまりを出力せよ。

入力例 1

4
A
B
B
A

出力例 1

2
  • s としてありうる文字列は ABAB と ABBB の 2 通りです。

入力例 2

1000
B
B
B
B

出力例 2

1
  • s としてありうる文字列は 1 通りです。

Score : 600 points

Problem Statement

Given are an integer N and four characters c_{\mathrm{AA}}, c_{\mathrm{AB}}, c_{\mathrm{BA}}, and c_{\mathrm{BB}}. Here, it is guaranteed that each of those four characters is A or B.

Snuke has a string s, which is initially AB.

Let |s| denote the length of s. Snuke can do the four kinds of operations below zero or more times in any order:

  1. Choose i such that 1 \leq i < |s|, s_{i} = A, s_{i+1} = A and insert c_{\mathrm{AA}} between the i-th and (i+1)-th characters of s.
  2. Choose i such that 1 \leq i < |s|, s_{i} = A, s_{i+1} = B and insert c_{\mathrm{AB}} between the i-th and (i+1)-th characters of s.
  3. Choose i such that 1 \leq i < |s|, s_{i} = B, s_{i+1} = A and insert c_{\mathrm{BA}} between the i-th and (i+1)-th characters of s.
  4. Choose i such that 1 \leq i < |s|, s_{i} = B, s_{i+1} = B and insert c_{\mathrm{BB}} between the i-th and (i+1)-th characters of s.

Find the number, modulo (10^9+7), of strings that can be s when Snuke has done the operations so that the length of s becomes N.

Constraints

  • 2 \leq N \leq 1000
  • Each of c_{\mathrm{AA}}, c_{\mathrm{AB}}, c_{\mathrm{BA}}, and c_{\mathrm{BB}} is A or B.

Input

Input is given from Standard Input in the following format:

N
c_{\mathrm{AA}}
c_{\mathrm{AB}}
c_{\mathrm{BA}}
c_{\mathrm{BB}}

Output

Print the number, modulo (10^9+7), of strings that can be s when Snuke has done the operations so that the length of s becomes N.

Sample Input 1

4
A
B
B
A

Sample Output 1

2
  • There are two strings that can be s when Snuke is done: ABAB and ABBB.

Sample Input 2

1000
B
B
B
B

Sample Output 2

1
  • There is just one string that can be s when Snuke is done.