팩토리얼과 점화식

$S(n, k)$를 다음과 같이 정의한다.

• $n = 0$이면 $S(n, k) = 1$
• $k = 0$이면 $S(n, k) = n$
• 나머지 경우에는 $S(n, k) = S(n, k-1) \times S(n-1, k)$

규칙은 위에서부터 차례로 적용한다.

예를 들어 $S(7, 1) = 7!$이고, $S(5, 3) = S(5, 2) \times S(4, 3) = S(5, 1) \times S(4, 2) \times S(4, 3)$이다.

$N$과 $K$가 주어질 때 $S(N, K)$의 약수의 개수를 구한다.

첫째 줄에 $N$과 $K$가 공백을 사이에 두고 주어진다. ($1 \le N \le 1000$, $1 \le K \le 100$)

첫째 줄에 $S(N, K)$의 약수의 개수를 1,000,000,009로 나눈 나머지를 출력한다.