문제1523--타일 채우기

1523: 타일 채우기

실행시간 제한: 2 Sec  메모리사용 제한: 128 MB
제출: 70  통과: 28
[제출] [채점기록] [묻고답하기]

문제 설명

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

입력 설명

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

출력 설명

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

입력 예시 Copy

2 1
3 2
3 8
4 10
-1 -1

출력 예시 Copy

1
3
153
18061

출처/분류