#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int mod = 1000000000;

int main() {
	long long n, m;

	cin >> n >> m;

	long long atari = (n - (n / 1000 / m) * 1000 * m) / 1000;

	// cout << atari << endl;

	long long ans;
	if (n == 0) {
		ans = 0;
	} else{
		ans = 1;
		int small = min(atari, m - atari);
		vector<bool> check(small + 1, false);
		//mCatari
		for (int i = 0; i < small; i++) {
			ans *= (m - i);

			for (int j = small; j > 1; j--) {
				if (!check[j] && ans % j == 0) {
					check[j] = true;
					ans /= j;
				}
			}
		}
	}

	ans %= mod;
	cout << ans << endl;
	return 0;
}