GCD of two binomial coefficients modulo 10^9 + 7

Question

There are given 0 ≤ k ≤ n ≤ 500000, 0 ≤ l ≤ m ≤ 500000.

I need co calculate GCD(C(n, k), C(m, l)) modulo 10^9 + 7.

My attempt:

I thought about tricks with fourmula: C(n, k) = n*(n-1)*...*(n-k+1) / k!

For example, suppose l >= k: GCD( C(n, k), C(m, l) ) = = GCD( n*(n-1)*...*(n-k+1) / k!, m*(m-1)*...*(m-l+1) / l! ) = = GCD( n*(n-1)*...*(n-k+1)*(k + 1)*...*l/ l!, m*(m-1)*...*(m-l+1) / l! ) = = GCD( n*(n-1)*...*(n-k+1)*(k + 1)*...*l, m*(m-1)*...*(m-l+1) ) / l!

Inversing l! with binary exponentiation to 10^9 + 5 is fine, but I don't know how to continue.

This (k + 1)*...*l part ruins everything. I can find some benefit if there is intersection between multipliers of n*(n-1)*...*(n-k+1) and m*(m-1)*...*(m-l+1), but if not, whole GCD must be contained in this (k + 1)*...*l part.

And what's next? Using native GCD algorithm for remaining multipliers? Too long again because of need to calculate product of them, so that manipulations above look meaningless.

Am I on a right way? Is there some trick to come up with this problem?

Answer 1

With juvian`s advice it is very simple. How didn't I come up with an idea of factorization!

My C++ code below:

#include <iostream>
#include <algorithm>

#define NMAX 500000
#define MOD 1000000007

using namespace std;


long long factorial(long long n)
{
    long long ans = 1;
    for (int i = 2; i <= n; i++)
        ans = ans * i % MOD;
    return ans;
}

long long binPow(long long num, int p)
{
    if (p == 0)
        return 1;

    if (p % 2 == 1)
        return binPow(num, p - 1) * num % MOD;
    if (p % 2 == 0)
    {
        long long b = binPow(num, p / 2);
        return b * b % MOD;
    }
}

void primesFactorize(long long n, long long primes[])
{
    for (int d = 2; d * d <= n; d++)
        while(n % d == 0)
        {
            n /= d;
            primes[d]++;
        }
    if (n > 1) primes[n]++;
}

long long primes1[NMAX];
long long primes2[NMAX];

int main()
{
    long long n, k, m, l;

    cin >> k >> n >> l >> m;

    if (k > l)
    {
        swap(n, m);
        swap(k, l);
    }

    for (int i = n - k + 1; i <= n; i++)
        primesFactorize(i, primes1);

    for (int i = k + 1; i <= l; i++)
        primesFactorize(i, primes1);

    for (int i = m - l + 1; i <= m; i++)
        primesFactorize(i, primes2);

    for (int i = 2; i <= max(n, m); i++)
        primes1[i] = min(primes1[i], primes2[i]);

    long long ans = 1;
    for (int i = 2; i <= max(n, m); i++)
        for (int j = 1; j <= primes1[i]; j++)
            ans = ans * i % MOD;

    ans = ans * binPow(factorial(l), MOD - 2) % MOD;

    cout << ans << endl;
    return 0;
}