Ориентированное дерево Дан неориентированный связный граф без циклов 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 (в частности, существуют пути, состоящие ровно из одной вершины). Так как ответ может быть достаточно большим, выведите его по модулю 109 + 7.
Формат входных данных
В первой строке задано одно целое число n (1 ≤ n ≤ 106) - количество вершин в изначальном графе.
В каждой из последующих n-1 строк содержится по два целых числа u и v (1 ≤ u, v ≤ n, u ≤ v) - две вершины, которые соединены ребром. Гарантируется, что заданный граф является деревом, в нём отсутствуют петли и кратные рёбра.
var a:Array[1..1000010] of longint;
i,n,s,ma,mi,sl:longint;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
readln(n);
mi:=(1 shl 30);
ma:=-(1 shl 30);
for i:=1 to n do begin read(a[i]);
ma:=max(ma,a[i]);
mi:=min(mi,a[i]);
end;
if ma=mi then write(0,'',n,'',0)
else
begin for i:=1 to n do
begin
if a[i]=ma then s:=s+1;
if a[i]=mi then sl:=sl+1;
end;
writeln(s,' ',sl,' ',n-s-sl);
close(input);
close(output);
end;
end.