Problem Statement

Given are an integer $N$ and four characters cAA​, cAB​, cBA​, and cBB​. Here, it is guaranteed that each of those four characters is A or B.

Snuke has a string $s$, which is initially AB.

Let $|s|$ denote the length of $s$. Snuke can do the four kinds of operations below zero or more times in any order:

1. Choose $i$ such that $1\le i<|s|$, si​ = A, si+1​ = A and insert cAA​ between the $i$-th and $(i+1)$-th characters of $s$.
2. Choose $i$ such that $1\le i<|s|$, si​ = A, si+1​ = B and insert cAB​ between the $i$-th and $(i+1)$-th characters of $s$.
3. Choose $i$ such that $1\le i<|s|$, si​ = B, si+1​ = A and insert cBA​ between the $i$-th and $(i+1)$-th characters of $s$.
4. Choose $i$ such that $1\le i<|s|$, si​ = B, si+1​ = B and insert cBB​ between the $i$-th and $(i+1)$-th characters of $s$.

Find the number, modulo (109+7), of strings that can be $s$ when Snuke has done the operations so that the length of $s$ becomes $N$.

Constraints

• $2\le N\le 1000$
• Each of cAA​, cAB​, cBA​, and cBB​ is A or B.

Sample Input 1

4
A
B
B
A

Sample Output 1

2

• There are two strings that can be $s$ when Snuke is done: ABAB and ABBB.

Sample Input 2

1000
B
B
B
B

Sample Output 2

1

• There is just one string that can be $s$ when Snuke is done.