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

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

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

<그림1>	<그림2>

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

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

0 0 1 2 

2 3 1 0 

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

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

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

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

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

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

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

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

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

1 2
1 2

2