Counting Valid Multi‐ary Min‐Heap Labelings

A multi‐ary heap is a tree data structure. In this problem we only consider a min‐heap with the following properties:

• Except for the root, every node has a weight that is not less than the weight of its parent.
• Every non‐leaf node has at least one child.

Initially, there are \(n\) nodes numbered from \(0\) to \(n-1\). Each node forms a single‐node tree (so each node is the root of its own tree). Then, there are \(q\) operations performed in order. There are two types of operations:

1. 1 x y: Choose nodes \(x\) and \(y\) from two different trees. Let \(r_x\) be the root of the tree containing \(x\) and \(r_y\) be the root of the tree containing \(y\). Attach the tree rooted at \(r_x\) directly under \(r_y\> (i.e. make \(r_x\) a child of \(r_y\)).
2. 2 x: Choose a node \(x\). Let \(size\) be the number of nodes in the tree containing \(x\). You are to compute the number of different min‐heap labelings possible if the numbers \(0, 1, \ldots, size-1\) are assigned to the nodes of this tree (each number used exactly once). Two heaps are considered different if there exists at least one node which receives a different value.

For the assignment to be valid, the values must satisfy the heap property: if a node is not the root, then its value is not less than the value of its parent.

The answer for each query of type 2 should be output modulo \(10^9+7\).

Hint: For a fixed tree structure with \(n\) nodes, if the root has children corresponding to subtrees with sizes \(s_1, s_2, \ldots, s_k\), then the number of valid labelings is given by:

[ f(root) = \binom{n-1}{s_1, s_2, \ldots, s_k} \times \prod_{i=1}^{k} f(child_i), ]

where the multinomial coefficient is defined as:

[ \binom{n-1}{s_1, s_2, \ldots, s_k} = \frac{(n-1)!}{s_1!, s_2!, \cdots, s_k!}. ]

</p>

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \leq n, q \leq 10^5)\), representing the number of nodes and the number of operations, respectively.

Then \(q\) lines follow. Each line represents an operation in one of the following formats:

• 1 x y : Attach the tree containing \(x\) to the tree containing \(y\). It is guaranteed that \(x\) and \(y\) are in different trees. \(0 \le x, y < n\).
• 2 x : Query the number of valid min‐heap labelings for the tree containing \(x\). \(0 \le x < n\).

outputFormat

For each operation of type 2, output the corresponding answer (the number of different valid labeling ways modulo \(10^9+7\)) on a separate line.

sample

5 6
1 0 1
2 0
1 2 1
2 2
1 3 4
2 3

1
2
1

</p>