#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	ll n;
	int m, r;
	cin >> n >> m;
	r = n / 1000 % m;

	ll ans = 1;
	int mr = m - r;
	while (m >mr) {
		ans *= m--;
		while (r>0&&ans%r == 0) {
			ans /= r--;
		}
		ans %= 1000000000;
	}


	cout << ans << endl;



	return 0;
}