#!/usr/bin/env python
# -*- coding: utf-8 -*-
from math import factorial
c = lambda y, x: factorial(y) // factorial(x) // factorial(y - x)

n = int(input())
m = int(input())
print(c(m, n // 1000 % m) % 10**9)