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$.

Source: codeforces | Difficulty: HARD
Tags: Matrices

Dynamic programming

Mathematics


Solutions:
import sys
from math import trunc
MOD = 10 ** 9 + 7
MODF = float(MOD)
MODF_inv = 1.0 / MODF

def modder(a):
	return a - MODF * trunc(a * MODF_inv)
SHRT = float(1 << 16)
SHRT_inv = 1.0 / SHRT

def mod_prod(a, b, c=0):
	a1 = trunc(a * SHRT_inv)
	a2 = a - SHRT * a1
	b1 = modder(b * SHRT)
	b2 = b
	return modder(a2 * b2 + a1 * b1 + c)

def mult(A, B):
	(n, m) = (len(A[0]), len(B))
	C = [[0.0] * n for _ in range(m)]
	for (j, B_j) in enumerate(B):
		C_j = C[j]
		for (k, A_k) in enumerate(A):
			Bkj = B_j[k]
			for (i, Aik) in enumerate(A_k):
				C_j[i] = mod_prod(Aik, Bkj, C_j[i])
	return C

def power(A, B, n, mult_func):
	if n == 0:
		return B
	while n > 1:
		if n % 2 == 1:
			B = mult_func(A, B)
		A = mult_func(A, A)
		n //= 2
	return mult_func(A, B)
(n, m) = [int(x) for x in input().split()]
mat = [[0.0] * m for _ in range(m)]
mat[0][0] = 1.0
mat[-1][0] = 1.0
for i in range(m - 1):
	mat[i][i + 1] = 1.0
vec = [[1.0] * m]
vec = power(mat, vec, n, mult)
print(int(vec[0][-1]))


import math
MOD = 10 ** 9 + 7
FMOD = float(MOD)
SHRT = float(2 ** 16)
fmod = lambda x: x - FMOD * math.trunc(x / FMOD)
mod_prod = lambda a, b, c=0: fmod(math.trunc(a / SHRT) * fmod(b * SHRT) + (a - SHRT * math.trunc(a / SHRT)) * b + c)

def mult(A, B):
	(n, p) = (len(A), len(B[0]))
	float_prec = 7881299347898367.0
	B = [[Bij - SHRT * math.trunc(Bij / SHRT) - 1j * math.trunc(Bij / SHRT) for Bij in Bi] for Bi in B]
	C = [[0.0] * p for _ in range(n)]
	for (i, Ai) in enumerate(A):
		Ci = C[i]
		for (j, Bj) in enumerate(B):
			Aij = Ai[j] + 1j * fmod(Ai[j] * SHRT)
			for (k, Bjk) in enumerate(Bj):
				Ci[k] += (Aij * Bjk).real
		for j in range(p):
			Ci[j] = fmod(Ci[j])
	return C

def power(A, B, m):
	while m > 0:
		if m % 2 == 1:
			B = mult(B, A)
		A = mult(A, A)
		m //= 2
	return B
(n, m) = [int(x) for x in input().split()]
mapper = [[0.0] * m for _ in range(m)]
mapper[0][0] = 1.0
mapper[-1][0] = 1.0
for i in range(m - 1):
	mapper[i][i + 1] = 1.0
vec = [[1.0] * m]
vec = power(mapper, vec, n)
print(int(vec[0][-1]))


import sys
from math import trunc
MOD = 10 ** 9 + 7
MODF = float(MOD)
small = float(2 ** 16)

def modder(x):
	return x - MODF * trunc(x / MODF)

def prod(a, b, c=0):
	return modder(c + trunc(a / small) * modder(b * small) + (a - small * trunc(a / small)) * b)

