Про дерево

Limits: 3 sec., 256 MiB

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

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

Input

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

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

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

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

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

Output

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

Constraints

\(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\).

Samples