分别算出一条边将原树分割成两个子树，然后用排列组合求出所有k个点在其中一棵子树（不需要这条边），或者小于k个点在这一个子树（需要这条边）的所有情况之和。
预处理好阶乘step，再进行如下变形（1e9+7是素数，所以直接用费马小定理啦）
C(num[p],i)%mod
=num[p]!/(i!*(num[p]-i)!)%mod
=num[p]!/(i!*(num[p]-i))*(i!*(num[p]-i)!)^(mod-1)%mod
=num[p]!*(i!*(num[p]-i)!)^(mod-2)%mod=num[p]!*fast_pow(i!*(num[p]-i)!,mod-2)%mod
=step[num[p]]*fast_pow(step[i]*(num[p]-i)%mod,mod-2)%mod;
标程

#include<bits/stdc++.h>
#define LL long long
const LL mod=1e9+7;
inline void read(LL &a)
{
    a=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
        a=(a<<1)+(a<<3)+c-'0';
        c=getchar();
    }
}
inline void write(LL a)
{
    if(a<0){putchar('-');a=-a;}
    if(a>9)write(a/10);
    putchar(a%10+'0');
}
#define maxn 2001
LL ans=0,n,k,d=0,num[maxn],point[maxn],next[maxn],to[maxn],father[maxn],step[maxn];
inline void add(LL a,LL b)
{
    next[++d]=point[a];
    point[a]=d;
    to[d]=b;
}
inline LL fast_pow(LL a,LL b)
{
    LL base=a,ans=1;
    while(b)
    {
        if(b&1)ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans;
}
inline LL dfs1(LL p)
{
    LL side=point[p];
    num[p]=1;
    while(side)
    {
        if(to[side]!=father[p])
        {
            father[to[side]]=p;
            num[p]+=dfs1(to[side]);
        }
        side=next[side];
    }
    return num[p];
}
inline LL C(LL m,LL n)
{
    return step[m]*fast_pow(step[n]*step[(m-n)]%mod,mod-2)%mod;
}
inline void dfs2(LL p)
{
    for(LL i=1;i<=k&&i<=num[p];i++)
        if(k-i<=n-num[p]&&k-i)
            ans=(ans+C(num[p],i)*C(n-num[p],k-i)%mod)%mod;
    LL side=point[p];
    while(side)
    {
        if(to[side]!=father[p])dfs2(to[side]);
        side=next[side];
    }
}
int main()
{
    read(n);read(k);
    LL st=1; 
    step[0]=1;
    for(LL i=1;i<=n;i++)st=step[i]=i*st%mod;
    memset(num,0,sizeof(num));
    memset(point,0,sizeof(point));
    LL u,v;
    for(LL i=1;i<=n-1;i++){read(u);read(v);add(u,v);add(v,u);}
    dfs1(1);
    dfs2(1);
    write(ans);
    return 0;
}

这是用扩展欧几里得求逆元，感谢Takami同学提供标程！（虽然他沒同意）

#include <stdio.h>
#include <iostream>
typedef long long ll;
const int maxn = 1005;
using namespace std;
const int mod = 1e9+7;
int n,k;
ll fact[maxn];
inline void exgcd(int a,int b,int &x,int &y) {
    if(!b) {
        x = 1,y = 0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=x*(a/b);
}
int ni(int a) {
    int x,y;
    exgcd(a,mod,x,y);
    while(x<0) x+=mod;
    return x;
}
struct edge {
    int a,b;
    int right,left;
} edges[maxn];
int head[maxn],nex[maxn<<1],dis[maxn<<1],q;
inline void connect(int x,int y) {
    nex[++q] = head[x],head[x] = q,dis[q] = y;
    nex[++q] = head[y],head[y] = q,dis[q] = x;
}
int cloc,in[maxn],out[maxn],fa[maxn];
void dfs(int a,int father) {
    fa[a] = father;
    in[a] = ++cloc;
    for(int i = head[a]; i; i = nex[i]) {
        int to = dis[i];
        if(to!=father)
            dfs(to,a);
    }
    out[a] = cloc;
}
int c(ll a,ll b) {
    return 1l*((1ll*fact[a]%mod*ni(fact[b])%mod)%mod)*ni(fact[a-b])%mod;
}
int mem[maxn][maxn];
int solve(ll a,ll b) {
    if(mem[a][b]) return mem[a][b];
    int ret = 0;
    for(int i = 1; i<=max(a,b); i++) {
        if(k-i<=b&&k-i>=1&&i<=a) {
            ret  = (ret+ 1ll*c(a,i)*c(b,k-i)%mod)%mod;
        }
    }
    mem[a][b] = mem[b][a] = ret;
    return ret;
}
int main() {
    cin>>n>>k;
    for(int i  =1; i<=n-1; i++) {
        int x,y;
        cin>>x>>y;
        edges[i].a = x,edges[i].b = y;
        connect(x,y);
    }
    fact[0] = 1;
    for(int i = 1; i<=n; i++)fact[i] = fact[i-1]*i%mod;
    int ans = 0;
    dfs(1,1);
    for(int i = 1; i<=n-1; i++) {
        edge &ed = edges[i];
        if(fa[ed.a]!=ed.b) swap(ed.a,ed.b);
        ed.right = out[ed.a]-in[ed.a]+1;
        ed.left = n -ed.right;
        ans=(ans+solve(ed.right,ed.left))%mod;
    }
    cout<<ans;
    return 0;
}

数据生成器
#include<bits/stdc++.h>
inline const void write(int a)
{
if(a>9)write(a/10);
putchar(a%10+'0');
}
int belong[1001];
inline const int check(int a)
{
if(belong[a]==a)return a;
return belong[a]=check(belong[a]);
}
int main()
{
freopen(".in","w",stdout);
srand(time(NULL));
int n=rand()%1001;
write(n);printf("\n");
for(int i=1;i<=n;i++)belong[i]=i;
for(int i=1;i<=n-1;i++)
{
while(true)
{
int u=0,v=0;
while(!u)u=rand()%(n+1);while(!v)v=rand()%(n+1);
if(check(u)!=check(v))
{
write(u);putchar(' ');write(v);printf("\n");
belong[check(u)]=v;
break;
}
}
}
return 0;
}