package no129;

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	static final BigInteger MOD = new BigInteger("1000000000");
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long m = sc.nextInt();
		long k = (n - (n / m / 1000 * 1000) * m) / 1000;
		//m C k
		//System.out.println(m + "," + k);
		BigInteger ans = BigInteger.ONE;
		for(int i=1;i<=m;i++) {
			ans = ans.multiply(BigInteger.valueOf(i));
		}
		for(int i=1;i<=m-k;i++) {
			ans = ans.divide(BigInteger.valueOf(i));
		}
		for(int i=1;i<=k;i++) {
			ans = ans.divide(BigInteger.valueOf(i));
		}
		ans = ans.mod(MOD);
		System.out.println(ans);
	}

}