#include #define mod 1000000007 using namespace std; char ib[1<<24],*ip1=ib,*ip2=ib; #define gc() (ip1==ip2&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin)),ip1==ip2?EOF:*ip1++) inline int read(){ int x=0;char c=gc(); while(c<'0'||c>'9')c=gc(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=gc(); return x; } int powdv(int x,int y=mod-2){ int ans=1; while(y){ if(y&1)ans=1ll*ans*x%mod; y>>=1,x=1ll*x*x%mod; } return ans; } int di[100005],id[100005],ny[100005]; int u[100005],v[100005],deg[100005],d[100005]; int e[100005],vist[100005]; int p[100005]; vectorg[100005];//����� index of edge int f[100005],he; void dfs(int x,int la){ f[x]=1ll*d[x]*p[x]%mod; for(auto cc:g[x]){ if(cc==la)continue; int cu=u[cc]^v[cc]^x; dfs(cu,cc); if(!vist[cc]){ he=(he+1ll*f[cu]*f[x])%mod; f[x]=(f[x]+1ll*f[cu]*p[x])%mod; } } } int main(){ freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); int c=read(),T=read(); assert(c); while(T--){ int n=read(),k=read();//n>=2 deg[i]>=1 for(int i=1;i<=n;++i){ deg[i]=d[i]=0; g[i].clear(); } for(int i=1;i=0;--i)id[i]=1ll*id[i+1]*(i+1)%mod; ny[0]=1; for(int i=1;i<=n;++i)ny[i]=1ll*id[i]*di[i-1]%mod; if(k==1){ int ans=1; for(int i=1;i<=n;++i)ans=1ll*ans*di[deg[i]-1]%mod; printf("%d\n",ans); continue; } int cj=1; for(int i=1;i<=n;++i)cj=1ll*cj*di[deg[i]-1]%mod; int ans=k; for(int i=1;i<=n;++i){ p[i]=ny[deg[i]-1]; ans=(ans-1ll*d[i]*(d[i]-1)/2%mod*p[i])%mod; } he=0;dfs(1,0);ans=(ans-he)%mod; ans=(0ll+ans+mod)*cj%mod; printf("%d\n",ans); } return 0; } /* ���ñ���DS��ex����׼������ʱ���⣡��������΢дд�μǣ� memory@2107 ͨ����Ŀ������ûһ����������ӡ�/ll D��ʼ�����ǵ䣬����ת����άƫ�򣬼ǵ����� k=1 �������9:00 A�᲻��������˸��� �ǵö��ģ���ʽ����ǰ����dp���ɣ�9:15 B���񶼻��ã���������Ҳ�����д������9:30 CĿǰ�뷨�� k=1 ���ף����˴����� 1,3 n-1���ߵ������u��������б��ڱ������������ģ�ÿ����������һ��ͷβ��Ӧ����β�� �ҳ����ݳ���ӣ����������������������⣬�������ң� ��д�����ǣ�Ϊʲôһֱ�ң�����ֻ�ܶ�� 2 �Ҳݣ���Ȼд�˸�������hack�ˣ�Ӧ�����׵���/dk Ц���ˣ�����û�� vector �������ô��/fn ���ڹ��� 1,2,3,5,6,7���Ͻ��Ż� ϲ����д���ˣ�10:40������ �Ҳ������죡���������ȫ���ô�log���Ҳ��ɿ�˭�ɿ죿 ��ʼд D��10:45 ������ O(nq) �ı�����11:00 ��IJ�̫��д�����о�ʤȯ�������Ѿ�����ô�ڶ����ˡ� �����˴�������11:40 ��������о��������㹻ʹ�Ҳ���������Ҫ��ĵĻ��� D �Ƿ��ܵĹ�ȥ��STL ����һ��ѣ� ʣ 80min ��飨���ģ���ÿ��� 20min �ɡ��ǵ�linux�±������� ����һ�� edge surf�����࿼��ʦץ��/ng B �����ˡ�12:03 A �����ˡ�12:08 D �Լ����˼������ݣ��о����ѿ��������� O2 ���� 1.2s �����ӡ����ǣ���Ϊɶ�ܵ���ô����������ʱ��ƿ�������� merge �ϣ������� fenwick�� �����о��ٶ��᲻��һ�㣬�Ǿ������ɡ� D �����ˡ�12:31 C �Ͳ�д���ˣ����˻���дд�ɡ� �������IJ��ˡ��ǾͲ�⼫�˰ɡ��������ں��Ѵ������ӡ� D ��������� k=1�� �ҿ���Ҫ��Ⱥ��v���50�ˡ� �ź����ƶ����Բ����ˣ������� */