Reziba has many magic gems. Each magic gem can be split into $M$ normal gems. The amount of space each magic (and normal) gem takes is $1$ unit. A normal gem cannot be split.

Reziba wants to choose a set of magic gems and split some of them, so the total space occupied by the resulting set of gems is $N$ units. If a magic gem is chosen and split, it takes $M$ units of space (since it is split into $M$ gems); if a magic gem is not split, it takes $1$ unit.

How many different configurations of the resulting set of gems can Reziba have, such that the total amount of space taken is $N$ units? Print the answer modulo $1000000007$ ($10^9+7$). Two configurations are considered different if the number of magic gems Reziba takes to form them differs, or the indices of gems Reziba has to split differ.


-----Input-----

The input contains a single line consisting of $2$ integers $N$ and $M$ ($1 \le N \le 10^{18}$, $2 \le M \le 100$).


-----Output-----

Print one integer, the total number of configurations of the resulting set of gems, given that the total amount of space taken is $N$ units. Print the answer modulo $1000000007$ ($10^9+7$).


-----Examples-----
Input
4 2

Output
5

Input
3 2

Output
3



-----Note-----

In the first example each magic gem can split into $2$ normal gems, and we know that the total amount of gems are $4$.

Let $1$ denote a magic gem, and $0$ denote a normal gem.

The total configurations you can have is:   $1 1 1 1$ (None of the gems split);  $0 0 1 1$ (First magic gem splits into $2$ normal gems);  $1 0 0 1$ (Second magic gem splits into $2$ normal gems);  $1 1 0 0$ (Third magic gem splits into $2$ normal gems);  $0 0 0 0$ (First and second magic gems split into total $4$ normal gems). 

Hence, answer is $5$.

Difficulty: interview

Starter code:

Solutions:
import sys

MOD = 10**9+7

# Polymod
def polymod(P,Q):
    assert(Q[-1]==1)
    n = len(Q)
    while len(P)>=n:
        p = P[-1]
        for i in range(n):
            P[-i-1] -= p*Q[-i-1]
        assert(P[-1]==0)
        P.pop()
    return P

def polyprod(P,Q):
    n = len(P)
    m = len(Q)
    W = [0]*(n+m-1)
    for i in range(n):
        for j in range(m):
            W[i+j]+=P[i]*Q[j]
    return [w%MOD for w in W]

# Calc A^m * B 
def power(A,B,m,mult):
    if m == 0:
        return B
    while m>1:
        if m%2==1:
            B = mult(A,B)
        A = mult(A,A)
        m//=2
    return mult(A,B)
    
def calc_nth_term(init,linear_coeff,n):
    def mult(A,B):
        return polymod(polyprod(A,B),linear_coeff)
    
    ans = power([0,1],[1],n,mult)
    return sum(ans[i]*init[i] for i in range(len(ans)))


n,m = [int(x) for x in input().split()]

linear_rec = [0]*(m+1)
linear_rec[0] = -1
linear_rec[m-1] = -1
linear_rec[m] = 1

print(calc_nth_term([1]*m,linear_rec,n)%MOD)


import sys

MOD = 10**9+7

# Polymod
def polymod(P,Q):
    assert(Q[-1]==1)
    n = len(Q)
    while len(P)>=n:
        p = P[-1]
        for i in range(n):
            P[-i-1] -= p*Q[-i-1]
        assert(P[-1]==0)
        P.pop()
    return P

def polyprod(P,Q):
    n = len(P)
    m = len(Q)
    W = [0]*(n+m-1)
    for i in range(n):
        for j in range(m):
            W[i+j]+=P[i]*Q[j]
    return [w%MOD for w in W]

# Calc A^m * B 
def power(A,B,m,mult):
    if m == 0:
        return B
    while m>1:
        if m%2==1:
            B = mult(A,B)
        A = mult(A,A)
        m//=2
    return mult(A,B)
    
def calc_nth_term(init,linear_coeff,n):
    def mult(A,B):
        return polymod(polyprod(A,B),linear_coeff)
    
    ans = power([0,1],[1],n,mult)
    return sum(ans[i]*init[i] for i in range(len(ans)))


n,m = [int(x) for x in input().split()]

linear_rec = [0]*(m+1)
linear_rec[0] = -1
linear_rec[m-1] = -1
linear_rec[m] = 1

print(calc_nth_term([1]*m,linear_rec,n)%MOD)