题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5542
题目大意：在n个数中找长度为m的单调上升子序列有多少种方案
题目思路：DP，离散化，树状数组优化，
dp[i][j]代表大小为i的数 长度为j时的方案，状态转移方程dp[i][j]=simiga(dp[1..i-1][j-1]) 如果直接求和的话，复杂度是n^3不行
用树状数组优化求和 复杂度n^2logn
n<=1000,a[i]<=1e9,所以离散化搞一下就行
//更新一下 这题在HDU上面能过 但是在电科上面会T
//因为有个地方可以优化不少 在我们枚举当前大小为i长度为j的时候 也就是query(a[i]-1,j-1)时，如果该表达式为0，那么j-1之后的长度肯定时达不到的
直接break就行了
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=;
const long long mod=1e9+;
long long tree[maxn][maxn];
int dp[maxn][maxn];
int a[maxn],b[maxn];
void add(int i,int m,int k){
for(i;i<=maxn;i+=(i&(-i))) (tree[m][i]+=k)%=mod;
}
long long query(int i,int m){
long long sum=;
for(i;i>;i-=(i&(-i))) (sum+=tree[m][i])%=mod;
return sum%mod;
}
void init(int n,int m){
for(int i=;i<=m+;i++){
for(int j=;j<=n+;j++){
dp[i][j]=;
}
}
for(int i=;i<=m+;i++)
memset(tree[i],,sizeof(tree[i]));
}
void solve(int T){
printf("Case #%d: ",T);
int n,m;
scanf("%d %d",&n,&m);
init(n,m);
for(int i=;i<=n;i++) scanf("%d",&b[i]),a[i]=b[i];
sort(b+,b++n);
int size=unique(b+,b++n)-b;
for(int i=;i<=n;i++) a[i]=lower_bound(b+,b+size,a[i])-b;
for(int i=;i<=n;i++){
for(int j=;j<=min(i+,m);j++){
if(j==) dp[j][a[i]]=;
else
dp[j][a[i]]=query(a[i]-,j-)%mod;
if(dp[j][a[i]]==) break;//如果长度j都到不了 那么j以后的肯定也是到不了
add(a[i],j,dp[j][a[i]]);
}
}
printf("%lld\n",query(size,m)%mod);
}
int main(){
int T;
scanf("%d",&T);
for(int i=;i<=T;i++) solve(i);
}