AT_arc108_d [ARC108D] AB

给定一个整数 $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$ 取模。

## 限制条件 - $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$ 种。