Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu   LightOJ 1067  
Description
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 除法求模不能类似乘法，对于（A/B）mod C，直接（A mod C）/ （B mod C）是错误的；找到B的逆元b(b=B^-1);求出(A*b)modC即可； 由费马小定理：B 关于 P 的逆元为  B^(p-2);
费马小定理(Fermat Theory)是数论中的一个重要定理，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a^{(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。}所以，a^-1*a=1=a^(p-1),所以：a^-1=a^(p-2); 数学排列组合公式：C（n，m）= n！/（m！*（n-m）！）
代码： #include #include #include using namespace std; #define LL long long #define G 1100000 #define mod 1000003 LL pri[G]; LL ni[G],ans; LL pow(LL a,int b) { LL ans=1,base=a; while (b>0) { if (b%2==1) ans=(base*ans)%mod; base=(base*base)%mod; b/=2; } return ans; } void s() //打表 { pri[0]=1; ni[0]=1; for (int i=1;i