시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 263 | 120 | 90 | 46.392% |
크기가 N×M인 체스판이 있다. 체스판의 행 번호는 위에서부터 1, 2, ..., N이고, 열 번호는 왼쪽에서부터 1, 2, ..., M이다. 체스판의 각 칸은 (i, j)로 표현하고, i는 행 번호, j는 열 번호이다.
체스판의 각 칸은 흰색 또는 검정색으로 색칠되어 있다. (i+j)가 2로 나누어 떨어지면 칸 (i, j)의 색은 검정색, 그 외에는 흰색이다. 두 칸이 변이나 점을 공유하면 인접한 칸이다. 칸의 색상과 행 번호에 따라서 이동할 수 있는 방법이 다르다. 이동은 행 번호가 증가하는 쪽으로만 이동할 수 있다.
1번 행에서 출발해서 N번 행에 도착하는 방법의 수를 구해보자. 이동은 1번 행에 있는 칸 중 임의의 하나에서 출발할 수 있다.
첫째 줄에 N (1 ≤ N ≤ 109), M(1 ≤ M ≤ 30)이 주어진다.
1번 행에서 출발해서 N번 행에 도착하는 방법의 수를 109+7로 나눈 나머지를 출력한다.
1 5
5
2 5
8
3 5
22
4 5
38
5 5
104