Time Limits: 1000 ms Memory Limits: 131072 KB

Description

鸡腿想到了一个很高（sha）明（bi）的运算符，那就是’!’，没错就是感叹号。他给了如下的定义：

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)

现在鸡腿告诉你n和k你能告诉他n!k的不同约数个数有多少个吗？只要对1,000,000,009取模就可以了哦！

Input

一行，输入两个正整数n，k。

Output

一行，输出一个整数表示答案。

Sample Input

1
2
3
4
输入1：
3 1
输入2：
100 2

Sample Output

1
2
3
4
输出1：
4
输出2：
321266186

Data Constraint

对于30%的数据0 <n ≤ 10, 0 <k ≤ 10；

对于100%的数据0 <n ≤ 1000, 0 <k ≤ 100。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 1005
int n, k, tot, p = 1e9 + 9;
int prm[N], book[N];
ll c[N], inv[N], t[N], ans = 1;
void pre_Prm() {
    for (int i = 2; i <= n; i++)
        if (!book[i]) {
            prm[++tot] = i;
            for (int j = 2; i * j <= n; j++)
                book[i * j] = 1;
        }
}
void pre_C() {
    inv[1] = 1; c[n] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (p - p / i) * inv[p % i] % p;
    for (int i = n - 1; i; i--)
        c[i] = (c[i + 1] * (n - i + k - 1) % p) * inv[n - i] % p;
}
int main() {
    scanf("%d%d", &n, &k);
    pre_Prm(); pre_C();
    for (int i = 1; i <= n; i++)
        for (int j = 1, k = i; j <= tot && k; j++) {
            int sum = 0;
            while (!(k % prm[j])) k /= prm[j], sum++;
            t[j] = (t[j] + sum * c[i] % p) % p;
        }
    for (int i = 1; i <= tot; i++)
        ans = ans * (t[i] + 1) % p;
    printf("%lld\n", ans);
    return 0;
}