1 #include <bits/stdc++.h> 2 using namespace std; 3 #define lowbit(x) x & (-x) 4  5 const int mod = int(1e9+7); 6 const int maxn = 1010; 7 int dp[maxn][maxn]; 8 int a[maxn], h[maxn]; 9 int n, m, hcnt;10 11 int sum(int i, int x) {12     int ret = 0;13     while(x) {14         ret = (ret + dp[i][x]) % mod;15         x -= lowbit(x);16     }17     return ret;18 }19 20 void update(int i, int x, int k) {21     while(x <= n) {22         dp[i][x] = (dp[i][x] + k) % mod;23         x += lowbit(x);24     }25 }26 27 int getid(int x) {28     return lower_bound(h, h+hcnt, x) - h;29 }30 31 int main() {32     // freopen("in", "r", stdin);33     int T, _ = 1;34     scanf("%d", &T);35     while(T--) {36         printf("Case #%d: ", _++);37         scanf("%d %d", &n, &m);38         for(int i = 1; i <= n; i++) {39             scanf("%d", &a[i]);40             h[i-1] = a[i];41         }42         sort(h, h+n); hcnt = unique(h, h+n) - h;43         for(int i = 1; i <= n; i++) a[i] = getid(a[i]) + 1;44         memset(dp, 0, sizeof(dp));45         for(int i = 1; i <= n; i++) {46             int lo = min(i, m);47             for(int j = 1; j <= lo; j++) {48                 if(j == 1) {49                     update(j, a[i], 1);50                     continue;51                 }52                 int tmp = sum(j-1, a[i]-1);53                 update(j, a[i], tmp);54             }55         }56         printf("%d\n", sum(m, n));57     }58     return 0;59 }