显然，
-
条件一等价于在 \(T'\) 中，\(1\sim n\) 组成的虚树等于它本身。
-
条件二等价于 \(1\sim i\) 组成的虚树上点的标号不超过 \(i+k\)。
我们考虑在原树的基础上依次添加 \(n+1\sim n+m\) 这 \(m\) 个点。添加一个点 \(i\) 时，它与原树的位置关系可能有以下几种：
- 挂在原树上某个点的下面。
- 挂在原树上某条边的中间。
- 原树上某条边分裂出一个编号比它大的点 \(j\)，然后将 \(i\) 挂在 \(j\) 下面。
我们考虑，对于第三种情况，我们不直接将这样的 \(i\) 加入虚树，而是维护一个集合 \(S\)，如果遇到这样的 \(i\)，就往 \(S\) 中加入 \(i\)，然后到扫描到 \(j\) 的时候再处理这样的 \(i\)。那么一个性质是，假设我们当前扫描到 \(i\)（还没处理加入 \(i\) 的贡献），那么 \(S\) 中的所有元素都必须 \(\ge i-k\)。这样可能的 \(S\) 只有 \(2^k\) 种。我们考虑 \(dp_{i,msk}\) 表示现在加入完 \(n+1\sim n+i\)，\(\forall x\)，\(x\in S\) 当且仅当 \(msk\) 的第 \(n+i-x\) 位为 \(1\)。那么我们考虑处理 \(i+1\) 时可能发生的转移：
- \(i+1\) 挂在原树上某个点的下面，有 \(n+i+|S|\) 种可能，转移到 \(dp_{i+1,2·msk}\)。
- \(i+1\) 挂在原树上某条边的中间，有 \(n+i+|S|-1\) 种可能，转移到 \(dp_{i+1,2·msk}\)。
- \(i+1\) 作为上述第三种情况中某个“\(i\)“出现，有 \(n+i+|S|-1\) 种可能，转移到 \(dp_{i+1,2·msk+1}\)。
- \(i+1\) 作为上述第三种情况中某个“\(j\)“出现，那么我们枚举它消灭掉的是哪个 \(i\)，设为 \(x\)，那么转移到 \(dp_{i+1,2(msk-2^x)}\)。
时间复杂度 \(Tmk2^k\)。
const int MAXP=1024;
const int MOD=1e9+7;
int n,m,k,f[MAXP+5],g[MAXP+5];
void add(int &x,int v){((x+=v)>=MOD)&&(x-=MOD);}
void solve(){
scanf("%d%d%d",&n,&m,&k);
for(int i=2;i<=n;i++)scanf("%*d");
memset(f,0,sizeof(f));f[0]=1;
for(int i=0;i<m;i++){
memset(g,0,sizeof(g));
for(int j=0;j<(1<<k);j++)if(f[j]){
int tmp=j;
while(tmp){
int lw=tmp&(-tmp);tmp^=lw;
if(((j^lw)<<1)<(1<<k))add(g[(j^lw)<<1],f[j]);
}
int c=n+i+__builtin_popcount(j);
if((j<<1)<(1<<k)){
add(g[j<<1],1ll*(c*2-1)*f[j]%MOD);
add(g[j<<1|1],1ll*(c-1)*f[j]%MOD);
}
}swap(f,g);
}printf("%d\n",f[0]);
}
int main(){
int qu;scanf("%*d%d",&qu);
while(qu--)solve();
return 0;
}