Pagini recente » Cod sursa (job #3285800) | Cod sursa (job #1122280) | Cod sursa (job #3285061) | Cod sursa (job #3146564) | Cod sursa (job #3249819)
#include <bits/stdc++.h>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
const long long MOD = 1000000007;
void bezout(long long &x, long long &y, long long &d, int a, int b)
{
if(!b)
x = 1, y = 0, d = a;
else
{
bezout(x, y, d, b, a % b);
///swap(x,y);
x ^= y;
y ^= x;
x ^= y;
y = y - x * (a / b);
/*
int aux = x;
x = y;
y = aux - y * (a / b);*/
}
}
long long comb(long long n, long long k)
{
long long x = 0, y = 0, d, valcomb = 1;
for(int i = n - k + 1; i <= n; i++)
valcomb=(valcomb*i)%MOD;
for(int i = 1; i <= k; i++)
{
x=y=0;
bezout(x, y, d, i, MOD);
if(x <= 0)
x = MOD - abs(x) % MOD;
valcomb=(valcomb*x)%MOD;
}
return valcomb%MOD;
}
int main()
{
long long n, k ;
f >> n >> k;
g << comb(n,k);
return 0;
}