def mult(A, B):
	(n, m) = (len(A[0]), len(B))
	A = [[Aij - small * trunc(Aij / small) - 1j * trunc(Aij / small) for Aij in A_j] for A_j in A]
	C = [[0.0] * n for _ in range(m)]
	for (j, B_j) in enumerate(B):
		C_j = C[j]
		for (k, A_k) in enumerate(A):
			Bkj = B_j[k] + 1j * modder(B_j[k] * small)
			for (i, Aik) in enumerate(A_k):
				C_j[i] += (Aik * Bkj).real
		for i in range(n):
			C_j[i] = modder(C_j[i])
	return C
(n, m) = [int(x) for x in input().split()]
mapper = [[0.0] * m for _ in range(m)]
mapper[0][0] = 1.0
mapper[-1][0] = 1.0
for i in range(m - 1):
	mapper[i][i + 1] = 1.0

def power(A, B, m):
	n = len(A)
	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)
vec = [[1.0] * m]
vec = power(mapper, vec, n)
print(int(vec[0][-1]))


import sys
MOD = 10 ** 9 + 7

def mult(A, B):
	n = len(A)
	C = []
	for x in range(n):
		c = [0] * n
		for z in range(n):
			b = B[x][z]
			a = A[z]
			for y in range(n):
				c[y] += a[y] * b
		C.append(c)
	for x in range(n):
		c = C[x]
		for y in range(n):
			c[y] %= MOD
	return C

def vecmult(A, B):
	n = len(A)
	C = [0] * n
	for z in range(n):
		b = B[z]
		a = A[z]
		for y in range(n):
			C[y] += a[y] * b
	return [c % MOD for c in C]
(n, m) = [int(x) for x in input().split()]
mapper = [[0] * m for _ in range(m)]
mapper[0][0] = 1
mapper[-1][0] = 1
for i in range(m - 1):
	mapper[i][i + 1] = 1

def power(A, B, m):
	n = len(A)
	if m == 0:
		return B
	while m > 1:
		if m % 2 == 1:
			B = vecmult(A, B)
		A = mult(A, A)
		m //= 2
	return vecmult(A, B)
vec = [1] * m
vec = power(mapper, vec, n)
print(vec[-1] % MOD)


import sys
MOD = 10 ** 9 + 7
double_prec = float(2 * 10 ** 5 * MOD)
MODF = float(MOD)

def mult(A, B):
	n = len(A)
	cutmask = 2 ** 16 - 1
	C = [[0] * n for _ in range(n)]
	buffer = [0.0] * n
	A = [[(aa & cutmask) + 1j * (aa >> 16) for aa in a] for a in A]
	for x in range(n):
		b = B[x]
		for z in range(n):
			a = A[z]
			bb = b[z] + 1j * ((b[z] << 16) % MOD)
			for y in range(n):
				buffer[y] += a[y].real * bb.real + a[y].imag * bb.imag
		c = C[x]
		for y in range(n):
			c[y] = int(buffer[y] % MODF)
			buffer[y] = 0.0
	return C

def vecmult(A, B):
	n = len(A)
	C = [0] * n
	for z in range(n):
		b = B[z]
		a = A[z]
		for y in range(n):
			C[y] += a[y] * b
	return [c % MOD for c in C]
(n, m) = [int(x) for x in input().split()]
mapper = [[0] * m for _ in range(m)]
mapper[0][0] = 1
mapper[-1][0] = 1
for i in range(m - 1):
	mapper[i][i + 1] = 1

def power(A, B, m):
	n = len(A)
	if m == 0:
		return B
	while m > 40:
		if m % 2 == 1:
			B = vecmult(A, B)
		A = mult(A, A)
		m //= 2
	while m > 0:
		B = vecmult(A, B)
		m -= 1
	return B
