import std.stdio, std.conv, std.math, std.string, std.range, std.array,
       std.algorithm, std.bigint;

enum MOD = 10^^9;

//return ULL nCr {(n,r)|n,r ∈ (int)}
BigInt combination(int n, int r){
  if (r == 0) return BigInt(1);
  if (r > n/2) return combination(n,n-r);
  BigInt ret=1;
  for (int i = 1; i <= r; ++i)
    ret *= (n-i+1)/i;
  return ret;
}

void main(){
  immutable N = readln().strip().to!long();
  immutable M = readln().strip().to!int();

  (M.combination(((N/1000)%M).to!int) % MOD).writeln();
}