//NOIP2024 RP++ #include #define fi first #define se second #define vc vector #define mk make_pair #define ll long long #define pb push_back #define pf push_front #define PI pair #define err cerr << " -_- " << endl #define debug cerr << " -------------------------- " << endl //#define LostForALifetime //#define int long long using namespace std; namespace IO{ inline int read(){ int X=0, W=0; char ch=getchar(); while(!isdigit(ch)) W|=ch=='-', ch=getchar(); while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar(); return W?-X:X; } inline void write(int x){ if(x<0) x=-x, putchar('-'); if(x>9) write(x/10); putchar(x%10+'0'); } inline void sprint(int x){write(x); putchar(32);} inline void eprint(int x){write(x); putchar(10);} }using namespace IO; const int MAXN = 1e5+5; const int mod = 1e9 + 7; int ans, all; int head[MAXN], ne[MAXN<<1], to[MAXN<<1], weight[MAXN<<1], Fa[MAXN], cnt; int n, k, e[MAXN], deg[MAXN], f[MAXN], g[MAXN], fac[MAXN], ifac[MAXN], v[MAXN]; bool mark[MAXN]; inline ll Quickpow(ll x, ll y){ ll z=1; while(y){ if(y&1) z=z*x%mod; x=x*x%mod; y>>=1; } return z; } inline void add(int x, int y, int w){++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;weight[cnt]=w;} inline void prework(int n){ fac[0]=ifac[0]=1; v[0]=1; for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod, v[i]=Quickpow(i,mod-2), ifac[i]=Quickpow(fac[i],mod-2); return ; } inline void dfs(int x, int fa){ f[x]=0; Fa[x]=fa; for(int i=head[x];i;i=ne[i]){ if(to[i]==fa) continue; dfs(to[i],x); if(mark[weight[i]]) (f[x]+=v[deg[x]-1])%=mod; else (f[x]+=1ll*f[to[i]]*v[deg[x]-1]%mod)%=mod; } return ; } inline void calc(int x, int va){ for(int i=head[x];i;i=ne[i]){ if(to[i]==Fa[x]) continue; if(mark[weight[i]]){ (ans+=1ll*all*(mod+1-va)%mod)%=mod; calc(to[i],v[deg[to[i]]-1]); (va+=v[deg[x]-1])%=mod; } else{ calc(to[i],1ll*va*v[deg[to[i]]-1]%mod); (va+=1ll*f[to[i]]*v[deg[x]-1]%mod)%=mod; } } return ; } inline void solve(){ n=read(), k=read(); cnt=0; all=1; ans=0; for(int i=1;i<=n;++i) head[i]=deg[i]=0; for(int i=1;i<=n;++i) mark[i]=0; for(int i=1;i