/SPBINARY2

              #include <iostream>
      using namespace std;
      
      #define LIM 1000000000
      
      int main() {
        int n, k;
        cin >> n >> k;
      
        int* f = new int[n + 1];
      
        f[0] = 2; // f[0] la mot so dac biet
        f[1] = 2;
      
        for (int i = 2; i <= n; i++) {
          if (i <= k) f[i] = (f[i - 1] * 2) % LIM;
          else
          {
            f[i] = (f[i - 1] * 2 - f[i - k - 1]) % LIM;
            if (f[i] < 0) f[i] += LIM;
          }
        }
      
        cout << f[n] << endl;
      
        return 0;
      }