import sequtils,strutils
var
    N = stdin.readline.parseBiggestInt
    M = stdin.readline.parseBiggestInt
    c = (N div 1000) mod M
    memo : array[10000, array[10000, int64]]
for i in 0..M:
    for j in 0..i:
        if j == 0:
            memo[i][j] = 1
        else:
            memo[i][j] = (memo[i - 1][j] + memo[i - 1][j - 1]) mod 1_000_000_000
    #echo memo[i][0..i.int]
echo memo[M][c]