#!/usr/bin/env python
# -*- coding: utf-8 -*-
from functools import reduce

mul = lambda x, y: x * y
def c(n, r):
    if r == 0 or n == r: return 1
    if r <= n - r: r = n - r
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(1, r + 1))

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