Problem: chain_of_command (2019 round3)

At last, Mr. X has managed to return to the school at which he formerly
taught, with the intention of confronting his suspicious successor, Mr. Y.
However, it appears that Mr. Y has fortified his position — he has brainwashed
all of his students into believing that he's the world's best teacher through
the timeless ploy of replacing classes with extra recesses. There's no way
that Mr. Y can be thrown out of the school without first compromising his
students' support!

There are **N** students in Mr. Y's class, with IDs from 1 to **N**. In an
attempt to maximize security, Mr. Y has arranged them into a hierarchical
structure, with each student _i_ either reporting to a commanding student
**Ci**, or not reporting to any other student (indicated by **Ci** = 0).
There's exactly one student _i_ for whom **Ci** = 0, who is the class leader.

A _chain of command_ is a sequence of one or more students going up the
hierarchical structure starting from some student _i_ and ending somewhere
between _i_ and the class leader (inclusive): _i_ → **Ci** → **CCi** → etc.
It's guaranteed that, for each student _i_, there exists a _chain of command_
beginning at them and ending at the class leader.

Initially, all **N** students are under Mr. Y's control. However, Mr. X is
about to perform some bribery of his own. One by one, in order from 1 to
**N**, Mr. X will bribe each student with healthy snacks. After the first _b_
bribes, students 1.._b_ will be under Mr. X's control instead of Mr. Y's.

After each of the **N** bribes, Mr. X would like to evaluate the vulnerability
of Mr. Y's class to a potential takeover. To do so, he'll determine **N**
hypothetical values: for each student _i_, he'll compute the maximum length
that a _controlled chain_ beginning with student _i_ could possibly have if 0
or more _promotions_ were to first take place (or 0 if no such chain could
exist).

A _controlled chain_ is a _chain of command_ consisting exclusively of
students under Mr. X's control. A _promotion_ is a modification to the class
structure in which Mr. X selects a certain student _j_ with a commanding
student _c_ = **Cj** (such that _c_ ≠ 0 and _c_ ≠ _i_), expels student _c_
(removing them from the class entirely), and brings _j_ up to occupy _c_'s
former place (setting **Cj** to **Cc**, and for each other student _k_ such
that **Ck** = _c_, now setting **Ck** to j). Note that each of these
hypothetical values should be considered independently of the others; Mr. X
will never actually perform any _promotions_ and permanently alter the class
structure.

In order to reduce the size of the output, these **N2** values should be
aggregated into a single integer as follows: Letting **Sb** be the sum of the
**N** students' maximum _controlled chain_ lengths after the first _b_
students have been bribed, output (**S1** * **S2** * ... * **SN**) modulo
1,000,000,007.

### Input

Input begins with an integer **T**, the number of times Mr. X needs to wrest
control from Mr. Y. For each time, there is first a line containing the
integer **N**. Then, **N** lines follow, the _i_th of which contains the
integer **Ci**.

### Output

For the _i_th time, print a line containing "Case #_i_: " followed by a single
integer, the product of all **N** sums of maximum _controlled chain_ lengths,
modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 80  
1 ≤ **N** ≤ 800,000  
0 ≤ **Ci** ≤ **N**  

### Explanation of Sample

In the first case, after the first student has been bribed, a length-1
_controlled chain_ can begin at student 1, while no _controlled chain_ can
begin at student 2. Once the second student has also been bribed, a length-1
_controlled chain_ can still begin at student 1, while a length-2 _controlled
chain_ may now begin at student 2 (2 → 1). This results in a total answer of
(1 + 0) * (1 + 2) = 3 (modulo 1,000,000,007).

In the second case, after the first two students have been bribed, a length-2
_controlled chain_ can begin at student 1 (1 → 2) if student 1 gets promoted
(replacing student 3). The total answer comes out to (1 + 0 + 0) * (2 + 1 + 0)
* (3 + 1 + 2) = 18 (modulo 1,000,000,007).

In the third case, after the first two students have been bribed, a length-2
_controlled chain_ may begin at student 1 (1 → 2) if student 2 gets promoted
(replacing student 3), and a length-1 _controlled chain_ can similarly begin
at student 2 (2 → 1) if student 1 gets promoted (replacing student 3). The
total answer comes out to (1 + 0 + 0) * (2 + 2 + 0) * (2 + 2 + 1) = 20 (modulo
1,000,000,007). _

