TOI19 Explorer

/*
    Task    : _example
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 05 June 2023 [19:35]
*/
#include<bits/stdc++.h>
#define MOD (long long )(1e9 + 7)
using namespace std;
vector<int > g[500010];
long long fact[500010];
long long dfs(int currentNode, int parent){
    if(g[currentNode].size() == 0)
        return 1;
    if(g[currentNode].size() == 1 && g[currentNode][0] == parent)
        return 1;
    long long ret = 1;
    int cnt = 0;
    for(auto x:g[currentNode]){
        if(x == parent) continue;
        cnt++;
        ret*=dfs(x,currentNode);
        ret%=MOD;
    }
    ret = (ret*fact[cnt])%MOD;
    return ret;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int n,last = 0,num;
    cin >> n >> last;
    for(int i=2;i<=2*n-1;i++){
        cin >> num;
        g[last].push_back(num);
        last = num;
    }
    fact[0] = fact[1] = 1;
    for(int i=2;i<=n;i++){
        fact[i] = (fact[i-1]*i)%MOD;
    }
    cout << dfs(last,0) << '\n';
    return 0;
}