cho.sh직사각형 색칠 2
M은 5 이하이고 N은 10^18까지인 N×M 격자를 단색 2×2 블록이 없도록 검정 또는 흰색으로 칠하는 방법의 수를 1,000,000,007로 나눈 나머지를 구한다.
어려움8동적 계획법행렬비트 연산조합론아직 제출이 없습니다시간 제한1초메모리 제한512 MB문제 설명
예제3
문제
단위 정사각형으로 나누어져 있는 N×M 크기의 직사각형이 주어졌을 때, 아래 조건을 만족하게 색칠하는 방법의 수를 구하는 프로그램을 작성하시오.
- 모든 칸은 검정색 또는 흰색 중 하나로 색칠해야 한다.
- 같은 색으로 이루어진 2×2 크기의 정사각형이 없어야 한다.
N = 3, M = 3인 경우 올바른 색칠 방법
N = 3, M = 3인 경우 올바르지 않은 색칠 방법
N, M이 주어졌을 때, N×M 크기의 직사각형을 올바르게 색칠하는 방법의 수를 1,000,000,007로 나눈 나머지를 구해보자.
입력
첫째 줄에 N (1 ≤ N ≤ 1018), M (1 ≤ M ≤ 5)이 주어진다.
출력
첫째 줄에 N×M 크기의 직사각형을 올바르게 색칠하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.