using System;

class Program
{
    static void Main()
    {
        long n = long.Parse(Console.ReadLine());
        long m = long.Parse(Console.ReadLine());

        long a = (n / 1000) % m;
        long ans = 1;

        for (long i = 1; i <= a; i++)
        {
            ans = ans * (m - i + 1) / i;
            ans %= 1000000000;
        }

        Console.WriteLine(ans);
    }
}