E. Дерево
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$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$$$-й запрос.

Примеры
Входные данные
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
Выходные данные
2
0
Входные данные
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
Выходные данные
1
1
Входные данные
5 2
3 5
4 5
4 2
1 4
2 2 3 1 2
2 2 4 5 4
Выходные данные
2
1
Примечание

Рассмотрим первый пример.

В первом запросе нужно разделить три данные вершины ($$$7$$$, $$$4$$$ и $$$3$$$) на не более чем три группы, считая, что корнем дерева является вершина $$$2$$$. Когда дерево подвешено за вершину $$$2$$$, вершина $$$4$$$ является предком вершин $$$3$$$ и $$$7$$$. Поэтому нельзя все вершины отнести к одной группе. Есть только $$$1$$$ способ разделить эти вершины на две группы: $$$[4]$$$ и $$$[3, 7]$$$. Кроме того, есть один способ разделить данные вершины на три группы: $$$[7]$$$, $$$[4]$$$ и $$$[3]$$$. Таким образом, есть всего $$$2$$$ способа разбить данные вершины на не более чем три группы.

Во втором запросе дерево подвешено за вершину $$$4$$$, при этом $$$6$$$ является предком $$$2$$$, а $$$2$$$ является предком $$$1$$$. Поэтому нельзя все вершины отнести к одной группе.