#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#define INF 1000000000

using namespace std;
typedef long long ll;

const ll MOD = 1000000000;

const int MAXN = 10010;
ll C[2][MAXN];

int main(void) {
    ll N, M;
    cin >> N >> M;
    ll n = N;
    n /= 1000;
    n /= M;
    N -= (n*1000) * M;
    N /= 1000;
    // M C Nを求める
    C[0][0] = 1;
    for (int n = 1; n <= M; n++) {
        int nn = n % 2;
        for (int r = 0; r < MAXN; r++) {
            C[nn][r] = (C[1-nn][r-1] + C[1-nn][r]) % MOD;
        }
    }
    cout << C[M%2][N] << endl;
    return 0;
}