У вас есть дерево из \(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)\)).
Выходные данные
Выведите одно целое число — суммарную стоимость всех деревьев, соответствующих ограничениям, взятую по модулю \(10^9 + 7\).
Примечание
В первом примере существует четыре способа покрасить дерево (то есть там надо просуммировать стоимость четырех деревьев):
- дерево со следующими цветами: \(\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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1
1 2
1 1
1 2
1 2
1 3
3 4
|
22
|