Про дерево

Обмеження: 3 сек., 256 МіБ

Дано дерево (зв’язний неорієнтований граф, у якому відсутні цикли) з \(n\) вершин. У кожній вершині \(v\) лежить камінь вагою \(w_v\).

Далі \(q\) запитів: скількома способами можна назбирати камінців сумарною вагою \(x\), якщо рухатися простим шляхом від вершини \(a\) до вершини \(b\)?

Вхідні дані

У першому рядку задано ціле число \(n\) — кількість вершин.

У другому рядку — \(n\) натуральних чисел \(w_i\) — вага камінця в \(i\)-тій вершині.

У наступних \(n-1\) рядках задані ребра графу.

У наступному рядку — ціле число \(q\) — кількість запитів.

У наступних \(q\) рядках задано запити. Кожен запит містить три числа \(a\), \(b\), \(x\), де \(a\) та \(b\) — пара вершин, і \(x\) — сумарна вага, яку треба назбирати.

Вихідні дані

Виведіть \(q\) чисел — відповіді на кожен запит за модулем простого числа \(10^9+7\).

Обмеження

\(0 \le n \le 10^5\),

\(1 \le q \le 10^4\),

\(1 \le a, b \le n\),

\(1 \le w_i, x \le 100\).

Приклади