传统题 1000ms 256MiB

小学生的复仇2

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

小学生ikun最近学了算法,变得嚣张起来。他刚掌握了如何用 O(n)O(\sqrt{n}) 的复杂度求出一个数 nn 的所有因子及个数,便到处炫耀(因为还有大部分大学生如cypress都还在用 O(n)O(n) 复杂度从1遍历到 nn 来计算因子)。

//c++代码中的某函数
vector<int>get_factors(int x){
    vector<int>ans;
    for(int i=1;i<=x/i;i++){
        if(x%i==0){
            ans.push_back(i);
            if(i!=x/i)ans.push_back(x/i); 
        }
    }
    sort(ans.begin(),ans.end());
    return ans;
}

为了给他点颜色看看,cypress的朋友取舍决定给他一个更具挑战性的任务,计算一个大数中所有因子的数量。

但小学生ikun不甘示弱,决定复仇。请你帮帮他

给定两个整数n,mn,m,计算C(n,m)C(n,m)的因子个数。

tips:C(n,m)C(n,m)表示组合数,也就是从 nn 个元素中选取 mm 个元素的不同组合的总数。它也可以通过组合公式计算:C(n,m)C(n,m)=n!m!(n−m)!\frac{n!}{m!(n-m)!} ​

Input Format

第一行包含两个整数 n,mn,m (1≤m≤n≤1061 \leq m \leq n \leq 10^6)

Output Format

输出 C(n,m)C(n,m) 的因子个数。答案可能很大,请对109+710^9+7取模。

Sample

输入 #1

1 1

输出 #1

1

输入 #2

2 1

输出 #2

2

输入 #3

4 2

输出 #3

4

Hint

样例1: C(1,1)=1C(1,1)=1 ,因子包含1个: 1

样例2: C(2,1)=2C(2,1)=2 ,因子包含2个: 1,2

样例3: C(4,2)=6C(4,2)=6 ,因子包含4个: 1,2,3,6

线下赛_test

未参加
状态
已结束
规则
XCPC
题目
10
开始于
2024-12-5 21:58
结束于
2024-12-6 21:58
持续时间
24 小时
主持人
参赛人数
1