24392번 - 영재의 징검다리

문제

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

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

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

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

입력

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

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

출력

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

제한

힌트