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 ≤ 10⁶), 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.

分析：

时间只有2秒，T组测试数据加上n的10⁶达到了10⁹递推肯定超时，那么考虑组合公式，C(n,k)=n!/(k!*(n-k)!);先打一个阶乘的表（当然要取模，只有10⁶）,然后就是这个除法取模的问题，当然是求逆元，（a/b）%mod=a*(b对mod 的逆元);求逆元可以用扩欧和费马小定理。

费马小定理的使用条件mod必须为素数。

代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
#define N 1000009
#define mod 1000003
#define LL long long

LL fact[N];

void init()
{
fact[0] = fact[1] = 1;

for(int i = 2; i < N; i++)
fact[i] = (fact[i-1] * i) % mod;
}
/*LL niyuan(int a, int p)
{
LL ans = 1;

if(p == 0)
return 1;

while(p)
{
if(p & 1)
ans = (ans * a) % mod;
a = (a * a) % mod;
p >>= 1;
}
return ans;

}*/

LL niyuan(int a, int b)///就是一个快速幂。
{
if(b == 0)
return 1;

LL x = niyuan(a, b / 2);

LL ans = x * x % mod;

if(b % 2 == 1)
ans = ans * a % mod;

return ans;
}
LL c(int n, int k)
{
LL fm = (fact[k] * fact[n-k]) % mod;///n! * (n-m)!.
LL ans1 = niyuan(fm, mod - 2);///求n!的逆元。

return (ans1 * fact[n]) % mod;///公式(a / b ) % mod = (a * a ^(mod-2) % mod。
}
int main(void)
{
int T, cas;
int n, k;

init();
scanf("%d", &T);
cas = 0;

while(T--)
{
cas++;
scanf("%d%d", &n, &k);
if(2 * k > n)///组合数性质。
k = n - k;

printf("Case %d: %lld\n", cas, c(n, k));

}
return 0;
}