{"raw_statement":[{"iden":"problem statement","content":"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`.\nSnuke has a string $s$, which is initially `AB`.\nLet $|s|$ denote the length of $s$. Snuke can do the four kinds of operations below zero or more times in any order:\n\n1.  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$.\n2.  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$.\n3.  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$.\n4.  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$.\n\nFind 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$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 1000$\n*   Each of $c_{\\mathrm{AA}}$, $c_{\\mathrm{AB}}$, $c_{\\mathrm{BA}}$, and $c_{\\mathrm{BB}}$ is `A` or `B`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$c_{\\mathrm{AA}}$\n$c_{\\mathrm{AB}}$\n$c_{\\mathrm{BA}}$\n$c_{\\mathrm{BB}}$"},{"iden":"sample input 1","content":"4\nA\nB\nB\nA"},{"iden":"sample output 1","content":"2\n\n*   There are two strings that can be $s$ when Snuke is done: `ABAB` and `ABBB`."},{"iden":"sample input 2","content":"1000\nB\nB\nB\nB"},{"iden":"sample output 2","content":"1\n\n*   There is just one string that can be $s$ when Snuke is done."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}