给您一棵包含 $$$n$$$ 节点和 $$$q$$$ 查询的树。
每个查询都以三个整数 $$$k$$$、$$$m$$$ 和 $$$r$$$ 开头,后跟 $$$k$$$ 树 $$$a_1、a_2、\ldots、a_k$$$ 的节点。要回答查询,假设树的根位于 $$$r$$$。我们希望将 $$$k$$$ 给定节点划分为最多 $$$m$$$ 组,以满足以下条件:
- 每个节点都应该属于一组,并且每个组应该至少有一个节点。
- 在任何组中,不应存在两个不同的节点,以致一个节点是另一个节点的祖先(直接或间接)。
您需要为每个查询输出模 $$$10^{9}+7$$$ 的路数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 10^{5}$$$) - 分别是树中的顶点数和查询数。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$),表示连接顶点 $$$u$$$ 和顶点 $$$v$$$ 的边。保证给定的图是一棵树。
接下来的 $$$q$$$ 行均以三个整数 $$$k$$$、$$$m$$$ 和 $$$r$$$ 开头 ($$$1 \le k, r \le n$$$, $$$1 \le m \le min(300,k)$$$) — 分别表示当前查询的节点数、最大组数和树的根。它们后面跟着 $$$k$$$ 不同的整数 $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_i \le n$$$),表示当前查询的节点。
保证所有查询的 $$$k$$$ 总和不超过 $$$10^{5}$$$。
输出
打印 $$$q$$$ 行,其中第 $$$i$$$ 行包含第 $$$i$$$ 查询的答案。
示例
输入 #1
7 2 5 4 2 6 5 3 1 2 7 5 4 6 3 3 2 7 4 3 3 1 4 6 2 1
输出 #1
2 0
输入 #2
7 2 4 7 2 5 4 1 5 1 5 6 4 3 3 3 2 7 1 4 2 1 6 3 2
输出 #2
1 1
输入 #3
5 2 3 5 4 5 4 2 1 4 2 2 3 1 2 2 2 4 5 4
输出 #3
2 1
注意
考虑第一个例子。
在第一个查询中,我们必须将三个给定节点($$$7$$$、$$$4$$$ 和 $$$3$$$)划分为最多三组,假设树的根位于 $$$2$$$。当树的根位于 $$$2$$$ 时,$$$4$$$ 是 $$$3$$$ 和 $$$7$$$ 的祖先。所以我们不能将所有节点归为一组。只有 $$$1$$$ 方法可以将给定节点分为两组,即 $$$[4]$$$ 和 $$$[3, 7]$$$。此外,只有一种方法可以将给定节点分为三组,即 $$$[7]$$$、$$$[4]$$$ 和 $$$[3]$$$。因此,总共有 $$$2$$$ 方法将给定节点分为最多三组。
在第二个查询中,当树的根位于 $$$4$$$ 时,$$$6$$$ 是 $$$2$$$ 的祖先,$$$2$$$ 是 $$$1$$$ 的祖先。因此,我们不能将所有给定的节点放入一组。