Given n different objects, you want to take k of them. How many ways to can do it?

For example, say there are 4 items; you want to take 2 of them. So, you can do it 6 ways.

Take 1, 2

Take 1, 3

Take 1, 4

Take 2, 3

Take 2, 4

Take 3, 4

Input
Input starts with an integer T (≤ 2000), denoting the number of test cases.

Each test case contains two integers n (1 ≤ n ≤ 106), k (0 ≤ k ≤ n).

Output
For each case, output the case number and the desired value. Since the result can be very large, you have to print the result modulo 1000003.

Sample Input
3

4 2

5 0

6 4

Sample Output
Case 1: 6

Case 2: 1

Case 3: 15

模板题。注意这里的mod是1e6的，如果要预处理[latex]n!%mod[/latex]需要开longlong的数组，因为有可能会出现1e6*1e6的情况。被坑了很久

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modn=1000003;
ll fact[modn+23]={0};
ll geta(ll n,ll& e)
{
	e=0;
	if(n==0) return 1;
	ll res=geta(n/modn,e);
	e+=n/modn;
	if(n/modn%2!=0) return res*(modn-fact[n%modn])%modn;
	return res*fact[n%modn]%modn;
}
ll exgcd(ll a,ll b,ll& x,ll& y)
{
	ll d=a;
	if(b!=0)
	{
		d=exgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}
	else
	{
		x=1;
		y=0;
	}
	return d;
}
ll mdr(ll a,ll m)
{
	ll x,y;
	exgcd(a,m,x,y);
	return (m+x%m)%m;
}
ll calc(ll n,ll k)
{
	if(n<0||k<0||n<k) return 0;
	ll e1,e2,e3;
	ll a1=geta(n,e1);
	ll a2=geta(k,e2);
	ll a3=geta(n-k,e3);
	if(e1>e2+e3) return 0;
	return a1*mdr(a2*a3%modn,modn)%modn;
}
int main()
{
	ll t,n,k;
	fact[0]=1;
	for(ll i=1;i<=modn;i++) fact[i]=(fact[i-1]*i)%modn;
	scanf("%lld",&t);
	for(ll i=1;i<=t;i++)
	{
		scanf("%lld%lld",&n,&k);
		printf("Case %lld: ",i);
		printf("%lld\n",calc(n,k));
	}	
}