Как вы, наверное, знаете, неориентированный связный граф с n вершинами и n - 1 ребрами называется деревом. Вам дано целое число d и дерево, состоящее из n вершин. С каждой вершиной i связано её значение ai.
Назовем множество S вершин дерева допустимым, если выполняются следующие условия:
- S является непустым множеством.
- S является связным множеством. Иными словами, если вершины u и v содержатся во множестве S, то все вершины, лежащие на простом пути между u и v должны также лежать в S.
-
.
Ваша задача — посчитать количество допустимых множеств. Так как результат может быть очень большим, выведите его остаток по модулю 1000000007 (109 + 7).
Выходные данные
Выведите количество допустимых множеств по модулю 1000000007.
Примечание
В первом примере можно найти ровно 8 допустимых множеств: {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {3, 4} и {1, 3, 4}. Множество {1, 2, 3, 4} не является допустимым, поскольку оно не отвечает третьему условию. Множество {1, 4} отвечает третьему условию, но противоречит второму условию.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 4
2 1 3 2
1 2
1 3
3 4
|
8
|
|
2
|
0 3
1 2 3
1 2
2 3
|
3
|
|
3
|
4 8
7 8 7 5 4 6 4 10
1 6
1 2
5 8
1 3
3 5
6 7
3 4
|
41
|