Team Practice More

Time limit1sMemory limit512 MB

Summary

Count assignments of N problems to three people where A's count is a multiple of K, B never solves two in a row, and C solves at least one, mod 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math, Matrix
Solved: No attempts yet

Problem

Three people, A, B, and C, are holding team practice for an upcoming ICPC contest. Because the ICPC is a team contest, deciding who solves which problem matters. So today's practice will solve N problems that all three of them can solve. The problems are numbered from 1 to N.

The three people solve the N problems as follows.

The problems must be solved in increasing order of their numbers, starting from problem 1.
Each problem is solved by exactly one of the three people.
The number of problems A solves must be a multiple of K.
B cannot solve problems in a row.
C must solve at least one problem.

Given N and K, count the number of ways to decide who solves each problem.

Input

The first line contains N (1 ≤ N ≤ 10^18) and K (0 ≤ K ≤ 10).

Output

Print the number of ways to decide who solves all N problems, modulo 1,000,000,007, on the first line.

Examples5

Example 1
Input
```
2 0
```
Expected output
```
3
```
Example 2
Input
```
2 1
```
Expected output
```
5
```
Example 3
Input
```
3 1
```
Expected output
```
17
```
Example 4
Input
```
3 2
```
Expected output
```
8
```
Example 5
Input
```
3 3
```
Expected output
```
5
```