题目描述

给定一个整数 $N$ 和 $4$ 个字符 $c\_{\texttt{AA}}, c\_{\texttt{AB}}, c\_{\texttt{BA}}, c\_{\texttt {BB}}$。这里，保证给定的 $4$ 个字符均为 $\texttt A$ 或 $\texttt B$。

すぬけ君有一个字符串 $s$。初始时，$s$ 为 $\texttt {AB}$。

记 $s$ 的长度为 $|s|$。すぬけ君可以以任意顺序、任意次数（包括 $0$ 次）进行以下 $4$ 种操作：

1. 选择 $1 \leq i < |s|$，且 $s_i$ 为 $\texttt A$，$s_{i+1}$ 为 $\texttt A$，在 $s$ 的第 $i$ 个字符和第 $i+1$ 个字符之间插入 $c_{\texttt {AA}}$。
2. 选择 $1 \leq i < |s|$，且 $s_i$ 为 $\texttt A$，$s_{i+1}$ 为 $\texttt B$，在 $s$ 的第 $i$ 个字符和第 $i+1$ 个字符之间插入 $c_{\texttt {AB}}$。
3. 选择 $1 \leq i < |s|$，且 $s_i$ 为 $\texttt B$，$s_{i+1}$ 为 $\texttt A$，在 $s$ 的第 $i$ 个字符和第 $i+1$ 个字符之间插入 $c_{\texttt {BA}}$。
4. 选择 $1 \leq i < |s|$，且 $s_i$ 为 $\texttt B$，$s_{i+1}$ 为 $\texttt B$，在 $s$ 的第 $i$ 个字符和第 $i+1$ 个字符之间插入 $c_{\texttt{BB}}$。

请你求出，经过若干次操作后，使得 $s$ 的长度变为 $N$ 时，可能得到的不同字符串的数量。答案对 $10^9+7$ 取模。

输入格式

输入从标准输入读入，格式如下：

$N$ $c_{\texttt {AA}}$ $c_{\texttt {AB}}$ $c_{\texttt {BA}}$ $c_{\texttt {BB}}$

输出格式

输出使 $s$ 的长度变为 $N$ 时，可能得到的不同字符串的数量，对 $10^9+7$ 取模。

样例 1

输入

4
A
B
B
A

输出

2

样例 2

输入

1000
B
B
B
B

输出

1

说明/提示

限制条件

• $2 \leq N \leq 1000$
• $c\_{\texttt {AA}}, c\_{\texttt {AB}}, c\_{\texttt {BA}}, c\_{\texttt {BB}}$ 均为 A 或 B

样例解释 1

• 可能得到的字符串为 $\texttt {ABAB}$和$\texttt {ABBB}$，共 $2$ 种。

样例解释 2

• 可能得到的字符串为 $1$ 种。