using System;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Collections;
using System.Collections.Generic;

public class Program {
    static BigInteger ncm(long n, long m) {
        BigInteger r = 1;
        for (long i = 1; i < m+1; ++i, --n) {
            r *= n;
            r /= i;
        }
        return r;
    }
    
    static void Main(string[] args) {
        long N = long.Parse(Console.ReadLine());
        long M = long.Parse(Console.ReadLine());
        long m = (N % (M * 1000)) / 1000;
        Console.WriteLine(ncm(M, m) % 1000000000);
    }
}