Али — младший брат Хамеда, у него завтра день рождения. Хамед хочет подарить брату подарок. Для этого он дал ему задачу по программированию и сказал, что если Али её решит, то он получит новенький ноутбук. Али ещё не такой талантливый программист как Хамед, и, хотя он обычно не жульничает, этот случай — исключение. Всё-таки на кону новенький ноутбук. Поэтому он решил в тайне от него попросить вас помочь ему. Пожалуйста, решите для Али следующую.
Вам дано взвешенное корневое дерево из n вершин. Вершина номер 1 является корнем дерева. Определим d(u, v) как сумму длин рёбер на кратчайшем пути между вершинами u и v. В частности, определим d(u, u) = 0. Также, определим S(v) для каждой вершины v как множество, содержащее все вершины u, такие, что d(1, u) = d(1, v) + d(v, u). Затем определим функцию f(u, v) по следующей формуле:
Ваша задача — вычислить f(u, v) для каждой из q данных пар вершин. Так как ответ может быть довольно большим, выведите его по модулю 109 + 7.