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) / F(X) / F(M - X) % 1000000000);
        }

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