import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); int m = sc.nextInt(); long[][] comb = new long[m + 1][m + 1]; for (int i = 0; i <= m; i++) { for (int j = 0; j <= i; j++) { if (j ==0 || j == i) { comb[i][j] = 1; } else { comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % 1000000000; } } } int count = (int)((n / 1000) % m); System.out.println(comb[m][count]); } }