显然有方程$f_{i,j}$表示前$j$个数以$A_j$选$i$个数构成严格单调上升子序列的方案数
$f_{i,j}=\sum\limits_{k<j并且a_k<a_j}f_{i-1,k}$,搞个树状数组维护一下就好了。
前一维可以滚掉。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=1e3+5;
const int mod=1e9+7;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[N];int a[N],b[N],sz,n,m;
void disc()
{
    sort(b+1,b+sz+1);int len=0;
    for(int i=1;i<=sz;i++)
        if(i==1||b[i-1]!=b[i])b[++len]=b[i];
    sz=len;
}
inline int get(int d)
{
    int l=1,r=sz;
    while(l<r)
    {
        int mid=l+r>>1;
        if(b[mid]<d)l=mid+1;
        else r=mid;
    }
    return l;
}
int c[N];
inline void add(int x,int k){for(;x<=sz;x+=x&-x)c[x]=(c[x]+k)%mod;}
inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans=(ans+c[x])%mod;return ans;}
int main()
{
    //freopen("data10.in","r",stdin);
    int T;qr(T);int t=0;
    while(T--)
    {
        qr(n),qr(m);
        for(int i=1;i<=n;i++)qr(a[i]),b[i]=a[i];
        sz=n;
        disc();memset(f,0,sizeof(f));
        for(int i=0;i<=n;i++)a[i]=get(a[i]);
        for(int i=1;i<=n;i++)f[i]=1;
        for(int i=2;i<=m;i++)
        {
            memset(c,0,sizeof(c));
            for(int j=i-1;j<=n;j++)
            {
                add(a[j],f[j]);
                f[j]=ask(a[j]-1);
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
            ans=(ans+f[i])%mod;
        ++t;
        printf("Case #%d: ",t);
        qw(ans);puts("");
    }
    return 0;
}