영재의 징검다리

면접 대비

시간 제한0.5초메모리 제한512 MB

요약

N행 M열 격자에서 한 행씩 이동하며 직전 위치에서 3칸 이내의 1인 칸만 밟아 건널 수 있는 경우의 수를 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 누적 합, 행렬, 구현
정답자: 아직 제출이 없습니다

문제

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

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

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

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

입력

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

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

출력

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

예제3

예제 1
입력
```
3 2
0 1
1 0
0 1
```
예상 출력
```
1
```

예제 2

입력

예상 출력

예제 3
입력
```
4 4
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1
```
예상 출력
```
8
```