typedef long long ll;
typedef long double ld;

#include <bits/stdc++.h>
using namespace std;
// #define int long long

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// std::cout << *s.find_by_order(1) << std::endl; // 2


// 二項係数
const int MOD = 1000000000;
const int MAX_C = 10000;
long long Com[MAX_C][MAX_C];
void COMinit() {
    Com[0][0] = 1;
    for (int i = 1; i < MAX_C; ++i) Com[0][i] = 0;
    for (int i = 1; i < MAX_C; ++i) {
        Com[i][0] = 1;
        for (int j = 1; j < MAX_C; ++j) {
            Com[i][j] = (Com[i-1][j-1] + Com[i-1][j]) % MOD;
        }
    }
}
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return Com[n][k];
}


signed main(){
    // これがないと落ちることがある
    ios_base::sync_with_stdio(false);
    cin.tie(0);


    COMinit();
    ll n;
    cin >> n;
    ll m;
    cin >> m;
    n-=n%1000;
    n/=1000;

    cout << COM(m,n%m) << endl;
}