vec = [1] * m
vec = power(mapper, vec, n)
print(vec[-1] % MOD)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def mat_mul_mod(A, B, mod):
	(n, p) = (len(A), len(B[0]))
	fmod = float(mod)
	float_prec = float(1 << 51)
	B = [[(Bij & (1 << 16) - 1) - 1j * (Bij >> 16) for Bij in Bi] for Bi in B]
	C = [[0] * p for _ in range(n)]
	for (i, Ai) in enumerate(A):
		row = [0.0] * p
		for (j, Bj) in enumerate(B):
			Aij = Ai[j] + 1j * (Ai[j] * 65536.0 % mod)
			for (k, Bjk) in enumerate(Bj):
				row[k] += (Aij * Bjk).real
				if row[k] > float_prec:
					row[k] %= fmod
		C[i] = [int(r % fmod) for r in row]
	return C

def main():
	MOD = 10 ** 9 + 7
	(n, m) = map(int, input().split())
	mat = [[0] * m for _ in range(m)]
	mat[0][0] = 1
	mat[0][-1] = 1
	for i in range(m - 1):
		mat[i + 1][i] = 1
	vec = [1] * m
	for i in bin(n)[:1:-1]:
		if i == '1':
			vec = [sum((a * b for (a, b) in zip(row, vec))) % MOD for row in mat]
		mat = mat_mul_mod(mat, mat, MOD)
	print(int(vec[-1]))
main()


import sys
MOD = 10 ** 9 + 7
double_prec = float(2 ** 51)
MODF = float(MOD)

def mult(A, B):
	n = len(A)
	m = len(B[0])
	C = [[0] * n for _ in range(m)]
	A = [[(Aij & 2 ** 16 - 1) - 1j * (Aij >> 16) for Aij in A_j] for A_j in A]
	for (j, B_j) in enumerate(B):
		buffer = [0.0] * n
		for (k, A_k) in enumerate(A):
			Bkj = B_j[k] + 1j * ((B_j[k] << 16) % MOD)
			for (i, Aik) in enumerate(A_k):
				buffer[i] += (Aik * Bkj).real
		C_j = C[j]
		for (i, b) in enumerate(buffer):
			C_j[i] = int(b % MODF)
	return C

def vecmult(A, B):
	n = len(A)
	C = [0] * n
	for (k, A_k) in enumerate(A):
		Bk = B[k]
		for (i, Aik) in enumerate(A_k):
			C[i] += Aik * Bk
	for i in range(n):
		C[i] %= MOD
	return C
(n, m) = [int(x) for x in input().split()]
mapper = [[0] * m for _ in range(m)]
mapper[0][0] = 1
mapper[-1][0] = 1
for i in range(m - 1):
	mapper[i][i + 1] = 1

def power(A, B, m):
	n = len(A)
	if m == 0:
		return B
	while m > 16:
		if m % 2 == 1:
			B = vecmult(A, B)
		A = mult(A, A)
		m //= 2
	while m > 0:
		B = vecmult(A, B)
		m -= 1
	return B
vec = [1] * m
vec = power(mapper, vec, n)
print(vec[-1])


import itertools
import os
import sys
from atexit import register
from io import BytesIO

class dict(dict):

	def items(self):
		return dict.iteritems(self)

	def keys(self):
		return dict.iterkeys(self)

	def values(self):
		return dict.itervalues(self)

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda : os.write(1, sys.stdout.getvalue()))
input = lambda : sys.stdin.readline().rstrip(b'\r\n')

def mat_mul_mod(A, B, mod):
	(n, p) = (len(A), len(B[0]))
	fmod = float(mod)
	float_prec = float(2 ** 51 - 1)
	B = [[(Bij & (1 << 16) - 1) - 1j * (Bij >> 16) for Bij in Bi] for Bi in B]
	C = []
	for Ai in A:
		row = [0.0] * p
		for (j, Bj) in enumerate(B):
			Aij = Ai[j] + 1j * ((Ai[j] << 16) % mod)
			for (k, Bjk) in enumerate(Bj):
				row[k] += (Aij * Bjk).real
				if row[k] > float_prec:
					row[k] %= fmod
		C.append([int(r % fmod) for r in row])
	return C
MOD = 10 ** 9 + 7

