시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 45 28 21 60.000%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

2 0

예제 출력 1

3

예제 입력 2

2 1

예제 출력 2

5

예제 입력 3

3 1

예제 출력 3

17

예제 입력 4

3 2

예제 출력 4

8

예제 입력 5

3 3

예제 출력 5

5

예제 입력 6

5 1

예제 출력 6

151

예제 입력 7

5 2

예제 출력 7

76

예제 입력 8

5 3

예제 출력 8

43