직사각형 색칠 2

단위 정사각형으로 나누어진 $N \times M$ 크기의 직사각형이 주어졌을 때, 다음 조건을 만족하도록 색칠하는 방법의 수를 구하는 프로그램을 작성하시오.

• 모든 칸은 검정색 또는 흰색 중 하나로 색칠해야 한다.
• 같은 색으로 이루어진 $2 \times 2$ 크기의 정사각형이 없어야 한다.

$N = 3$, $M = 3$인 경우 올바른 색칠 방법

$N = 3$, $M = 3$인 경우 올바르지 않은 색칠 방법

$N, M$이 주어졌을 때, $N \times M$ 크기의 직사각형을 올바르게 색칠하는 방법의 수를 $1\,000\,000\,007$로 나눈 나머지를 구해보자.

첫째 줄에 $N$ ($1 \le N \le 10^{18}$), $M$ ($1 \le M \le 5$)이 주어진다.

첫째 줄에 $N \times M$ 크기의 직사각형을 올바르게 색칠하는 방법의 수를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.