18287번 - 체스판 이동

문제

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

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

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

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

입력

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

출력

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

제한

힌트