def main():
	(n, m) = map(int, input().split())
	mat = [[0] * m for _ in range(m)]
	mat[0][0] = 1
	mat[0][-1] = 1
	for i in range(m - 1):
		mat[i + 1][i] = 1
	vec = [1] * m
	while n > 0:
		if n & 1:
			vec = [sum((a * b for (a, b) in zip(row, vec))) % MOD for row in mat]
		mat = mat_mul_mod(mat, mat, MOD)
		n //= 2
	sys.stdout.write(str(vec[-1]).encode())
main()


import sys
from math import trunc
MOD = 10 ** 9 + 7
MODF = float(MOD)
small = 1.0 * 2 ** 16

def modder(x):
	return x - MODF * trunc(x / MODF)

def prod(a, b, c):
	abig = trunc(a / small)
	return modder(c + abig * modder(b * small) + (a - small * abig) * b)

def mult(A, B):
	n = len(A)
	m = len(B[0])
	C = [[0.0] * n for _ in range(m)]
	A = [[(Aij, modder(Aij * small)) for Aij in A_j] for A_j in A]
	for (j, B_j) in enumerate(B):
		buffer = C[j]
		for (k, A_k) in enumerate(A):
			Bkjbig = trunc(B_j[k] / small)
			Bkjsmall = B_j[k] - small * Bkjbig
			for (i, Aik) in enumerate(A_k):
				buffer[i] += Aik[0] * Bkjsmall + Aik[1] * Bkjbig
		for (i, b) in enumerate(buffer):
			buffer[i] = modder(b)
	return C

def vecmult(A, B):
	n = len(A)
	C = [0.0] * n
	for (k, A_k) in enumerate(A):
		Bk = B[k]
		for (i, Aik) in enumerate(A_k):
			C[i] = prod(Aik, Bk, C[i])
	return C
(n, m) = [int(x) for x in input().split()]
mapper = [[0.0] * m for _ in range(m)]
mapper[0][0] = 1.0
mapper[-1][0] = 1.0
for i in range(m - 1):
	mapper[i][i + 1] = 1.0

def power(A, B, m):
	n = len(A)
	if m == 0:
		return B
	while m > 50:
		if m % 2 == 1:
			B = vecmult(A, B)
		A = mult(A, A)
		m //= 2
	while m > 0:
		B = vecmult(A, B)
		m -= 1
	return B
vec = [1.0] * m
vec = power(mapper, vec, n)
print(int(vec[-1]) % MOD)


import math
FMOD = 1000000007.0
PREC = 7881299347898367.0
SHRT = 65536.0
fmod = lambda x: x - FMOD * math.trunc(x / FMOD)
mod_prod = lambda a, b, c=0: fmod(math.trunc(a / SHRT) * fmod(b * SHRT) + (a - SHRT * math.trunc(a / SHRT)) * b + c)

def mult(A, B):
	(n, p) = (len(A), len(B[0]))
	B = [[Bij - SHRT * math.trunc(Bij / SHRT) - 1j * math.trunc(Bij / SHRT) for Bij in Bi] for Bi in B]
	C = [[0.0] * p for _ in range(n)]
	for (i, Ai) in enumerate(A):
		Ci = C[i]
		for (j, Bj) in enumerate(B):
			Aij = Ai[j] + 1j * fmod(Ai[j] * SHRT)
			for (k, Bjk) in enumerate(Bj):
				Ci[k] += (Aij * Bjk).real
				if Ci[k] > PREC:
					Ci[k] = fmod(Ci[k])
		C[i] = [fmod(Cij) for Cij in Ci]
	return C

def power(A, B, m):
	while m > 0:
		if m % 2 == 1:
			B = mult(B, A)
		A = mult(A, A)
		m //= 2
	return B
(n, m) = [int(x) for x in input().split()]
mapper = [[0.0] * m for _ in range(m)]
(mapper[0][0], mapper[-1][0]) = (1.0, 1.0)
for i in range(m - 1):
	mapper[i][i + 1] = 1.0
