import std.stdio, std.conv, std.math, std.string, std.range, std.array,
       std.algorithm;

enum MOD = 10^^9;

//return ULL nCr {(n,r)|n,r ∈ (int)}
ulong combination(int n, int r){
	if (r == 0) return 1;
	if (r > n/2) return combination(n,n-r);
	ulong ret=1;
	for (int i = 1; i <= r; ++i)
		ret = (ret*(n-i+1)/i) % MOD;
	return ret;
}

void main(){
  immutable N = readln().strip().to!long();
  immutable M = readln().strip().to!int();

  M.combination(((N/1000)%M).to!int).writeln();
}