import sequtils,strutils
var
    N = stdin.readline.parseBiggestInt
    M = stdin.readline.parseBiggestInt
    c = (N div 1000) mod M

proc combi(a, b:int64) : int64 =
    var b = b
    if b > a div 2:
        b = a - b
    var
        j = a
        p : int64 = 1
    for i in 1..b:
        p = ((p * j) div i) mod 1_000_000_000
        j -= 1
    return p

echo combi(M, c)