#include #include #include #include #include #include #include #include #define REP(i,k,n) for(int i=k;i P; ll memo[10001][10001]; ll nCr(ll n,ll r) { if(n < r) return 0; if(n == r) return 1; if(r == 1) return n; if(memo[n][r] != -1) return memo[n][r]; return memo[n][r] = (nCr(n-1,r)+nCr(n-1,r-1))%MOD; } int main() { ll n,m; cin >> n >> m; rep(i,10005) rep(j,10005) memo[i][j] = -1; n = n/1000; if(n % m == 0) { cout << 1 << endl; } else { int d = n % m; cout << nCr(m,d) << endl; } return 0; }