from collections import * import sys sys.setrecursionlimit(10 ** 6) int1 = lambda x: int(x) - 1 p2D = lambda x: print(*x, sep="\n") def II(): return int(sys.stdin.readline()) def MI(): return map(int, sys.stdin.readline().split()) def MF(): return map(float, sys.stdin.readline().split()) def LI(): return list(map(int, sys.stdin.readline().split())) def LF(): return list(map(float, sys.stdin.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] md = 10 ** 9 memo = {} def com(com_n, com_r): if com_n < com_r * 2: com_r = com_n - com_r if (com_n, com_r) in memo: return memo[(com_n, com_r)] if com_r == 1: return com_n if com_r == 0: return 1 res = memo[(com_n, com_r)] = (com(com_n - 1, com_r) + com(com_n - 1, com_r - 1)) % md return res def main(): n = II() m = II() n //= 1000 hit = n % m print(com(m, hit)) main()