C++ 解法, 执行用时: 1199ms, 内存消耗: 342116K, 提交时间: 2022-05-19 11:56:05

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

#define OK puts("OK")

const int mod=1e9+7;
const int MN=2005;
const int MC=3e7+5;
int n,m;
vector<int>G[MN];
int f[MN][MN],g[MN][MN];

void dp(int u,int fa){
    for(int i=1;i<=n+1;i++)f[u][i]=1;
    for(int v:G[u]){
        if(v==fa)continue;
        dp(v,u);
        for(int i=1;i<=n+1;i++)f[u][i]=f[u][i]*g[v][i]%mod;
    }
    for(int i=1;i<=n+1;i++)g[u][i]=(g[u][i-1]+f[u][i])%mod;
}

int a[MN],invx[MN],p[MN],q[MN],r[MN];

int ksm(int x,int y,int p=mod){
    int res=1;
    for(int i=y;i;i>>=1,x=x*x%p)if(i&1)res=res*x%p;
    return res;
}

int inv(int x,int p=mod){
    return ksm(x,p-2,p);
}

void Lagrange(){
    for(int i=1;i<=n+1;i++)invx[i]=inv(i);
    p[0]=1;
    for(int i=1;i<=n+1;i++){
        q[0]=mod-i,q[1]=1;
        for(int j=0;j<i;j++)
            for(int k=0;k<=1;k++)r[j+k]=(r[j+k]+p[j]*q[k]%mod+mod)%mod;
        for(int j=0;j<=i;j++)p[j]=r[j],r[j]=0;
    }
    for(int i=1;i<=n+1;i++){
        int fm=inv(g[1][i])%mod;
        for(int j=1;j<=n+1;j++)if(j!=i)fm=fm*(i-j+mod)%mod;
        r[0]=(mod-p[0]*invx[i]%mod+mod)%mod,fm=inv(fm);
        for(int j=1;j<=n;j++)r[j]=(mod-(p[j]-r[j-1]+mod)%mod*invx[i]%mod+mod)%mod;
        for(int j=0;j<=n;j++)a[j]=(a[j]+r[j]*fm%mod+mod)%mod;
    }
}

int calc(int k){
    int res=0;
    for(int i=n;i>=0;i--)res=(res*k%mod+a[i])%mod;
    return res;
}

int mu[MC],pri[1857860];
bool isp[MC];

void pre(){
    int N=30000000,cnt=0;mu[1]=1;
    memset(isp,1,sizeof(isp));
    for(int i=2;i<=N;i++){
        if(isp[i])pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt;j++){
            if(i*pri[j]>N)break;
            int x=i*pri[j];isp[x]=0;
            if(i%pri[j]==0){mu[x]=0;break;}
            mu[x]=-mu[i];
        }
    }
    for(int i=1;i<=N;i++)mu[i]+=mu[i-1];
}

signed main(void){


    n=read(),m=read();
    for(int i=1;i<=n-1;i++){
        int u=read(),v=read();
        G[u].push_back(v),G[v].push_back(u);
    }
    dp(1,0);pre(),Lagrange();
    int ans=0;
    for(int l=1,r=0;l<=m;l=r+1){
        r=m/(m/l);
        ans=(ans+(mu[r]-mu[l-1]+mod)%mod*calc(m/l)%mod+mod)%mod;
    }
    cout<<ans<<endl;


    return 0;
}