18289번 - 팀 연습 더

문제

A, B, C 세 사람이 다가오는 ICPC 대회를 위해 팀 연습을 하려고 한다. ICPC 대회는 팀 대회이기 때문에, 어떤 사람이 어떤 문제를 풀지 결정하는 것도 중요하다. 따라서, 오늘 연습은 세 사람이 모두 풀 수 있는 문제 N개를 풀 것이다. 문제는 1번부터 N번까지 번호가 매겨져 있다.

세 사람이 문제 N개를 푸는 방법은 다음과 같다.

• 문제는 1번부터 문제 번호가 증가하는 순서대로 해결해야 한다.
• 각 문제를 푸는 사람은 세 사람 중 한 명이다.
• A가 해결한 문제의 수는 K의 배수가 되어야 한다.
• B는 문제를 연속해서 풀 수 없다.
• C는 한 문제 이상 해결해야 한다.

N과 K가 주어졌을 때, 문제를 푸는 사람을 정하는 방법의 수를 모두 구해보자.

입력

첫째 줄에 N (1 ≤ N ≤ 10¹⁸), K (0 ≤ K ≤ 10)가 주어진다.

출력

첫째 줄에 문제 N개를 모두 푸는 사람을 정하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

제한

힌트