Bình có một dãy số nguyên dương. Với mỗi truy vấn \((l, r)\), Bình muốn tính bội số chung nhỏ nhất (LCM) của tất cả các phần tử trong đoạn \([l, r]\). Kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(10^9 + 7\).

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le N\)).

Định dạng đầu ra

• Ứng với mỗi truy vấn, in ra LCM của đoạn modulo \(10^9 + 7\).

Ví dụ

Input:

5 3
2 3 4 5 6
1 3
2 5
1 5

Output:

12
60
60