Cho đồ thị dạng cây gồm \(N\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\), đỉnh thứ \(i\) \((1 \leq i \leq N)\) có ghi giá trị nguyên dương \(A_i\). Có \(Q\) truy vấn, truy vấn thứ \(k\) \((1 \leq k \leq Q)\) được mô tả bằng ba số \(u_k, v_k, x_k\) và cần tính giá trị \(S_k = \prod gcd(A_t, x_k) \bmod (10^9 + 7)\), trong đó \(t\) là các đỉnh nằm trên đường đi đơn từ \(u_k\) đến \(v_k\) và phép toán \(\bmod\) là phép toán chia lấy dư.

Yêu cầu: Với mỗi truy vấn hãy tính giá trị \(S_k\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N, Q\) \((N, Q \leq 10^5)\)
• Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1, A_2, A_3, ..., A_N\) \((A_i \leq 10^7)\)
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) mô tả một cạnh của cây
• Dòng thứ \(k\) \((1 \leq k \leq Q)\) trong \(Q\) dòng tiếp theo chứa ba số nguyên dương \(u_k, v_k, x_k\) \((1 \leq u_k, v_k \leq N; x_k \leq 10^7)\) mô tả truy vấn thứ \(k\)

Output

• Ghi ra \(Q\) dòng tương ứng là đáp án của \(Q\) truy vấn

Example

4 3
1 2 3 4
1 2
2 3
3 4
1 4 1
4 4 2
1 4 2

1
2
4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N, Q \leq 1000\)
• Subtask \(2\) (\(30\%\) số điểm): \(x_k\) là \(2\) lũy thừa của một số nguyên không âm
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc nào thêm