shad.cpp

#include <iostream>
#include <vector>

typedef int64_t Int;

std::vector<bool> simple(500001, true);

void factor(std::vector<int64_t> &a, int n) {
    int64_t s = 0;
    for(int i=2; i<=n; i++) {
        s=0;
        if (simple[i]) {
            for(int t = i; t <= n; t *= i) {
                s += n/t;
            }
        }
        a[i] = s;
    }
    return;
}

Int solveFast(Int n, Int k) {
    std::vector<int64_t> f1(500001, 0), f2(500001, 0), f3(500001, 0);
    factor(f1, n);
    factor(f2, k);
    factor(f3, n-k);
    f1[1] = 1;
    for(int i=2; i<500001; i++) {
        if (f2[i] != 0) {
            f1[i] -= f2[i];
        }
        if (f3[i] != 0) {
            f1[i] -= f3[i];
        }
    }
    int64_t s=1;
    for(int i=2; i<500001; i++) {
        if (f1[i] != 0) {
            s = (s*(f1[i]+1)) % 1000000007;
        }
    }
    return s;
}

Int solveSlow(Int n, Int k) {
    if (k > n-k) return solveSlow(n, n-k);
    Int c = 1;
    for (Int i = 1; i <= k; ++i) {
        c *= (n - i + 1);
        c /= i;
    }
    Int sum = 1 + (c != 1);
    for (Int i = 2; i * i <= c; ++i) {
        Int j = c / i;
        if (i * j == c) {
            sum += 1 + (j != i);
        }
    }
    return sum;
}

void test(int N, int K) {
    std::cout << "start test!" << std::endl;
    for (int k = 0; k <= K; ++k) {
        for (int n = k; n <= N; ++n) {
            if (solveSlow(n, k) != solveFast(n, k)) {
                std::cout << "n = " << n << ", k = " << k
                    << ", slow = " << solveSlow(n, k) << ", fast = " << solveFast(n, k) << std::endl;
                throw 1;
            }
        }
    }
    std::cout << "ok" << std::endl;
    std::exit(0);
}

int main()
{
    simple[0] = simple[1] = false;
    for(int i = 2; i * i <= 500000; i++) {
        if (!simple[i]) continue;

        for (int j=i*i; j<=500000; j+=i) {
            simple[j] = false;
        }

    }
    // Тестирование
    // test(20, 20);

    int n, k;
    std::cin >> k >> n;
    std::cout << solveFast(n, k) << std::endl;
    return 0;
}