{"problem":{"name":"AB","description":{"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`. Sn","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc108_d"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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`.\n\n## Input\n\nInput 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}}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc108_d","tags":[],"sample_group":[["4\nA\nB\nB\nA","2\n\n*   There are two strings that can be $s$ when Snuke is done: `ABAB` and `ABBB`."],["1000\nB\nB\nB\nB","1\n\n*   There is just one string that can be $s$ when Snuke is done."]],"created_at":"2026-03-03 11:01:13"}}