A7749 | Tree

You are given a tree with $n$ nodes and $q$ queries.

Every query starts with three integers $k$ , $m$ and $r$ , followed by $k$ nodes of the tree $a_1, a_2, \ldots, a_k$ . To answer a query, assume that the tree is rooted at $r$ . We want to divide the $k$ given nodes into at most $m$ groups such that the following conditions are met:

- Each node should be in exactly one group and each group should have at least one node.
- In any group, there should be no two distinct nodes such that one node is an ancestor (direct or indirect) of the other.

You need to output the number of ways modulo $10^{9}+7$ for every query.

The first line contains two integers $n$ and $q$ ( $1 \le n, q \le 10^{5}$ ) — the number of vertices in the tree and the number of queries, respectively.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ( $1 \le u, v \le n, u \ne v$ ), denoting an edge connecting vertex $u$ and vertex $v$ . It is guaranteed that the given graph is a tree.

Each of the next $q$ lines starts with three integers $k$ , $m$ and $r$ ( $1 \le k, r \le n$ , $1 \le m \le min(300,k)$ ) — the number of nodes, the maximum number of groups and the root of the tree for the current query, respectively. They are followed by $k$ distinct integers $a_1, a_2, \ldots, a_k$ ( $1 \le a_i \le n$ ), denoting the nodes of the current query.

It is guaranteed that the sum of $k$ over all queries does not exceed $10^{5}$ .

Print $q$ lines, where the $i$ -th line contains the answer to the $i$ -th query.