SPBINARY2

#include <set>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <string>
#include <climits>
#include <stack>
#include <queue>
using namespace std;
const int N = 1e6, mod = 1e9;
long long f[N+1], n, k, s = 0;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    f[0] = 1;
    for (int i = 1; i <= k; ++ i)
    {
        f[i] = (f[i-1] * 2) % mod;
        s = (s + f[i]) % mod;
    }
    for (int i = k + 1; i <= n; ++ i)
    {
        f[i] = s;
        s = (s + f[i] - f[i-k] + mod) % mod;
    }
    cout << f[n];
}