Республиканская олимпиада по информатике 2019 года за 11 класс | Казахстанские олимпиады

Задача D. Дерево невидимого Жанадиля

Дано связное дерево с $N$ вершин.

Невидимый Жанадиль выбирает какое-то подмножество вершин из заданного дерева, и удаляет все выбранные вершины и связанные с ними ребра из дерева.

В результате получится лес из $X$ связанных компонент, где компонента $i$ содержит $sz_i$ вершин, для $1 <= i <= X$. Основываясь на этом, Жанадиль считает значение $F = \sum_{i=1}^{X} 2^{sz[i]}$.

Ваша задача состоит в том чтоб посчитать и вывести сумму значений $F$ по всем возможным подмножествам.

Выведите ответ по модулю $10^9 + 7$.

Формат входного файла

Первая строка содержит целое число $N$ $(1 <= N <= 2 * 10^5)$ — количество вершин в дереве.

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

Формат выходного файла

Выведите сумму значений $F$ по всем возможным подмножествам по модулю $10^9 + 7$.

Примеры

Вход

3
1 2
2 3

Выход

26

Вход

5
1 2
1 3
5 1
5 4

Выход

216