题目描述

给定一个整数 $N$ 和四个字符 $c_{\mathrm{AA}}$、$c_{\mathrm{AB}}$、$c_{\mathrm{BA}}$ 和 $c_{\mathrm{BB}}$。这四个字符保证都是 A 或 B。

Snuke 有一个字符串 $s$，初始为 AB。

记 $|s|$ 为字符串 $s$ 的长度。Snuke 可以以任意顺序、零次或多次进行以下四种操作：

1. 选择 $i$，满足 $1 \leq i < |s|$，$s_i$ = A，$s_{i+1}$ = A，并在字符串 $s$ 的第 $i$ 和第 $(i+1)$ 之间插入字符 $c_{\mathrm{AA}}$。
2. 选择 $i$，满足 $1 \leq i < |s|$，$s_i$ = A，$s_{i+1}$ = B，并在字符串 $s$ 的第 $i$ 和第 $(i+1)$ 之间插入字符 $c_{\mathrm{AB}}$。
3. 选择 $i$，满足 $1 \leq i < |s|$，$s_i$ = B，$s_{i+1}$ = A，并在字符串 $s$ 的第 $i$ 和第 $(i+1)$ 之间插入字符 $c_{\mathrm{BA}}$。
4. 选择 $i$，满足 $1 \leq i < |s|$，$s_i$ = B，$s_{i+1}$ = B，并在字符串 $s$ 的第 $i$ 和第 $(i+1)$ 之间插入字符 $c_{\mathrm{BB}}$。

计算满足 Snuke 进行操作后字符串 $s$ 长度为 $N$ 的字符串数量，对 $(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}}$

输出

输出满足 Snuke 进行操作后字符串 $s$ 长度为 $N$ 的字符串数量，对 $(10^9+7)$ 取模。

示例输入 1

4
A
B
B
A

示例输出 1

2

• 当 Snuke 进行操作后，有两种可能的字符串：ABAB 和 ABBB。

示例输入 2

1000
B
B
B
B

示例输出 2

1

• 当 Snuke 进行操作后，只有一种可能的字符串。