Ориентированное дерево

Ориентированное дерево
Дан неориентированный связный граф без циклов g с n вершинами и n-1 ребром. Другими словами дано дерево на n вершинах.

Получим ориентированный граф g' следующим образом: ориентируем каждое из ребер дерева (то есть для каждого ребра u-v в изначальном графе, в графе g' проведем ориентированное ребро u → v или v → u).

Найдите сумму количеств путей по всем возможным g'. Путем называется последовательность вершин a1, a2, ..., am такая, что для любого i(1 ≤ i ≤ m-1) существует ориентированное ребро ai → ai+1 и ax ≠ ay, если x ≠ y (в частности, существуют пути, состоящие ровно из одной вершины). Так как ответ может быть достаточно большим, выведите его по модулю 10⁹ + 7.

Формат входных данных
В первой строке задано одно целое число n (1 ≤ n ≤ 10⁶) - количество вершин в изначальном графе.

В каждой из последующих n-1 строк содержится по два целых числа u и v (1 ≤ u, v ≤ n, u ≤ v) - две вершины, которые соединены ребром. Гарантируется, что заданный граф является деревом, в нём отсутствуют петли и кратные рёбра.

Формат результата
Выведите в отдельной строке одно целое число - ответ на задачу по модулю 10⁹ + 7.

Примеры
Входные данные
1
Результат работы
1


Входные данные
2
1 2
Результат работы
6


Входные данные
4
1 2
1 3
1 4
Результат работы
68

1

Интересно... В исходных данных задан пример 2 вершины. Ребро одно 1-2. Откуда там может получиться сумма 6?

0

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

0

Сообщение от Dfoght Там получается к 2 вершинам добавляется еще 2

- ??? Где в условии слова про "добавление вершин"?

0