hackercupai/hackercup huggingface dataset:
H Combinator (HC) is a business incubator that provides seed funding to startups. It operates on the core value that "nothing is somebody else's problem" (since businesses slow down when tasks get perpetually passed from person to person). HC currently supports \(T\) companies. As a managing director hoping to weed out some bad investments, you would like to assess how well the structure of each company holds up to this important principle.

Suppose a company has \(N\) employees, numbered \(1\) to \(N\) in decreasing order of seniority. Employee \(1\) is the CEO, while each other employee \(i\) \((i \ge 2)\) has a manager, employee \(M_i\) \((M_i \lt i)\).

When employee \(i\) is assigned a task to complete, they may instead reassign it to one of the following employees:

1. One of their direct reports (any employee \(j\) such that \(M_j = i\)), if any exist
2. Their manager (employee \(M_i\)), if \(i \ge 2\)
3. The CEO (employee \(1\)), if \(i \ge 2\)

That employee may then reassign the task to yet another employee, and so on. However, an employee may never be reassigned a task that has ever been previously assigned to them, as the lack of responsibility would become too apparent. For example, an employee and manager cannot repeatedly pass a task back and forth.

Let \(R_i\) be the maximum number of times that a task could be reassigned from one employee to another if it were initially assigned to employee \(i\). For each company, you would like to calculate the product \((R_1 * R_2 * ... * R_N)\), modulo 1,000,000,007.

# Constraints

\(1 \le T \le 100\)
\(2 \le N \le 1,000,000\)
\(1 \le M_i \lt i\)

The sum of \(N\) across all companies is at most 6,000,000.

# Input

Input begins with an integer \(T\), the number of companies. For each company there are 2 lines. The first line contains the single integer \(N\). The second line contains \(N - 1\) space-separated integers, \(M_{2..N}\).

# Output

For the \(i\)th company, print a line containing *"Case #i: "*, followed by a single integer, the product of \(R_{1..N}\) modulo 1,000,000,007.

# Explanation of Sample

For the first company, if the CEO is initially assigned a task, all they can do is reassign it to one of their reports, who cannot then assign it back. On the other hand, if another employee is initially assigned a task, they can reassign it to the CEO, who can then assign it to the other remaining employee. Therefore, \(R = [1, 2, 2]\), and the final answer is (1 * 2 * 2) modulo 1,000,000,007 = 4.

For the second company, no matter which employee is initially assigned a task, it can then be reassigned twice. For example, employee 2 can assign their task to their report (employee 3), who can then assign it to the CEO. Therefore, \(R = [2, 2, 2]\).

For the third company, \(R = [2, 2, 3, 3]\).

For the fourth company, \(R = [3, 6, 6, 6, 7, 7, 7, 7, 8, 8]\).

For the fifth company, \(R = [4, 6, 6, 7, 8, 6, 7, 7, 8, 7, 7, 8, 8, 9, 9]\).