Вам дано дерево с \(n\) вершинами, пронумерованными с \(1\) до \(n\). В вершине \(i\) записано значение \(V_i\).
Если простой путь от вершины \(u_1\) до вершины \(u_m\) состоит из \(m\) вершин, а именно из \(u_1 \rightarrow u_2 \rightarrow u_3 \rightarrow \dots u_{m-1} \rightarrow u_{m}\), то знакопеременная сумма для этого пути \(A(u_{1},u_{m})\) определяется как \(A(u_{1},u_{m}) = \sum\limits_{i=1}^{m} (-1)^{i+1} \cdot V_{u_{i}}\). Путь может содержать \(0\) рёбер, т. е. \(u_{1}=u_{m}\).
Вычислите сумму знакопеременных сумм для всех различных простых путей в дереве. Обратите внимание, пути ориентированны: два пути считаются различными, если у них различное начало или различный конец. Так как ответ может быть большим, выведите остаток от деления его на \(10^{9}+7\).
Примечание
Рассмотрим первый пример.
Знакопеременная сумма для простого пути из вершины \(1\) в вершину \(2\): \(1 \rightarrow 2\) равна \(A(1,2) = 1 \cdot (-4)+(-1) \cdot 1 = -5\).
Знакопеременная сумма для простого пути из вершины \(1\) в вершину \(3\): \(1 \rightarrow 3\) равна \(A(1,3) = 1 \cdot (-4)+(-1) \cdot 5 = -9\).
Знакопеременная сумма для простого пути из вершины \(2\) в вершину \(4\): \(2 \rightarrow 1 \rightarrow 4\) равна \(A(2,4) = 1 \cdot (1)+(-1) \cdot (-4)+1 \cdot (-2) = 3\).
Простой путь из вершины \(1\) в вершину \(1\) содержит только вершину \(1\), поэтому \(A(1,1) = 1 \cdot (-4) = -4\).
Аналогично, \(A(2, 1) = 5\), \(A(3, 1) = 9\), \(A(4, 2) = 3\), \(A(1, 4) = -2\), \(A(4, 1) = 2\), \(A(2, 2) = 1\), \(A(3, 3) = 5\), \(A(4, 4) = -2\), \(A(3, 4) = 7\), \(A(4, 3) = 7\), \(A(2, 3) = 10\), \(A(3, 2) = 10\). Поэтому ответ равен \((-5) + (-9) + 3 + (-4) + 5 + 9 + 3 + (-2) + 2 + 1 + 5 + (-2) + 7 + 7 + 10 + 10 = 40\).