LightOJ - 1067 - Combinations

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define M (long long)1000003
8. #define S 1000003
9. #define LL long long
10. using namespace std;
11.  
12. LL factorial[M+3];
13.  
14. void findFact(){
15.     factorial[0] = 1;
16.     for(int i = 1; i < S; i++){
17.         factorial[i] = factorial[i-1] * i;
18.         factorial[i] %= M;
19.     }
20. }
21.  
22. LL modInverse(LL a, LL p){
23.     if(p == 0)return 1LL;
24.     else if(p%2)return ((a%M)*(modInverse(a, p-1)%M))%M;
25.     else{
26.         LL x = modInverse(a, p/2);
27.         return (x%M*x%M)%M;
28.     }
29. }
30.  
31. int main(){
32.     memset(factorial, 1LL, sizeof(factorial));
33.     findFact();
34.     int t, cs = 0;
35.     LL n, k;
36.     scanf("%d", &t);
37.     while(t--){
38.         scanf("%d %d", &n, &k);
39.         LL y = factorial[n];
40.         LL z = (factorial[n-k]%M*factorial[k]%M)%M;
41.         LL ans = modInverse(z, M-2LL);
42.         ans = (y%M*ans%M)%M;
43.         printf("Case %d: %lld\n", ++cs, ans);
44.     }
45.     return 0;
46. }