Description
Given a tree representing ant colony rooms, count valid orderings to build all rooms respecting parent-child order. Return count modulo 10^9+7.
Examples
Input:
prevRoom = [-1,0,1]Output:
1Explanation:
Only one valid order.
Input:
prevRoom = [-1,0,0,1,2]Output:
6Explanation:
Room 0 is root with children 1 and 2. Room 3 depends on 1, room 4 depends on 2. After building room 0, It is possible to interleave the two subtrees in 6 different valid orderings.
Input:
prevRoom = [-1,0,0,1,1]Output:
8Explanation:
Room 0 must be built first. Respecting all dependencies, there are 8 valid build orderings.
Constraints
- •
1 ≤ n ≤ 10⁵