#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1e9;
int MOD = 1e9;
int dp[10010][10010];
main(){
    ll N,M;
    cin >> N >> M;
    dp[0][0] = 1;
    for(int i = 0;i <= M;i++){
        for(int j = 0;j <= i;j++){
            dp[i+1][j] = (dp[i+1][j] + dp[i][j])%MOD;
            dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j])%MOD;
        }
    }
    cout << dp[M][N/1000%M] << endl;
}