using System;
using System.Numerics;

namespace No129_1 {
    public class Program {
        public static void Main(string[] args){
            var N = BigInteger.Parse(Console.ReadLine());
            var M = BigInteger.Parse(Console.ReadLine());
            var X = N / 1000 % M;

            Console.WriteLine(F(M, X) / F(M - X, 1) % 1000000000);
        }

        public static BigInteger F(BigInteger x, BigInteger y){
            BigInteger result = 1;
            for(BigInteger i = y + 1; i <= x; i++){
                result *= i;
            }
            return result;
        }
    }
}