3390: 小 M 求和
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：外部导入
提交：1
解决：1
题目描述
小 W 顺利地完成了拼图，
该他给小 M 出题啦。
小 W 定义“！”运算符：
1、 N!k = N!(k-1) * (N-1)!k (N> 0 aNd k > 0)
2、 N!k = 1 (N = 0)
3、 N!k = N (k = 0)
现在小 W 告诉小 M N 和 k，小 M 需要说出 N!k 的不同约数个数。为了降低难度，答案对 1000000009 取模就好了。
输入
第一行两个整数 N,M。
输出
一行一个整数，为答案。
样例输入 复制
3 1样例输出 复制
4提示
in
100 2
out
321266186
对于 30%的数据：N<=10,k<=10
对于 100%的数据：N<=1000,k<=100