vec = [[1.0] * m]
vec = power(mapper, vec, n)
print(int(vec[0][-1] % FMOD))


import sys
MOD = 10 ** 9 + 7
MODF = 1.0 * MOD
MODF_inv = 1.0 / MODF
SHRT = 1.0 * (1 << 16)
SHRT_inv = 1.0 / SHRT
MAGIC = float(2 ** 52 + 2 ** 51)
fround = lambda x: x + MAGIC - MAGIC
modder = lambda a: a - MODF * fround(a * MODF_inv)
mod_prod = lambda a, b, c=0.0: modder((b - SHRT * fround(SHRT_inv * b)) * a + c + modder(a * SHRT) * fround(b * SHRT_inv))

def mult(A, B):
	(n, m) = (len(A[0]), len(B))
	C = [[0.0] * n for _ in range(m)]
	for (j, B_j) in enumerate(B):
		C_j = C[j]
		for (k, A_k) in enumerate(A):
			Bkj = B_j[k]
			for (i, Aik) in enumerate(A_k):
				C_j[i] = mod_prod(Aik, Bkj, C_j[i])
	return C

def power(A, B, n, mult_func):
	if n == 0:
		return B
	while n > 1:
		if n % 2 == 1:
			B = mult_func(A, B)
		A = mult_func(A, A)
		n //= 2
	return mult_func(A, B)
(n, m) = [int(x) for x in input().split()]
mat = [[0.0] * m for _ in range(m)]
mat[0][0] = 1.0
mat[-1][0] = 1.0
for i in range(m - 1):
	mat[i][i + 1] = 1.0
vec = [[1.0] * m]
vec = power(mat, vec, n, mult)
print(int(vec[0][-1]) % MOD)


def _solve(n, m, memo):
	if n <= 0:
		return 0
	if n < m:
		return 1
	if n == 1:
		return 2
	if (n, m) in memo:
		return memo[n, m]
	out = 0
	mid = n // 2
	out = (out + _solve(mid, m, memo) * _solve(n - mid, m, memo)) % 1000000007
	for i in range(1, m):
		if mid - i < 0 or n - mid + i - m < 0:
			continue
		n1 = 1 if mid - i == 0 else _solve(mid - i, m, memo)
		n2 = 1 if n - mid + i - m == 0 else _solve(n - mid + i - m, m, memo)
		out = (out + n1 * n2) % 1000000007
	memo[n, m] = out
	return out

def solve(n, m):
	return _solve(n, m, {})

def main():
	from sys import stdin
	(n, m) = list(map(int, stdin.readline().strip().split()))
	out = solve(n, m)
	print('{}'.format(out))
main()


import sys
from math import trunc
MOD = 10 ** 9 + 7
MODF = float(MOD)
FLOAT_PREC = float(2 ** 52)

def modder(x):
	return x - MODF * trunc(x / MODF)
SHRT = float(2 ** 16)

def prod(a, b, c=0):
	return modder(c + trunc(a / SHRT) * modder(b * SHRT) + (a - SHRT * trunc(a / SHRT)) * b)

def mult(A, B):
	(n, m) = (len(A[0]), len(B))
	C = [[0.0] * n for _ in range(m)]
	for (j, B_j) in enumerate(B):
		C_j = C[j]
		for (k, A_k) in enumerate(A):
			Bkj = B_j[k]
			for (i, Aik) in enumerate(A_k):
				C_j[i] = prod(Aik, Bkj, C_j[i])
	return C

def power(A, B, n, mult_func):
	if n == 0:
		return B
	while n > 1:
		if n % 2 == 1:
			B = mult_func(A, B)
		A = mult_func(A, A)
		n //= 2
	return mult_func(A, B)
