Дано дерево из \(n\) вершин и \(q\) запросов.
Каждый запрос начинается с трех целых чисел \(k\), \(m\) и \(r\), и продолжается \(k\) вершинами дерева \(a_1, a_2, \ldots, a_k\). Чтобы ответить на запрос, предположите, что дерево подвешено за вершину \(r\). Рассмотрим разбиения данных \(k\) вершин на не более чем \(m\) групп так, что выполняются следующие условия:
- Каждая вершина принадлежит ровно одной группе, каждая группа содержит хотя бы одну вершину.
- Ни в одной группе нет двух вершин таких, что одна является предком (не обязательно непосредственным) другой.
Выведите количество различных таких разбиений по модулю \(10^{9}+7\) для каждого запроса.
Выходные данные
Выведите \(q\) строк, где \(i\)-я строка содержит ответ на \(i\)-й запрос.
Примечание
Рассмотрим первый пример.
В первом запросе нужно разделить три данные вершины (\(7\), \(4\) и \(3\)) на не более чем три группы, считая, что корнем дерева является вершина \(2\). Когда дерево подвешено за вершину \(2\), вершина \(4\) является предком вершин \(3\) и \(7\). Поэтому нельзя все вершины отнести к одной группе. Есть только \(1\) способ разделить эти вершины на две группы: \([4]\) и \([3, 7]\). Кроме того, есть один способ разделить данные вершины на три группы: \([7]\), \([4]\) и \([3]\). Таким образом, есть всего \(2\) способа разбить данные вершины на не более чем три группы.
Во втором запросе дерево подвешено за вершину \(4\), при этом \(6\) является предком \(2\), а \(2\) является предком \(1\). Поэтому нельзя все вершины отнести к одной группе.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|
1
1
|
|
3
|
5 2
3 5
4 5
4 2
1 4
2 2 3 1 2
2 2 4 5 4
|
2
1
|