Busy Beaver снова сеет хаос на фермерском рынке! В этот раз он затеял «продуктовую битву» среди торговых палаток.

Палатки пронумерованы от $1$ до $N$ и соединены $N - 1$ дорогой, образуя дерево. Иными словами, можно добраться от любой палатки до любой другой, следуя по дорогам, и между любыми двумя палатками существует ровно один простой путь.

Busy Beaver распределяет каждую палатку в «Команду Картофеля» (Team Potato) или «Команду Томата» (Team Tomato) следующим образом:

• Он начинает с палатки $1$, перемещается по дорогам, посещает каждую палатку и в конце возвращается в палатку $1$. Среди всех таких маршрутов он выбирает тот, при котором общее количество пройденных дорог минимально.
• Палатка $1$ закрепляется за «Командой Картофеля».
• Когда Busy Beaver посещает палатку впервые (кроме палатки $1$), он немедленно назначает её одной из двух команд. Чтобы борьба была честной, он чередует команды при каждом назначении новой палатки. То есть, если последняя назначенная палатка была закреплена за «Командой Картофеля», то следующая посещенная палатка должна быть закреплена за «Командой Томата», и наоборот.

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

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

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

Первая строка каждого тестового случая содержит единственное целое число $N$ ($2 \le N \le 10^5$).

Каждая из следующих $N - 1$ строк содержит два целых числа $u$ и $v$ ($1 \le u, v \le N, u \neq v$), указывающих на наличие дороги между палатками $u$ и $v$.

Сумма $N$ по всем тестовым случаям не превышает $2 \cdot 10^5$.

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

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

Система оценки

Для этой задачи существует три подзадачи:

• (10 баллов): Палатки образуют граф-звезду с корнем в палатке $1$. Конкретнее, с палаткой $1$ соединено $N - 1$ дорог.
• (20 баллов): Палатки образуют бинарное дерево с корнем в палатке $1$. Конкретнее, с палаткой $1$ соединено не более $2$ дорог, а с любой другой палаткой — не более $3$ дорог.
• (70 баллов): Дополнительных ограничений нет.

Примеры

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

4
4
1 2
2 3
2 4
7
1 2
1 3
1 4
1 5
1 6
1 7
7
1 2
1 3
2 4
2 5
3 6
3 7
7
1 2
1 3
1 4
2 5
2 6
2 7

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

2
20
8
12

Примечание

Пример содержит 4 тестовых случая:

• Тестовый случай 1 удовлетворяет второй подзадаче (бинарное дерево).
• Тестовый случай 2 удовлетворяет первой подзадаче (граф-звезда).
• Тестовый случай 3 удовлетворяет второй подзадаче (бинарное дерево).
• Тестовый случай 4 удовлетворяет третьей подзадаче (без дополнительных ограничений).

В первом тестовом случае один из вариантов распределения показан ниже.

Один из маршрутов минимальной длины: $1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1$.

Его общая длина равна $6$, что является минимально возможным значением для маршрута, который начинается в палатке $1$, посещает каждую палатку и возвращается в палатку $1$.

Палатки распределяются по командам в порядке их первого посещения:

• Палатка $1$ закреплена за «Командой Картофеля».
• Палатка $2$ закреплена за «Командой Томата».
• Палатка $3$ закреплена за «Командой Картофеля».
• Палатка $4$ закреплена за «Командой Томата».

Другой возможный вариант распределения получается при посещении палатки $4$ перед палаткой $3$, что меняет их команды местами. Таким образом, общее количество возможных распределений равно $2$.