(n, m) = [int(x) for x in input().split()]
mat = [[0.0] * m for _ in range(m)]
mat[0][0] = 1.0
mat[-1][0] = 1.0
for i in range(m - 1):
	mat[i][i + 1] = 1.0
vec = [[1.0] * m]
vec = power(mat, vec, n, mult)
print(int(vec[0][-1]))


import sys
MOD = 10 ** 9 + 7

def mult(A, B):
	n = len(A)
	cut = 2 ** 16
	cutmask = cut - 1
	C = [[0.0] * n for _ in range(n)]
	tmp1 = [[float(aa & cutmask) for aa in a] for a in A]
	tmp2 = [[float(aa >> 16) for aa in a] for a in A]
	for x in range(n):
		c = C[x]
		for z in range(n):
			b = float(B[x][z])
			a = tmp1[z]
			for y in range(n):
				c[y] += a[y] * b
			b = float((B[x][z] << 16) % MOD)
			a = tmp2[z]
			for y in range(n):
				c[y] += a[y] * b
		for y in range(n):
			c[y] = int(c[y]) % MOD
	return C

def vecmult(A, B):
	n = len(A)
	C = [0] * n
	for z in range(n):
		b = B[z]
		a = A[z]
		for y in range(n):
			C[y] += a[y] * b
	return [c % MOD for c in C]
(n, m) = [int(x) for x in input().split()]
mapper = [[0] * m for _ in range(m)]
mapper[0][0] = 1
mapper[-1][0] = 1
for i in range(m - 1):
	mapper[i][i + 1] = 1

def power(A, B, m):
	n = len(A)
	if m == 0:
		return B
	while m > 8:
		if m % 2 == 1:
			B = vecmult(A, B)
		A = mult(A, A)
		m //= 2
	while m > 0:
		B = vecmult(A, B)
		m -= 1
	return B
vec = [1] * m
vec = power(mapper, vec, n)
print(vec[-1] % MOD)


import math
FMOD = 1000000007.0
PREC = 7881299347898367.0
SHRT = 65536.0
fmod = lambda x: x - FMOD * math.trunc(x / FMOD)
mod_prod = lambda a, b, c=0: fmod(math.trunc(a / SHRT) * fmod(b * SHRT) + (a - SHRT * math.trunc(a / SHRT)) * b + c)

def mult(A, B):
	(n, p) = (len(A), len(B[0]))
	B = [[Bij - SHRT * math.trunc(Bij / SHRT) - 1j * math.trunc(Bij / SHRT) for Bij in Bi] for Bi in B]
	C = [[0.0] * p for _ in range(n)]
	for (i, Ai) in enumerate(A):
		Ci = C[i]
		for (j, Bj) in enumerate(B):
			Aij = Ai[j] + 1j * fmod(Ai[j] * SHRT)
			for (k, Bjk) in enumerate(Bj):
				Ci[k] += (Aij * Bjk).real
				if Ci[k] > PREC:
					Ci[k] = fmod(Ci[k])
		C[i] = [fmod(Cij) for Cij in Ci]
	return C

def power(A, B, m):
	while m > 0:
		if m % 2 == 1:
			B = mult(B, A)
		A = mult(A, A)
		m //= 2
	return B
(N, M) = map(int, input().split())
if M > N:
	print(1)
	exit()
MOD_NUM = 10 ** 9 + 7
A = [[0] * (M + 1) for _ in range(M + 1)]
A[0][0] += 1
A[0][M - 1] += 1
for i in range(1, M + 1):
	A[i][i - 1] = 1
I = [[0] * (1 + M) for _ in range(1 + M)]
for i in range(1 + M):
	I[i][i] = 1
A = power(A, I, N - M)
x = [1] * (1 + M)
x[0] += 1
ans = 0
for j in range(1 + M):
	ans += A[0][j] * x[j]
	ans %= MOD_NUM
print(int(ans))


import sys
MOD = 10 ** 9 + 7

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]

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)