LightOJ-nCr.c

#include"stdio.h"
#include"string.h"
#include"math.h"
#include"stdlib.h"
#include"ctype.h"
#include"limits.h"
#include"time.h"
#include"stdbool.h"
#define ll long long
ll factory[1000005]={1};

ll mod(ll n, ll l, ll o)
{
	ll m=1;
	while(l)
	{
		if(l%2)
		m=(m*n)%o;
		n=(n*n)%o;
		l/=2;
	}
	return m%o;
}

int main()
{
	clock_t lnh=clock();
	int t,d=1;
	scanf("%d",&t);
	ll i,f;
	for(i=f=1;i<1000005;i++)
	factory[i]=(factory[i-1]*i)%1000003;
	
	while(t--)
	{
	ll n,i,k,a,b,m=1000003;
	scanf("%lld%lld",&n,&k);
	
	a=mod(factory[k],m-2,m);
	b=mod(factory[n-k],m-2,m);
	n=factory[n];
	b=(a*b)%m;
	n=(n*b)%m;
	
	printf("Case %d: %lld\n",d++,n);
	
	}
	
	clock_t cls=clock();
  //printf("%fms\n",(double)((cls-lnh)*1000)/CLOCKS_PER_SEC);
	return 0;
}