[Codemarshal] A. Tree Mania

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : A. Tree Mania
Source            : Codemarshal
                    SUB IUPC 2015
Category          : Combinatorics
Algorithm         : Prufer Code
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 2e5 + 5;  
static const long long mod = 1e9 + 7;  
  
long long binaryExpo(long long a, long long p, long long m)  
{  
      if (p <= 0) return 1 % m;  
      if (p == 1) return a % m;  
      if (p & 1) return (a % m * binaryExpo(a, p - 1, m)) % m;  
      long long ret = binaryExpo(a, p / 2, m);  
      return (ret % m * ret % m) % m;  
}  
  
long long modInv(long long a, long long m)  
{  
      return binaryExpo(a, m - 2, m);  
}  
  
long long fact[maxn];  
long long ifact[maxn];  
long long deg[maxn];  
  
void preCalc()  
{  
      fact[0] = 1LL;  
      ifact[0] = 1LL;  
      for (int i = 1; i < maxn; i++)  
      {  
            fact[i] = (1LL * i * fact[i - 1]) % mod;  
            ifact[i] = modInv(fact[i], mod);  
      }  
}  
  
long long nCr(int n, int r)  
{  
      if (n < r) return 0;  
      long long x = fact[n];  
      long long y = (ifact[r] * ifact[n - r]) % mod;  
      long long ncr = (x * y) % mod;  
      return ncr;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      preCalc();  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            int n;  
            cin >> n;  
            int sum = 0;  
            for (int i = 1; i <= n - 2; i++)  
            {  
                  cin >> deg[i];  
                  sum += deg[i];  
            }  
            long long ans = 1;  
            int N = n - 2;  
            for (int i = 1; i <= n - 2; i++)  
            {  
                  long long x = nCr(N, deg[i] - 1);  
                  ans = (ans * x) % mod;  
                  N -= (deg[i] - 1);  
            }  
            int loop = 2 * (n - 1) - sum;  
            long long binomial = binaryExpo(2, loop - 2, mod);  
            long long totalTree = (ans * binomial) % mod;  
            cout << "Case " << tcase << ": " << totalTree << '\n';  
      }  
}