考虑dp.
f[i][j]表示以a[i]结尾,长度为j的递增序列数量
那么可得转移: $$f[i][1]=1$$
$$f[i][j]=\sum_{k=1}^{j-1} f[i-1][k] (a[k]<a[j])$$
暴力做就是$O(n^2m)$
考虑优化.$k$对$j$有贡献,当且仅当$a[k]<a[j],k<j$.两个限制条件不是单调的,无法直接处理.

修改一下转移的定义,f[i][j]表示以i结尾(注意这里的不同),长度为j的递增序列数量
那么这里的转移就变成 $$f[i][j]=\sum_{k=1}^{j-1} f[i-1][k] (k在j之前出现)$$
用树状数组维护前缀和.$t[i].Qsum(j)$表示$\sum_{k=1}^j f[i][k]$.考虑到$a[j]$时,如果前面的数都已经插入树状数组并且后面的数都没有插入树状数组,那么 $$f[i][a[j]]=t[i].Qsum(a[j]-1)$$
我们就这样扫描每个数,求出它在每个长度下的f后把它插入到对应的树状数组中就好了.
注意离散化,时间复杂度$O(nmlogn)$

/**********/省略快读
#define MAXN 1011
ll n,m,a[MAXN],fx[MAXN];
ll place(ll val)
{
    return std::lower_bound(fx+1,fx+n+1,val)-fx;
}
const ll mod=ll(1e9+7);
struct BIT
{
    ll t[MAXN];
#define lowb (i&-i)
    void clear()
    {
        memset(t,0,sizeof t);
    }
    void modify(ll i,ll k)
    {
        while(i<=n)
        {
            t[i]=(t[i]+k)%mod;
            i+=lowb;
        }
    }
    ll Qsum(ll i)
    {
        if(i==0)return 0;
        ll res=0;
        while(i)
        {
            res=(res+t[i])%mod;
            i-=lowb;
        }
        return res;
    }
}t[MAXN];
int main()
{
    ll task=read();
    for(ll p=1;p<=task;++p)
    {
        n=read(),m=read();
        for(ll i=1;i<=n;++i)
        {
            a[i]=read();
            fx[i]=a[i];
        }
        std::sort(fx+1,fx+n+1);
        for(ll i=1;i<=n;++i)
        {
            for(ll len=1;len<=min(i,m);++len)
            {
                ll val;
                if(len>1)val=t[len-1].Qsum(place(a[i])-1);
                else val=1;
                t[len].modify(place(a[i]),val);
            }
        }
        printf("Case #%lld: %lld\n",p,t[m].Qsum(n));
        for(ll len=1;len<=m;++len)t[len].clear();
    }
    return 0;
}