Lightoj 1095 - Arrange the Numbers

http://lightoj.com/volume_showproblem.php?problem=1095

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define MOD 1000000007
4. #define N 1005
5. #define ll long long unsigned
6. ll fac[N];
7. ll dp[N][N];
8. int pre(){
9.     fac[0] = 1;
10.     for(int i = 1; i <N; i++) fac[i]= (fac[i-1]*i)%MOD;
11.     memset(dp, -1, sizeof(dp));
12. }
13. ll ncr(int n, int k){
14.     if(k==1) return n;
15.     if(n==k) return 1;
16.     if(dp[n][k]!=-1) return dp[n][k];
17.     return dp[n][k]= (ncr(n-1,k-1)+ncr(n-1,k))%MOD;
18. }
19. int main(){
20.     pre();
21.     int ts;
22.     scanf("%d", &ts);
23.     for(int p =1;p <= ts; p++){
24.     int n, m, k;
25.     scanf("%d%d%d", &n, &m, &k);
26.     ll ans1 = ncr(m, k);
27.     ll ans2 = fac[n-k];
28.     for(int i = 1; i <= m-k; i++){
29.         if(i%2) ans2-= (ncr(m-k, i)*fac[n-k-i])%MOD;
30.         else ans2+= (ncr(m-k, i)*fac[n-k-i])%MOD;
31.         ans2 = (ans2+MOD)%MOD;
32.     }
33.     printf("Case %d: %llu\n",p, (ans1*ans2)%MOD);
34.     }
35.     return 0;  
36. }