In the fourth case, the total answer is (1 + 0 + 0 + 0 + 0) * (2 + 2 + 0 + 0 +
0) * (2 + 3 + 2 + 0 + 0) * (2 + 3 + 2 + 1 + 0) * (2 + 3 + 2 + 1 + 3) = 2464
(modulo 1,000,000,007).

In the fifth case, the total answer is 1 * 3 * 7 * 11 * 14 * 16 * 20 * 28 * 33
* 39 * 44 * 47 = 790446393 (modulo 1,000,000,007).



Sample input:
5
2
0
1
3
3
0
2
3
3
3
0
5
4
3
4
0
3
12
7
8
6
3
6
2
6
0
5
4
7
2


Sample output:
Case #1: 3
Case #2: 18
Case #3: 20
Case #4: 2464
Case #5: 790446393



Code: // Chain of Command
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 800001
#define MOD 1000000007

int N;
LL curSum;
int ind,sz[LIM],in[LIM],out[LIM],nxt[LIM];
int C[LIM],S[LIM];
int BLT[2][LIM]; // 0: B, 1: X
bool X[LIM],hasSetXUpward[LIM];
vector<int> ch[LIM],unsetXch[LIM];

void RecCalcSz(int i)
{
	int j;
	sz[i]=1;
		Fox(j,Sz(ch[i]))
		{
			int c=ch[i][j];
			RecCalcSz(c);
			sz[i]+=sz[c];
				if(sz[c]>sz[ch[i][0]])
					swap(ch[i][0],ch[i][j]);
		}
}

void RecHLD(int i)
{
	in[i]=ind++;
	int j;
		Fox(j,Sz(ch[i]))
		{
			int c=ch[i][j];
			nxt[c]=j ? c : nxt[i];
			RecHLD(c);
		}
	out[i]=ind;
}

void IncBLT(int b,int i)
{
	for (i++; i<=N; i+=(i&-i))
		BLT[b][i]++;
}

int QueryBLT(int b,int i)
{
	int s=0;
		for (i++; i>0; i-=(i&-i))
			s+=BLT[b][i];
	return(s);
}

int QueryBInSubtree(int i)
{
	return(QueryBLT(0,out[i]-1)-QueryBLT(0,in[i]-1));
}

int QueryXToRoot(int i)
{
	int x=1;
		while (i>=0)
		{
			int a=nxt[i];
			x+=QueryBLT(1,in[i])-QueryBLT(1,in[a]-1);
			i=C[a];
		}
	return(x);
}

void SetX(int i)
{
		if (X[i])
			return;
	X[i]=1;
	IncBLT(1,in[i]);
	curSum+=QueryBInSubtree(i);
}

void Bribe(int i)
{
	int j;
	IncBLT(0,in[i]);
	curSum+=QueryXToRoot(i);
		Fox(j,Sz(ch[i]))
			SetX(ch[i][j]);
		for(;;)
		{
				if (hasSetXUpward[i])
					break;
			hasSetXUpward[i]=1;
			int c=C[i];
				if (c<0)
					break;
				Fox(j,Sz(unsetXch[c]))
					if (unsetXch[c][j]!=i)
						SetX(unsetXch[c][j]);
			unsetXch[c].clear();
			unsetXch[c].pb(i);
			i=c;
		}
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int i,r;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// init
				Fox(i,N)
				{
					ch[i].clear();
					unsetXch[i].clear();
				}
			// input
			Read(N);
				Fox(i,N)
				{
					Read(C[i]),C[i]--;
						if (C[i]<0)
							r=i;
						else
						{
							ch[C[i]].pb(i);
							unsetXch[C[i]].pb(i);
						}
				}
			// perform heavy-light decomposition
			ind=0;
			RecCalcSz(r);
			nxt[r]=r;
			RecHLD(r);
			// init
			curSum=0;
			Fill(BLT,0);
			Fill(X,0);
			Fill(hasSetXUpward,0);
			// process bribes
			int ans=1;
				Fox(i,N)
				{
					Bribe(i);
					ans=ans*(curSum%MOD)%MOD;
				}
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}