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:
Works with negative numbers.
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⁵