3504.运算符

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;
}