module main;
// https://w.atwiki.jp/uwicoder/pages/2118.html より
// 組み合わせ
import std;

immutable MOD = 10L ^^ 9;
long nCr(long n, long r)
{
	auto C = new long[][](n + 1, n + 1);
	foreach (i; 0 .. n + 1) {
		C[i][0] = 1;
		foreach (j; 1 .. i + 1) {
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
			if (C[i][j] > MOD)
				C[i][j] -= MOD;
		}
	}
	return C[n][r];
}

void main()
{
	// 入力
	auto N = readln.chomp.to!long;
	auto M = readln.chomp.to!long;
	// 答えの計算
	N /= 1000;
	N %= M;
	// 答えの出力
	writeln(nCr(M, N));
}