Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
776 B
3
Indexable
Never
#include <iostream>
using namespace std;

long long p = 1000000007;

long long factorial(long long n) {
	long long res = 1;
	while (n > 1) {
		res = (res * ((n/p) % 2 ? p-1 : 1)) % p;
		for (long long i=2; i<=n%p; ++i)
			res = (res * i) % p;
		n /= p;
	}
	return res % p;
}

long long xGCD(long long a, long long b, long long &x, long long &y) {
    if(b == 0) {
       x = 1;
       y = 0;
       return a;
    }

    long long x1, y1, gcd = xGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

int main()
{
	long long n,k;
	cin >> n >> k;

	long long n_fact = factorial(n);
	long long x,y;

	long long denominator = factorial(k)*factorial(n - k);

	xGCD(denominator, p, x, y);

	if (x < 0)
	{
		x = x + p;
	}

	cout << (n_fact * x)%p << endl;
}