#!/usr/bin/env python
#coding:utf8


def read():
    return input(), input()


def work((N, M)):
    toPay  = N / M / 1000 * 1000
    remain = N - toPay * M
    K = remain / 1000

    # M から K 個を選ぶ組み合わせの数
    ans = 1
    for i in range(M - K + 1, M + 1):
        ans *= i
    for i in range(1, K + 1):
        ans /= i
    print ans % 1000000000
    

if __name__ == "__main__":
    work(read())