Lan muốn nhờ Anh giải giúp bài toán sau: Cho một mảng số nguyên, có 2 toán tử có thể tác động lên mảng như sau:

• 0 i x — gán giá trị x cho phần tử thứ i;
• 1 l r — trả về số lượng ước số của tích các phần tử liên tiếp trong đoạn từ l đến r. Số này có thể rất lớn nên hãy lấy phần dư trong phép chia cho 10⁹ + 7.

Thực ra vì có tình ý với Lan nên Anh không thể từ chối Lan. Nhưng vốn tính lười biếng nên Anh không muốn làm việc mà muốn bí mật nhờ bạn viết hộ chương trình giải quyết bài toán dùm.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n là kích thước của mảng (1 ≤ n ≤ 5 · 10⁴).

Dòng thứ 2 chứa n số nguyên a_i là các phần tử của mảng (1 ≤ a_i ≤ 10⁴).

Dòng thứ 3 chứa một số nguyên q là số lượng yêu cầu (1 ≤ q ≤ 10⁴).

Mỗi dòng trong số q dòng tiếp theo chứa 3 số nguyên chỉ một toán tử tác động lên mảng. Nếu số đầu tiên là 0 thì sẽ thực hiện cập nhật yêu cầu này trong mảng. Nếu số đầu tiên là 1, thì chương trình cần tìm ra số ước số của tích các phần tử liên tiếp nhau trong đoạn, lấy phần dư trong phép chia cho 10⁹+7.

Dữ liệu đảm bảo trong tất cả các yêu cầu 1 ≤ i,l,r ≤ n;1 ≤ x ≤ 10⁴. Kết quả

Đối với mỗi yêu cầu tìm số ước số, ghi ra trên một dòng giá trị tìm được lấy phần dư cho 10⁹ + 7.