Примечание: лимит памяти для этой задачи составляет 512 МБ, что в два раза больше стандартного.

Совершенное бинарное дерево — это корневое дерево, в котором каждый нелистовой узел имеет ровно двух потомков, а все листовые узлы находятся на одинаковом расстоянии от корня.

Некорневое совершенное бинарное дерево — это дерево без выделенного корня, которое становится совершенным бинарным деревом, если выбрать один из его узлов в качестве корня.

У Бесси есть дерево с $N$ ($1 \le N \le 10^5$) узлами. Определите количество способов удалить подмножество ребер из дерева так, чтобы получившийся лес состоял из набора некорневых совершенных бинарных деревьев. Поскольку ответ может быть очень большим, выведите его по модулю $10^9+7$.

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

Первая строка содержит целое число $T$ ($1 \leq T \leq 100$), количество независимых тестовых случаев.

Первая строка каждого тестового случая содержит целое число $N$.

Каждая из следующих $N-1$ строк каждого тестового случая содержит два целых числа $u_i$ и $v_i$ ($1 \leq u_i, v_i \leq N$), обозначающих ребро между узлами $u_i$ и $v_i$.

Гарантируется, что для каждого тестового случая заданные ребра образуют дерево с $N$ узлами.

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

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

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

Примеры

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

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

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

8
2
14

Примечание

В первом тестовом случае Бесси может удалить любое из следующих подмножеств ребер, чтобы получить лес из совершенных бинарных деревьев:

1. $(2, 6)$
2. $(1, 2)$, $(2, 3)$, $(2, 6)$
3. $(1, 2)$, $(2, 3)$, $(4, 6)$
4. $(1, 2)$, $(2, 3)$, $(5, 6)$
5. $(1, 2)$, $(4, 6)$, $(5, 6)$
6. $(2, 6)$, $(4, 6)$, $(5, 6)$
7. $(2, 3)$, $(4, 6)$, $(5, 6)$
8. $(1, 2)$, $(2, 3)$, $(2, 6)$, $(4, 6)$, $(5, 6)$

Первое подмножество приводит к двум поддеревьям высоты $1$, последнее подмножество приводит к шести поддеревьям высоты $0$, а остальные подмножества приводят к трем поддеревьям высоты $0$ и одному поддереву высоты $1$.