#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000000

long Combination(int n, long r);

int main(void) {
    
    long long N;
    int M;
    long long a, x; // available, X
    long j, s; // jambo, solve
    scanf("%lld%d", &N, &M);
    a = N / 1000;
    x = a / M;
    j = a - (x*M);
    s = 1;
    if (j) {
        s = Combination(M, j);
    }
    printf("%ld\n", s);
    
    return EXIT_SUCCESS;
}

long Combination(int n, long r) {
    long paskal[10000] = {0};
    long s1, s2;
    paskal[0] = 1;
    for (int i = 1; i <= n+1; i++) {
        s1 = 0;
        s2 = paskal[0];
        for (int j = 0; j < i; j++) {
            paskal[j] = (s1 + s2) % MOD;
            s1 = s2;
            s2 = paskal[j+1];
        }
    }
    return paskal[r];
}