Xét dãy số nguyên dương \(A = (a_1, a_2, \dots, a_n)\) và hai thao tác trên dãy:

1. Thao tác loại 0 với hai thông số \(i, x\): Thay đổi phần tử \(a_i\) bằng số nguyên dương \(x\) (\(1 \le i \le n, 1 \le x \le 10^6\)).
2. Thao tác loại 1 với hai thông số \(L, R\): Gọi \(P\) là tích các số từ \(a_L\) đến \(a_R\), \(D(P)\) là số ước số của \(P\). Thao tác này yêu cầu đưa ra phần dư trong phép chia \(D(P)\) cho \(10^9 + 7\).

Yêu cầu: Cho dãy số \(A\) và \(Q\) thao tác, với mỗi thao tác loại 1 hãy đưa ra kết quả tương ứng.

Input

• Dòng đầu chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).
• Dòng thứ ba chứa số nguyên \(Q\) là số thao tác.
• Tiếp theo là \(Q\) dòng, mỗi dòng chứa ba số mô tả các thao tác:
  • Nếu là thao tác loại 0: dòng gồm ba số 0 i x.
  • Nếu là thao tác loại 1: dòng gồm ba số 1 L R.

Output

• Ghi ra kết quả gồm nhiều dòng, mỗi dòng là một số tương ứng với kết quả của các thao tác loại 1 theo thứ tự xuất hiện.

Constraints

• \(1 \le n, Q \le 10^5\).
• \(1 \le a_i, x \le 10^6\).
• Các subtask:
  • Subtask 1 (30% số điểm): \(n, Q \le 1000\).
  • Subtask 2 (30% số điểm): \(n, Q \le 5 \cdot 10^4\) và không có thao tác loại 0.
  • Subtask 3 (40% số điểm): \(n, Q \le 10^5\).

Example

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

6
4

Nguồn: Thầy Đông '21