F. Покрашенное дерево
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть дерево из $$$n$$$ вершин. Цвет $$$i$$$-й вершины — $$$h_{i}$$$.

Стоимость дерева определяется как $$$\sum\limits_{h_{i} = h_{j}, 1 \le i < j \le n}{dis(i,j)}$$$, где $$$dis(i,j)$$$ — количество ребер на кратчайшем пути между $$$i$$$ и $$$j$$$.

Вы не помните точные цвета вершин. Все, что вы помните — $$$h_{i}$$$ может быть любым целым числом из $$$[l_{i}, r_{i}]$$$ (включая границы). Вы хотите посчитать суммарную стоимость всех деревьев, удовлетворяющих этим ограничениям, по модулю $$$10^9 + 7$$$ (множество ребер фиксировано, но точные цвета неизвестны, поэтому всего таких деревьев $$$\prod\limits_{i = 1}^{n} (r_{i} - l_{i} + 1)$$$).

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

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество вершин.

Затем следуют $$$n$$$ строк, в каждой строке заданы два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^5$$$), обозначающих отрезок возможных цветов вершины $$$i$$$.

Затем следуют $$$n - 1$$$ строк, в каждой строке заданы два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), обозначающих ребро дерева. Гарантируется, что данные ребра задают дерево.

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

Выведите одно целое число — суммарную стоимость всех деревьев, соответствующих ограничениям, взятую по модулю $$$10^9 + 7$$$.

Пример
Входные данные
4
1 1
1 2
1 1
1 2
1 2
1 3
3 4
Выходные данные
22
Примечание

В первом примере существует четыре способа покрасить дерево (то есть там надо просуммировать стоимость четырех деревьев):

  • дерево со следующими цветами: $$$\lbrace 1,1,1,1 \rbrace$$$. Его стоимость равна $$$dis(1,2)+dis(1,3)+dis(1,4)+dis(2,3)+dis(2,4)+dis(3,4) = 10$$$;
  • дерево со следующими цветами: $$$\lbrace 1,2,1,1 \rbrace$$$. Его стоимость равна $$$dis(1,3)+dis(1,4)+dis(3,4)=4$$$;
  • дерево со следующими цветами: $$$\lbrace 1,1,1,2 \rbrace$$$. Его стоимость равна $$$dis(1,2)+dis(1,3)+dis(2,3)=4$$$;
  • дерево со следующими цветами: $$$\lbrace 1,2,1,2 \rbrace$$$. Его стоимость равна $$$dis(1,3)+dis(2,4)=4$$$.

Суммарная стоимость равна $$$10+4+4+4=22$$$.