체스판 이동

시간 제한2초메모리 제한512 MB

요약

N×M 체스판에서 홀수 행은 같은 색 인접 칸으로만, 짝수 행은 색 제약 없이 인접 칸으로 이동할 수 있을 때 1행에서 N행에 도착하는 경로의 수를 10^9+7로 나눈 나머지를 구한다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 행렬, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

크기가 N×M인 체스판이 있다. 체스판의 행 번호는 위에서부터 1, 2, ..., N이고, 열 번호는 왼쪽에서부터 1, 2, ..., M이다. 체스판의 각 칸은 (i, j)로 표현하고, i는 행 번호, j는 열 번호이다.

체스판의 각 칸은 흰색 또는 검정색으로 칠해져 있다. (i+j)가 2로 나누어 떨어지면 칸 (i, j)의 색은 검정색, 그 외에는 흰색이다. 두 칸이 변이나 점을 공유하면 인접한 칸이다. 칸의 색상과 행 번호에 따라 이동할 수 있는 방법이 다르다. 이동은 행 번호가 증가하는 쪽으로만 할 수 있다.

행 번호가 홀수인 경우
- 검정색 칸에 있으면, 인접한 검정색 칸으로 이동할 수 있다.
- 흰색 칸에 있으면, 인접한 흰색 칸으로 이동할 수 있다.
행 번호가 짝수인 경우
- 인접한 칸으로 이동할 수 있으며, 홀수 행과는 달리 색상과 관련된 제한은 없다.

1번 행에서 출발해서 N번 행에 도착하는 방법의 수를 구해보자. 이동은 1번 행에 있는 칸 중 임의의 하나에서 출발할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 10^9), M(1 ≤ M ≤ 30)이 주어진다.

출력

1번 행에서 출발해서 N번 행에 도착하는 방법의 수를 10^9+7로 나눈 나머지를 출력한다.

예제5

예제 1
입력
```
1 5
```
예상 출력
```
5
```
예제 2
입력
```
2 5
```
예상 출력
```
8
```
예제 3
입력
```
3 5
```
예상 출력
```
22
```
예제 4
입력
```
4 5
```
예상 출력
```
38
```
예제 5
입력
```
5 5
```
예상 출력
```
104
```