#1523 타일 채우기

17  2 s   128 MB  

Description

R x C 크기로 이루어진 직사각형이 있다. R, C가 주어질 때 이 직사각형 안에 1x2의 직사각형 또는 2x1의 직사각형을 채워 넣을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

Input

각 테스트 케이스마다 직사각형의 크기 R, C가 들어온다. R, C는 정수이며 R, C가 모두 -1로 들어올 경우 프로그램을 종료한다. ( 1 <= R <= 8, 1 <= C <= 100 )

Output

각 테스트 케이스마다 R x C 크기의 직사각형에 1x2 또는 2x1 크기의 직사각형을 채워넣을 수 있는 경우의 수를 구하여 출력하라. 만약 답이 1,000,000,007보다 크다면 1,000,000,007으로 나눈 나머지를 출력하라.

Sample Input

Sample Output

2 1
3 2
3 8
4 10
-1 -1
1
3
153
18061

Source

From Arshuaz