영재의 징검다리

푸앙이 게임에 참가한 영재는 유리 징검다리 게임을 통과해야 한다.

유리 징검다리 게임의 규칙은 간단하다. 총 $N$번의 걸음을 통해 건널 수 있고, 각 걸음마다 $M$개의 칸이 있다. 영재는 시작점($N-1$번째 줄)의 한 칸에서 건너기 시작해 이후 앞의 인접한 최대 3개의 유리 중 하나를 선택해 건너갈 수 있다. 밟은 칸이 강화유리라면 안전하게 건널 수 있지만, 일반 유리는 밟을 수 없다.

다음은 $N = 3$, $M = 5$인 어느 순간에 영재가 가능한 이동을 나타낸 그림이다.

다리의 정보가 주어지면, 영재가 다리를 무사히 건널 수 있는 경우의 수를 구해 보자.

첫 줄에 $N$과 $M$($1 \le N, M \le 1{,}000$)이 공백으로 구분되어 주어지고, 그 뒤에는 $N$줄에 걸쳐 다리의 정보가 주어진다.

강화유리의 경우 1, 일반 유리의 경우 0으로 주어진다.

영재가 무사히 다리를 건널 수 있는 경우의 수를 $1{,}000{,}000{,}007$로 나눈 나머지를 출력한다.