Binomial_Mod_Template

pair<ll, pair<ll, ll> > egcd(ll a, ll b)				//solves ax + by = gcd(a,b) = g;
{	//returns (g,(x,y))
	pair<ll, pair<ll, ll> > ret;

	if (a == 0)
	{
		ret.f = b ;
		ret.s.f = 0 ;
		ret.s.s = 1 ;
	}
	else
	{
		ll g, x, y;
		pair<ll, pair<ll, ll> > temp = egcd( b % a, a) ;
		g = temp.f;
		x = temp.s.f;
		y = temp.s.s;
		ret.f = g;
		ret.s.f = y - (b / a) * x ;
		ret.s.s = x;
	}

	return ret;
}

ll modinv(ll den, ll m)			// den and m must be coprime
{
	pair<ll, pair<ll, ll> > ans = egcd(den, m) ;
	if (ans.f == 1)
	{
		return (ans.s.f + m) % m ;
	}
}


ll moddiv(ll num, ll den, ll m)
{
	return (num * modinv(den, m) ) % m ;
}


vll fact;
void C( int n, ll m)		// n must be less than m
{
	fact.reserve(n + 1);
	fact[0] = 1;
	vll num(n + 1, 1); // n*(n-1)*(n-2).....(n-k+1)
	for (int i = 0; i < n ; i++)
	{
		num[i + 1] = (num[i] * (n - i)) % m ;
	}

	vll den(n + 1, 1); //k!
	for (int i = 1; i <= n; i++)
	{
		den[i] = (den[i - 1] * i) % m ;
	}

	for (int i = 1; i <= n; i++)
	{
		fact[i] = moddiv(num[i], den[i], m);
	}
}