14275번 - 직사각형 색칠
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 10 | 6 | 4 | 57.143% |
문제
단위 정사각형으로 나누어져 있는 N×M 크기의 직사각형이 주어졌을 때, 아래 조건을 만족하게 색칠하는 방법의 수를 구하는 프로그램을 작성하시오.
- 모든 칸은 색칠되어 있거나 비어있어야 한다.
- 색칠된 칸과 인접한 색칠된 칸의 짝수개이어야 한다.
아래 그림은 N=4, M=7인 경우의 예이다. (노란색: 색칠, 검정색: 빈 칸)
N과 M이 주어졌을 때, 색칠하는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 8)
출력
첫째 줄에 입력으로 주어진 직사각형을 색칠하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.
예제 입력 1
1 1
예제 출력 1
2
예제 입력 2
2 2
예제 출력 2
8
예제 입력 3
1 3
예제 출력 3
5
예제 입력 4
47 7
예제 출력 4
944149920
힌트
예제 2의 경우 아래와 같은 8가지 방법이 가능하다.
