<p>You are an ant tasked with adding <code>n</code> new rooms numbered <code>0</code> to <code>n-1</code> to your colony. You are given the expansion plan as a <strong>0-indexed</strong> integer array of length <code>n</code>, <code>prevRoom</code>, where <code>prevRoom[i]</code> indicates that you must build room <code>prevRoom[i]</code> before building room <code>i</code>, and these two rooms must be connected <strong>directly</strong>. Room <code>0</code> is already built, so <code>prevRoom[0] = -1</code>. The expansion&nbsp;plan is given such that once all the rooms are built, every room will be reachable from room <code>0</code>.</p>

<p>You can only build <strong>one room</strong> at a time, and you can travel freely between rooms you have <strong>already built</strong> only if they are <strong>connected</strong>.&nbsp;You can choose to build <strong>any room</strong> as long as its <strong>previous room</strong>&nbsp;is already built.</p>

<p>Return <em>the <strong>number of different orders</strong> you can build all the rooms in</em>. Since the answer may be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/19/d1.JPG" style="width: 200px; height: 212px;" />
<pre>
<strong>Input:</strong> prevRoom = [-1,0,1]
<strong>Output:</strong> 1
<strong>Explanation:</strong>&nbsp;There is only one way to build the additional rooms: 0 &rarr; 1 &rarr; 2
</pre>

<p><strong class="example">Example 2:</strong></p>
<strong><img alt="" src="https://assets.leetcode.com/uploads/2021/06/19/d2.JPG" style="width: 200px; height: 239px;" /></strong>

<pre>
<strong>Input:</strong> prevRoom = [-1,0,0,1,2]
<strong>Output:</strong> 6
<strong>Explanation:
</strong>The 6 ways are:
0 &rarr; 1 &rarr; 3 &rarr; 2 &rarr; 4
0 &rarr; 2 &rarr; 4 &rarr; 1 &rarr; 3
0 &rarr; 1 &rarr; 2 &rarr; 3 &rarr; 4
0 &rarr; 1 &rarr; 2 &rarr; 4 &rarr; 3
0 &rarr; 2 &rarr; 1 &rarr; 3 &rarr; 4
0 &rarr; 2 &rarr; 1 &rarr; 4 &rarr; 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == prevRoom.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>prevRoom[0] == -1</code></li>
	<li><code>0 &lt;= prevRoom[i] &lt; n</code> for all <code>1 &lt;= i &lt; n</code></li>
	<li>Every room is reachable from room <code>0</code> once all the rooms are built.</li>
</ul>
class Solution:
    def waysToBuildRooms(self, prevRoom: List[int]) -> int:
        # room zero built
        # must build prevRoom[i] before i
        
        # once you've built prevRoom[i] at some point you can build i
        #    i must be appended as a child to prevRoom[i] directly

        # 0 is already built

        # n is 1e5 at most so DFS+BT is out, so is top-down DFS + caching, etc.

        # prevRoom req is probably a topological ordering thing

        # so suppose we've built rooms 0, a, b, c, ... so far
        
        # we know that if we build room x next, then all elements with prevRoom[i] == x must be children, which helps

        # so ways to build x are
        #     > we can build the children in any way: product of ways[y] where prevRoom[y] == x
        #     > we can build the children in any order: *= numChildren factorial

        # we know all rooms are connected ultimately to 0 per problem statement so the final ways(0) will save us

        # UPDATE: the above isn't quite true
        #    if the left subtree has 2 elements, and the right subtree has two elements:
        #       we can build left then right, or right then left (I had this)
        #       but we can also interleave the elements, yikes
        #
        # so we're missing the interleaved stuff. Suppose we have ways(left) and ways(right) as I intended: the ways we
        # can do the appending of elements to each subtree individually
        # then for k children of sizes s1 .. sk we can
        #    > permute the s1 .. sk append operations in any order, i.e. all distinct patterns of s1 appendToFirstChild .. sk appendToKthChild
        #    > then multiply by the ways of sequencing the s1 appends to first child, and second child, etc.
        #
        # So we need totalChildren! / s1! / s2! / ...
        # and thus we need modular multiplicative inverses for each factorial, yikes

        # fixed stuff
        BIG = 10**9 + 7

        __fm = [1]
        def factmod(n: int) -> int:
            """Returns n! mod BIG"""
            while len(__fm)-1 < n:
                __fm.append(len(__fm)*__fm[-1] % BIG) # append 2!, 3!, ... n!

            return __fm[n]

        _mminv = []
        def mmInvFact(n: int) -> int:
            """Returns the modular multiplicative inverse of n! mod BIG"""

            while len(_mminv)-1 < n:
                _mminv.append(0)

            if _mminv[n] == 0:
                # TODO: replace with Extended Euclidean for speed, but this will do nicely
                _mminv[n] = pow(factmod(n), BIG-2, BIG) # n!**(BIG-2) % BIG, long story, Euler's Theorem, proved with set bijection, Bezout's, pigeonhole

            return _mminv[n]


        # preliminaries, problem-dependent
        N = len(prevRoom)

        adj = [[] for _ in range(N)]
        for r in range(1, N):
            p = prevRoom[r]
            adj[p].append(r)

        # no caching: each room has one predecessor room (?) so this is called once per room
        def ways(room: int) -> tuple[int, int]:
            """Returns (ways, sizeOfTree)"""

            if not adj[room]:
                return 1, 1

            w = 1
            c = 0

            # total ways is numChildren! / s1! / ... / sk! * ways(child1) * .. * ways(child_k)
            for child in adj[room]:
                w_i, s_i = ways(child)
                w *= w_i # * ways(child_i) part
                w %= BIG
                w *= mmInvFact(s_i) # / s_i! part
                w %= BIG

                c += s_i

            # c is total children
            w *= factmod(c) # final numChildren!
            w %= BIG

            return w, c+1 # size of this tree is numChildren + 1

        ans, _ = ways(0)
        return ans
1529