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

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

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

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

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

0 0 1 2

2 3 1 0

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

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

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

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