Problem: renovations (2019 round3)

A family of four moles lives in an underground burrow. Each of them has an
important role to play! Daddy Mole is in charge of renovating the burrow.
Mommy Mole fixes up Daddy Mole's inevitable mistakes. And Brother Mole and
Sister Mole mostly lie around playing video games.

Their burrow consists of **N** little underground rooms, numbered from 1 to
**N**. Room 1 is connected to the surface, and for each other room _i_ (such
that 2 ≤ _i_ ≤ **N**), the room initially "above" room _i_ is room **Pi**,
meaning that there's a tunnel leading downwards from room **Pi** to room _i_,
which may be traversed in either direction. It's guaranteed that it's possible
to reach each room from room 1 by travelling through a sequence of tunnels.

Daddy Mole will renovate the burrow **K** times in a row. For each renovation
in turn, he'll independently randomly select a room _i_ aside from room 1
(such that 2 ≤ _i_ ≤ **N**), with each such room having an equal 1 / (**N** \-
1) probability of being chosen each time. He'll then "improve" the burrow's
architectural design by simply caving in the tunnel connecting node _i_ and
the room currently above it, causing that tunnel to no longer exist. Mommy
Mole will then immediately salvage the situation by creating a new tunnel
leading downwards from room 1 to room _i_ (such that the room above _i_ will
now be room 1). This may result in Mommy Mole recreating exactly the same
tunnel that Daddy Mole had just caved in. Note that, in the resulting burrow,
each room will always once again be reachable from room 1.

After these **K** random renovations have been completed, Brother Mole (who
hangs out in room **A**) will go visit Sister Mole in her room (room **B**) to
show off his latest video game high score. He'll travel along the unique
sequence of tunnels which will get him there without passing through any rooms
multiple times, at a speed of 1 tunnel per minute. What's the expected amount
of time this will take him?

Let this expected time (in minutes) be represented as a quotient of integers
**p/q** in lowest terms. Output the value of this quotient modulo
1,000,000,007 — in other words, output the unique integer **x** such that 0 ≤
**x** < 1,000,000,007 and **p** = **x*****q** (modulo 1,000,000,007).

### Input

Input begins with an integer **T**, the number of burrows. For each burrow,
there is first a line containing the space-separated integers **N**, **K**,
**A**, and **B**. Then, **N** \- 1 lines follow, the _i_th of which contains
the integer **Pi+1** (starting with **P2**).

### Output

For the _i_th burrow, print a line containing "Case #_i_: " followed by a
single integer, the expected number of minutes required for Brother Mole to
travel from room **A** to room **B** after **K** renovations, expressed as a
quotient of integers modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 70  
2 ≤ **N** ≤ 6,000  
0 ≤ **K** ≤ 2,000,000  
1 ≤ **A**, **B**, **Pi** ≤ **N**  
**A** ≠ **B**   

### Explanation of Sample

In the first case, if Daddy Mole chooses room 2 for his single renovation
(caving in the tunnel between rooms 2 and 3), then Mommy Mole will dig a
tunnel between rooms 1 and 2, and Brother Mole will then need 2 minutes to
travel from room 2 to room 3 (passing through room 1 along the way).
Otherwise, if Daddy Mole chooses node 3, then Mommy Mole will restore the
burrow to its original state, and Brother Mole will be able to reach room 3
directly in 1 minute. These two possibilities are equally likely, resulting in
an expected time of (2+1)/2 = 3/2 = 500000005 (modulo 1,000,000,007) minutes.

In the second case, no matter which room Daddy Mole chooses for each
renovation, Mommy Mole will recreate the tunnel that he caves in, resulting in
Brother Mole's trip taking 2 minutes after any number of renovations.



Sample input:
7
3 1 2 3
3
1
3 2000000 2 3
1
1
6 0 5 3
1
1
2
2
4
6 2 5 3
1
1
2
2
4
6 3 1 6
5
4
5
1
3
6 3 2 4
5
4
5
1
3
16 123456 3 14
5
11
6
16
13
1
14
15
13
12
2
7
10
4
9


Sample output:
Case #1: 500000005
Case #2: 2
Case #3: 3
Case #4: 480000006
Case #5: 744000007
Case #6: 344000005
Case #7: 575944518



Code: // Renovations
// 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 6001
#define MOD 1000000007

int N,K;
int expMem[LIM];

int Exp(int a,int b)
{
		if ((a<N) && (b==K) && (expMem[a]))
			return(expMem[a]);
	LL p=a,v=1;
		while (b)
		{
				if (b&1)
					v=v*p%MOD;
			p=p*p%MOD;
			b>>=1;
		}
		if ((a<N) && (b==K))
			expMem[a]=v;
	return(v);
}

void Add(int &a,int b)
{
	a=(a+b)%MOD;
}

int Prod(int a,int b)
{
	return((LL)a*b%MOD);
}

void Div(int &a,int b)
{
	a=Prod(a,Exp(b,MOD-2));
}

// # of sequences with f forbidden nodes, r required nodes
int Count(int f,int r)
{
	int v=N-f-1;
	int c=Exp(v,K);
		if (!r)
			return(c);
		if (r==1)
			return((c-Exp(v-1,K)+MOD)%MOD);
	return((c-(LL)2*Exp(v-1,K)%MOD+Exp(v-2,K)+MOD)%MOD);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int L,A,B;
	int i,dA,dB,dL;
	int P[LIM]={-1};
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// init
			Fill(expMem,0);
			// input
			Read(N),Read(K),Read(A),Read(B),A--,B--;
				Fox1(i,N-1)
					Read(P[i]),P[i]--;
			// compute depths of A, B, and their LCA
			queue<int> qA,qB;
				for (dA=0; A>=0; A=P[A],dA++)
					qA.push(A);
				for (dB=0; B>=0; B=P[B],dB++)
					qB.push(B);
			dL=max(dA,dB);
				for(;;)
				{
						if (qA.front()==qB.front())
							break;
					dL--;
						if (Sz(qA)>dL)
							qA.pop();
						if (Sz(qB)>dL)
							qB.pop();
				}
			dL--,dA--,dB--;
			// consider all possible final states
			int ans=0;
				if (!dL) // original LCA is the root?
				{
					Fox(A,dA+1)
						Fox(B,dB+1)
						{
								if ((dA) && (!A) || (dB) && (!B))
									continue;
							Add(ans,Prod(A+B,Count(A+B-(A?1:0)-(B?1:0),(A<dA?1:0)+(B<dB?1:0))));
						}
				}
				else
				{
					// consider LCA being retained
						Fox1(L,dL)
							Add(ans,Prod(dA+dB-2*dL,Count(dA+dB-2*dL+L-1,(L<dL ? 1 : 0))));
					// consider LCA being broken
						Fox1(A,dA)
							Fox1(B,dB)
							{
									if ((A>dA-dL) && (B>dB-dL))
										continue;
								Add(ans,Prod(A+B,Count(A+B-2,(A<dA?1:0)+(B<dB?1:0))));
							}
				}
			// divide by total number of sequences
			Div(ans,Exp(N-1,K));
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}