#include using namespace std; inline int rd(){ char c=getchar();int s=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) s=s*10+c-48,c=getchar(); return s; } const int p=1e9+7,N=100005; int n,k,i,x,y,tot=1,lst[N],tmp[3],a[N],b[N],iv[N],cnt[N]; bool vis[N]; struct edg{ int y,n; }d[N<<1]; void cun(int x,int y){d[++tot]=edg{y,lst[x]};lst[x]=tot;} int f[N][3]; void dfs(int x,int fa){ f[x][0]=1,f[x][1]=f[x][2]=0;int u=iv[cnt[x]]; for(int j=lst[x];j;j=d[j].n) if(j^fa^1){ dfs(d[j].y,j); f[x][2]=(1ll*f[x][2]*f[d[j].y][0]+1ll*f[x][1]*f[d[j].y][1]%p*u+1ll*f[x][0]*f[d[j].y][2])%p; f[x][1]=(1ll*f[x][0]*f[d[j].y][1]+1ll*f[x][1]*f[d[j].y][0])%p; f[x][0]=1ll*f[x][0]*f[d[j].y][0]%p; } int mul=1; for(int j=1;j>1]){ f[x][2]=((f[x][2]-f[x][0])%p-f[x][1])%p; f[x][1]=-f[x][0]; } // printf("%d %d %d %d\n",x,f[x][0],f[x][1],f[x][2]); } void mian(){ scanf("%d%d",&n,&k);tot=1;memset(lst,0,sizeof(lst));memset(vis,0,sizeof(vis)); memset(cnt,-1,sizeof(cnt)); for(i=1;i