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

У Юсефа есть корневое дерево$$$^{\text{∗}}$$$, состоящее ровно из $$$n$$$ вершин, с корнем в вершине $$$1$$$. Вы хотите дать Юсефу массив $$$a$$$ длины $$$n$$$, где каждый элемент $$$a_i$$$ $$$(1 \le i \le n)$$$ может быть либо $$$1$$$, либо $$$2$$$.

Обозначим $$$s_u$$$ как сумму $$$a_v$$$, где вершина $$$v$$$ находится в поддереве$$$^{\text{†}}$$$ вершины $$$u$$$. Юсеф считает дерево особым, если все значения в $$$s$$$ попарно различны (т.е. все суммы поддеревьев уникальны).

Ваша задача — помочь Юсефу подсчитать количество различных массивов $$$a$$$, которые делают дерево особым. Два массива $$$b$$$ и $$$c$$$ различны, если существует индекс $$$i$$$, такой что $$$b_i \neq c_i$$$.

Поскольку результат может быть очень большим, вы должны вывести его по модулю $$$10^9 + 7$$$.

$$$^{\text{∗}}$$$Дерево — это связный неориентированный граф с $$$n - 1$$$ рёбрами.

$$$^{\text{†}}$$$Поддерево вершины $$$v$$$ — это множество всех вершин, которые проходят через $$$v$$$ по простому пути к корню. Обратите внимание, что вершина $$$v$$$ также включена в множество.

Входные данные

Первая строка содержит целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество наборов входных данных.

Каждый тест состоит из нескольких строк. Первая строка теста содержит целое число $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — количество вершин в дереве.

Затем следуют $$$n−1$$$ строк, каждая из которых содержит два целых числа $$$u$$$ и $$$v$$$ $$$(1 \le u,v \le n, u \ne v)$$$, которые описывают пару вершин, соединённых ребром. Гарантируется, что данный граф является деревом и не имеет петель или кратных рёбер.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого теста выведите одно целое число $$$x$$$ — количество различных массивов $$$a$$$, которые делают дерево особым, по модулю $$$10^9 + 7$$$.

Пример
Входные данные
7
2
1 2
8
1 2
2 3
3 8
2 4
4 5
5 6
6 7
10
1 2
2 3
3 4
4 5
5 6
4 7
7 8
4 9
9 10
7
1 4
4 2
3 2
3 5
2 6
6 7
7
1 2
2 3
3 4
3 5
4 6
6 7
7
5 7
4 6
1 6
1 3
2 6
6 7
5
3 4
1 2
1 3
2 5
Выходные данные
4
24
0
16
48
0
4
Примечание

Дерево, представленное в пятом примере: