//#pragma comment(linker, "/STACK:102400000, 102400000")

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = 1e3 + ;

 LL dp[N][N], mod = 1e9 + ;

 int a[N], b[N], m, n;

 LL bit[N][N];

 void add(int pos, int i, int val) { //上升子序列长度为pos

     for( ; i <= n; i += (i&-i))

         bit[pos][i] = (bit[pos][i] + val) % mod;

 }

 LL sum(int pos, int i) {

     LL s = ;

     for( ; i >= ; i -= (i&-i))

         s = (s + bit[pos][i]) % mod;

     return s;

 }

 int main()

 {

     int t;

     scanf("%d", &t);

     for(int ca = ; ca <= t; ++ca) {

         scanf("%d %d", &n, &m);

         for(int i = ; i <= n; ++i) {

             scanf("%d", a + i);

             b[i] = a[i];

         }

         sort(b + , b + n + );

         for(int i = ; i <= n; ++i) {

             a[i] = lower_bound(b + , b + n + , a[i]) - b; //离散化

         }

         memset(dp, , sizeof(dp));

         memset(bit, , sizeof(bit));

         dp[][] = ;

         add(, a[], );

         for(int i = ; i <= n; ++i) {

             dp[i][] = ;

             for(int k = max(m - (n - i), ); k <= min(i, m); ++k) { //这边可以优化一下

                 dp[i][k] = (dp[i][k] + sum(k - , a[i] - )) % mod; //比a[i]小且上升子序列长度为k-1

                 add(k, a[i], dp[i][k]);

             }

         }

         LL res = ;

         for(int i = ; i <= n; ++i) {

             res = (res + dp[i][m]) % mod;

         }

         printf("Case #%d: %lld\n", ca, res);

     }

     return ;

 }