n rooms numbered 0 to n - 1. Room 0 already exists. For every other room i, the plan gives parent[i], the room that i is dug right next to; room i can be built only once parent[i] is finished. For room 0, parent[0] = -1.
Rooms are built one at a time, and at any moment you may pick any room whose parent room is already built. The plan guarantees that in the end every room is connected to room 0.
Count the different orders in which all the rooms can be built. The answer can be large, so return it modulo 10⁹ + 7.parent=[-1, 0, 0] → 2
Rooms 1 and 2 both attach to room 0, so they can be built in either order: 1 → 2 or 2 → 1.
parent=[-1, 0, 0, 1] → 3
The valid orders are 1 → 2 → 3, 1 → 3 → 2 and 2 → 1 → 3: room 3 always comes after room 1.
parent=[-1, 0, 1, 2] → 1
The rooms form a chain, so there is exactly one order.
parent=[-1, 0, 0]
2
Run checks the first 3 tests in your browser. Submit checks all 91 tests on the server, hidden ones included.