5409 : C10 - 긴 격자 채우기 (A Long Grid)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
세로 $2$ 행, 가로 $W$ 열의 직사각형 격자판이 있습니다.
상하좌우로 인접한 두 칸이 같은 색이 되지 않도록, 격자의 모든 칸을 빨강, 노랑, 초록, 파랑의 $4$ 가지 색 중 하나로 칠하는 경우의 수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le W \le 10^9$
• 입력되는 모든 값은 정수입니다.
상하좌우로 인접한 두 칸이 같은 색이 되지 않도록, 격자의 모든 칸을 빨강, 노랑, 초록, 파랑의 $4$ 가지 색 중 하나로 칠하는 경우의 수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le W \le 10^9$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 정수 $W$ 가 주어집니다.
출력 설명
색칠하는 경우의 수를 $10^9 + 7$ 로 나눈 나머지를 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
12도움
$W = 1$ 일 때, $2$ 칸을 서로 다른 색으로 칠하는 방법은 $4 \times 3 = 12$ 가지입니다.
각 열을 칠할 때 이전 열의 색 배치와 인접하지 않게 칠하는 전이 경우의 수는 항상 $7$ 가지이므로, 전체 방법의 수는 $12 \times 7^{W-1} \pmod{10^9+7}$ 이 됩니다.
각 열을 칠할 때 이전 열의 색 배치와 인접하지 않게 칠하는 전이 경우의 수는 항상 $7$ 가지이므로, 전체 방법의 수는 $12 \times 7^{W-1} \pmod{10^9+7}$ 이 됩니다.