Cho dãy số có \(N\) phần tử \((2 \le A_i \le 10^7)\) và \(Q\) truy vấn (mỗi truy vấn gồm \(L\) và \(R\)). Hãy tìm bội chung nhỏ nhất của tất cả các số trong đoạn \([L,R]\). Do bội chung là số rất lớn nên kết quả tính toán được \(MOD\) cho \(10^9+7\).

Ràng buộc:

• \(10 \le N, Q \le 10^5\)
• \(0 \le L \le R \le N\)

Dữ liệu vào:

• Dòng thứ nhất: có 2 số \(N\) và \(Q\)
• Q Dòng tiếp theo: mỗi dòng chứa 2 số \(L\) và \(R\)

Dữ liệu ra:

• Q dòng: mỗi dòng là bội chung nhỏ nhất MOD \((1000000007)\) trong đoạn \(L, R\)

Lưu ý:

• vị trí bắt đầu từ \(0\)

Input

10 3
2 3 4 5 6 7 8 9 10 12
0 2
0 9
3 5

Output

12
2520
210