#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1e9;
int MOD = 1e9+7;
ll combi(ll n, ll r){
    ll i,p=1;
    for(i=1;i<=r;i++)p=p*(n-i+1)/i % INF;
    return p;
}
main(){
    ll N,M;
    cin >> N >> M;
    cout << combi(M,N/1000%M) << endl;
}