<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:
        # make a tree map of the previous rooms by enumeration of prevRoom 
        tree = collections.defaultdict(list)
        for index, room in enumerate(prevRoom) : tree[room].append(index)

        # dfs based on node id, where if node id is not recorded, there are 1 nodes and 1 way to build a leaf node
        def dfs(node_id) : 
            if not tree[node_id] : return 1, 1
            else : 
                # otherwise, we start with 0 num nodes and 1 way to build 
                num_nodes, ways_to_build = 0, 1 
                # and recursively consider all neighbor nodes of this node in the tree 
                for neighbors_id in tree[node_id] : 
                    # where for each neighbor, we conduct this same dfs 
                    neighbors_num_nodes, neighbors_ways = dfs(neighbors_id)
                    # updating our number of nodes by incrementation 
                    num_nodes += neighbors_num_nodes
                    # then calculating ways to build as the multiplication of self with n choose k where 
                        # n is number of nodes inclusive of current neighbors and k is neighbors num nodes 
                        # this represents how many ways we can build neighbors num nodes based on the current num nodes 
                        # and then multiply by neighbors ways for each of the ways the neighbors can build 
                    # this then in total represents the ways to build n choose k * multiple of neighbors methods 
                    # this increases as num_nodes increases, and is bound by modulo as well internally. Could be bound externally 
                    ways_to_build = (ways_to_build * math.comb(num_nodes, neighbors_num_nodes) * neighbors_ways) % 1_000_000_007
                # at end, return num nodes + 1 and ways to build 
                return num_nodes + 1, ways_to_build

        # recursive walk through of Example 2 
        '''
            previousRooms generates Tree as 
            Tree -> 
                -1  : [0]
                0   : [1, 2]
                1   : [3]
                2   : [4] 
            
            Call dfs using 0 as node_id 
                0 is in tree, so we continue 
                num nodes = 0, ways to build = 1 
                for neighbors_id in tree[0] -> for neighbors in [1, 2] 
                    neighbors_id = 1 
                        neighbors_num_nodes, neighbors_ways = dfs(1)
                            dfs(1) -> 1 in tree, so continue 
                            num_nodes_1, ways_to_build_1 = 0, 1 
                            for neighbors_id in [3] 
                                neighbors_num_nodes, neighbors_ways = 1, 1 (3 is a leaf) 
                                num_nodes_1 = 1 
                                ways_to_build_1 = (1 * 1 C 1 * 1) % mod = 1 
                            return 1+1, 1 
                        neighbors_num_nodes, neighbors_ways = 2, 1 
                        num_nodes = 2
                        ways_to_build = (1 * 2 C 2 * 1) % mod = 1 
                    neighbors_id = 2 
                        dfs(2) -> will return 2, 1 
                        num_nodes = 4 
                        ways to build = (1 * 4 C 2 * 1) % mod = 6 
                            4 C 2 is six as from [a, b, c, d] you have [a, [b, c, d]], [b, [c, d]], [c, d], where the second [] means choose one from
                return then 5, 6 (5 nodes, 6 ways to build)
        '''
        # return the number of ways to build the rooms 
        return dfs(0)[1]
1563