#!/usr/bin/env python
# -*- coding: utf-8 -*-

mod = 1000000000

def c(y, x):
    if y // 2 < x: x = y - x;
    t = 1
    for i in range(1, x + 1): t = t * (y + 1 - i) // i
    return t

n = int(input())
m = int(input())
print(c(m, n // 1000 % m) % mod)