#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for(tint i=s;i<tint(n);i++)
#define forn(i, n) forsn(i, 0, n)
#define all(v) v.begin(), v.end()
#define NACHO ios_base::sync_with_stdio(0);cin.tie(NULL);

typedef long long tint;

const tint MOD = 1000000;

int main(){
    tint k, d; cin >> k >> d;
    queue<tint> q;
    tint sum = 1;
    ///1 1 2 4 8 16 31
    q.push(sum);
    forn(i, d-1){
        sum = (2*sum) % MOD;
        q.push(sum);
        if(q.size() > k){
            sum =  (sum-q.front()+MOD)%MOD;
            q.pop();
        }
    }
    cout << sum << endl;
}