#include #include #include #include #include #include #include #include #include #include #include #define ll long long using namespace std; #define her1 20081214 #define cht 1000000007 #define IV void #define ull unsigned long long #define mem(x,val) memset(x,val,sizeof x) #define F(i,j,n)for(register int i=j;i<=n;i++) #define D(i,j,n)for(register int i=j;i>=n;i--) #define E(i,now)for(register int i=first[now];i;i=e[i].nxt) #define FL(i,j,n)for(register i64 i=j;i<=n;i++) #define DL(i,j,n)for(register i64 i=j;i>=n;i--) #define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt) ll read(){ ll ans=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar(); return ans*f; } #undef ll #include "assert.h" mt19937_64 rnd(her1); #include "functional" using i64 = long long; const int MAX = 1e5; const int maxn = 1e5+5;bool vis[maxn]; IV cadd(i64&x,i64 val){x=(x+val)%cht;} i64 n,k,x[maxn],y[maxn],fac[maxn];vector >G[maxn]; i64 tmp[3][2][2],ntmp[3][2][2],f[maxn][2][2],Ans; IV dfs(i64 u,i64 F){ mem(f[u],0);for(auto[v,id]:G[u])if(v^F)dfs(v,u); if(G[u].size()==1){f[u][0][1]=1;return;} mem(tmp,0);tmp[0][0][1]=1; for(auto[v,id]:G[u])if(v^F){ mem(ntmp,0); F(x,0,2)F(np,0,1)F(nq,0,1)F(p,0,1)cadd(ntmp[x][np][nq],tmp[x][np][nq]*f[v][p][1]); F(x,0,1)F(np,0,1)F(nq,0,1){ F(p,0,1)F(q,0,1)if(q||nq){ if(!p&&!q)continue; cadd(ntmp[x+1][np|p|(q&&vis[id])][q&nq],tmp[x][np][nq]*f[v][p][q]); } } F(x,0,2)F(np,0,1)F(nq,0,1)tmp[x][np][nq]=ntmp[x][np][nq]; } // if(u==5){ // F(x,0,1)F(y,0,1){ // cout<1)rt=i;dfs(rt,0); // cout<1)Ans=Ans*fac[G[i].size()-2]%cht; printf("%lld\n",(Ans+cht)%cht); } IV init(){ fac[0]=1; F(i,1,MAX)fac[i]=fac[i-1]*i%cht; } int main(){ freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); init();read();i64 T=read();while(T--)solve();return 0; }