The Queue - LightOJ

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int mod = 1e9 + 7, N = 1e3;
int C[N + 1][N + 1];
vector<int> Adj[N + 1];
int n, deg[N + 1], cnt[N + 1];
long long dp[N + 1];
void prepare()
{
    C[0][0] = 1;
    for (int i = 1; i <= N; ++ i)
    {
        for (int j = 0; j <= i; ++ j)
        {
            if (j == 0 || j == i)
            {
                C[i][j] = 1;
            }
            else
            {
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
            }
        }
    }
}
void read()
{
    cin >> n;
    for (int i = 1; i < n; ++ i)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].push_back(v);
        ++deg[v];
    }
}
void DFS(int u)
{
    cnt[u] = 0;
    dp[u] = 1;
    vector<int> Child;
    for (int v : Adj[u])
    {
        DFS(v);
        cnt[u] += cnt[v];
        dp[u] *= dp[v];
        dp[u] %= mod;
        Child.push_back(cnt[v]);
    }
    int check = cnt[u];
    for (int c : Child)
    {
        dp[u] *= C[check][c];
        check -= c;
        dp[u] %= mod;
    }
    ++cnt[u];
}
void solve()
{
    for (int i = 1; i <= n; ++ i)
    {
        if (deg[i] == 0)
        {
            DFS(i);
            cout << dp[i] << '\n';
        }
    }
    for (int i = 1; i <= n; ++ i)
    {
        Adj[i].clear();
        deg[i] = 0;
    }
}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   if (fopen(TASK".INP", "r"))
   {
      freopen(TASK".INP", "r", stdin);
      //freopen(TASK".OUT", "w", stdout);
   }
   prepare();
   int t = 1;
   bool typetest = true;
   if (typetest)
   {
      cin >> t;
   }
   for (int __ = 1; __ <= t; ++ __)
   {
      cout << "Case " << __ << ": ";
      read();
      solve();
   }
}