Factorials and a recurrence

$S(n, k)$ is defined as follows.

• $S(n, k) = 1$ when $n = 0$
• $S(n, k) = n$ when $k = 0$
• $S(n, k) = S(n, k-1) \times S(n-1, k)$ otherwise

Apply the rules in the order listed.

For example, $S(7, 1) = 7!$, and $S(5, 3) = S(5, 2) \times S(4, 3) = S(5, 1) \times S(4, 2) \times S(4, 3)$.

Given $N$ and $K$, count the divisors of $S(N, K)$.

The first line contains $N$ and $K$ separated by a space. ($1 \le N \le 1000$, $1 \le K \le 100$)

Print the number of divisors of $S(N, K)$ modulo 1,000,000,009 on the first line.