2021.1.20.(목) ~ 1.21.(금) 에 SFPC가 열립니다. 자세한 사항은 11월에 학교로 안내될 공문을 참고해주세요.
문제1054--세종이의 블록 쌓기(L)

1054: 세종이의 블록 쌓기(L)

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 128 MB

제출
문제 설명

세종이는 블록 판에 1 * 2 블록과 1 * 1 블록을 이용하여 블록 쌓기 놀이를 하고 있다.

아래 그림에서 블록이 쌓인 모양이 <그림1>과 같을 때, 이를 위에서 본 모양은 <그림2>와 같고 각 영역의 블록의 높이를 나타내면 <그림3>과 같다.





<그림1> <그림2> <그림3>


세종이가 하는 블록 쌓기 놀이를 구경하고 있던 이도는 완성된 모양이 주어질 때, 주어진 두 가지 모양의 블록들을 이용하여 완성된 모양으로 쌓을 수 있는 경우의 수가 궁금해 졌다.

단, 블록은 아래서 부터 빈 공간 없이 쌓아 올려야 한다. 아래와 같은 모양은 만들 수 없다.





0 0 1 2

2 3 1 0

높이가 위와 같이 주어졌을 때 만들 수 있는 여러 가지 경우 중 일부는 다음과 같다.





1 * 1 블록과 1 * 2 블록은 무한히 많이 준비되어 있다.

완성된 모양이 주어질 때, 만들 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

(단, 1 * 2 블록을 세워서 사용할 수는 없다)

입력 설명

완성된 모양을 위에서 바라보았을 때의 가로(n)와 세로(m) 크기가 공백을 기준으로 주어진다.

2번째 줄부터 n * m 의 높이(a_i)가 공백을 기준으로 주어진다.

(1 <= n, m <= 10), (0 <= a_i <= 3)



출력 설명

가능한 경우의 수를 출력한다.

(단, 수가 너무 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다)

입력 예시 복사
1 2
1 2
출력 예시 복사
2
도움
위 예시에 해당하는 경우는 다음과 같이 2가지이다.
 
출처/분류