1510: [2020 세종 정올 본선] 세종이의 블록 쌓기(L)

세종이는 블록 판에 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