WhiteBlue

$N \times M$의 격자에서 각 칸을 흰색 또는 파란색으로 칠하려고 한다. 일부 칸은 이미 색칠되어 있으며, 이 칸의 색은 바꿀 수 없다.

격자의 나머지 칸을 모두 칠하되, 가로로 연속된 세 칸 또는 세로로 연속된 세 칸이 모두 같은 색이 되지 않아야 한다.

조건을 만족하는 서로 다른 색칠 방법의 수를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $S_1$ $S_2$

조건을 만족하는 색칠 방법의 수를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

• $1 \le N \le 8$.
• $1 \le M \le 50$.
• $|S_i|=M$ ().