/*
Author=UTKARSH
*/
/*
------------------------------------------------------------------------
░██╗░░░░░░░██╗░█████╗░██████╗░██╗░░██╗ ██╗░░██╗░█████╗░██████╗░██████╗░
░██║░░██╗░░██║██╔══██╗██╔══██╗██║░██╔╝ ██║░░██║██╔══██╗██╔══██╗██╔══██╗
░╚██╗████╗██╔╝██║░░██║██████╔╝█████═╝░ ███████║███████║██████╔╝██║░░██║
░░████╔═████║░██║░░██║██╔══██╗██╔═██╗░ ██╔══██║██╔══██║██╔══██╗██║░░██║
░░╚██╔╝░╚██╔╝░╚█████╔╝██║░░██║██║░╚██╗ ██║░░██║██║░░██║██║░░██║██████╔╝
░░░╚═╝░░░╚═╝░░░╚════╝░╚═╝░░╚═╝╚═╝░░╚═╝ ╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═════╝░
------------------------------------------------------------------------
*/
#include "bits/stdc++.h"
using namespace std;
typedef unsigned long long ull;
typedef long double lld;
typedef long long int ll;
typedef long double ld;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1e9
#define en "\n"
#define pb push_back
#define ppb pop_back
#define vi vector<ll>
#define vs vector<string>
#define pii pair<ll, ll>
#define mp make_pair
#define all(n) n.begin(), n.end()
#define ff first
#define ss second
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define sz(x) (int)((x).size())
#define mem1(a) memset(a,-1, sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define ppc __builtin_popcount
#define ppcll __builtin_popcountll
#define loop(i, a, b) for (int i = (a); i < (b); i++)
#define looprev(i, a, b) for (int i = (a); i >= (b); i--)
#define logarr(arr,a,b) for(int z=(a);z<(b);z++) cout<<(arr[z])<<" ";cout<<endl;
#define pt(a,b) cout<<a<<" "<<b<<"\n";
#ifndef ONLINE_JUDGE
#include "debug.hpp"
#else
#define debug(x)
#endif
template <typename T> T gcd(T a, T b) {if (b && a % b) return gcd(b, a % b); return b;}
template <typename T> T lcm(T a, T b) {return (a * (b / gcd(a, b)));}
template<typename T> void inline in(vector<T> &v, ll n) {
v.resize(n); for (ll i = 0; i < n; i++) cin >> v[i];
}
bool inline isVowel (char c) {
return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.ff>>a.ss;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.ff<<" "<<a.ss;return out;}
template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
const long long INF=4e17;
const long long N=1e6+5;
const int MOD=1e9;
ll a[N];
//Code here.....boom-->:):):):):)
void solve(){
ll n,k;cin>>n>>k;
ll sum=0;
loop(i,0,k){
a[i]=1;
sum=mod_add(sum,1,MOD);
}
loop(i,k,n+1){
assert(k<=i);
a[i]=sum;
sum=mod_sub(sum,a[i-k],MOD);
sum=mod_add(sum,a[i],MOD);
}
cout<<a[n]<<en;
}
int main()
{
FIO;
cout << setprecision(8) << fixed;
int t=1;
// cin>>t;
for(int tcase=1;tcase<=t;tcase++){
// cout<<"Case #"<<tcase<<": ";
solve();
}
return 0;
}