PXTREE

Năm 2048, sau cuộc chiến tranh giữa các vì sao, các hố đen đã nuốt trọn các thiên hà bại trận. Trái Đất đón nhận một làn sóng di cư ồ ạt từ các thiên hà này. Giờ đây, trước tình trạng đất chật người đông, những ngôi nhà truyền thống đã được thiết kế lại để mọi người đều có nơi sinh sống mà không chiếm dụng quá nhiều diện tích.

Chính phủ thông báo rằng mỗi ngôi nhà giờ đây sẽ có cấu trúc của một cây tìm kiếm nhị phân (Binary Search Tree). Bạn có thể tìm hiểu thêm về lý thuyết cây tìm kiếm nhị phân tại đây.

Sau chiến tranh, ngôi nhà của Lilia đã đổ sập thành N căn phòng riêng biệt. Căn phòng thứ i có độ tiện nghi k_i. Lilia sử dụng một số (hoặc tất cả) các phòng được chính phủ cho phép để xây dựng lại ngôi nhà của mình. Tuy nhiên, để ngôi nhà trở nên "hoàn hảo", độ tiện nghi của hai căn phòng bất kỳ được nối trực tiếp với nhau trong cấu trúc ngôi nhà bắt buộc phải có ước chung lớn nhất khác 1.

Nhằm kiểm định chính sách xây nhà này có hiệu quả hay không, chính phủ đã đặt ra cho Lilia Q câu hỏi. Mỗi câu hỏi gồm hai số $l, r$ $(l \le r)$. Chính phủ yêu cầu Lilia tính tổng số cách xây nhà "hoàn hảo" cho đoạn $[l, r]$ (tạm gọi là $Query_{l, r}$). Biết rằng số cách xây nhà cho đoạn $[l, r]$ là tổng số cách xây "hoàn hảo" từ các đoạn $[u, v]$ (tạm gọi là $S_{u, v}$) với:

• $l \le u \le v \le r$.
• $Query_{l, r} = \sum S_{u, v}$

Cụ thể hơn, với mỗi truy vấn, ta cần tính tổng số cách xây nhà "hoàn hảo" từ tất cả các đoạn con liên tiếp $[u, v]$ nằm trong đoạn $[l, r]$.

Chú ý rằng một cách xây nhà "hoàn hảo" cho một đoạn bất kỳ là hợp lệ nếu nó sử dụng tất cả các phòng trong đoạn đó và không được bỏ sót phòng nào.

Đầu vào:

• Dòng đầu tiên chứa các số nguyên dương $N (1 \le N \le 500), Q (1 \le Q \le 10^5)$ — lần lượt là số lượng căn phòng của ngôi nhà và số lượng câu hỏi mà Lilia nhận được.

• Dòng thứ hai chứa N số nguyên dương $c_1, c_2, ..., c_n$ $(1 \le c_i \le 10^9)$ — độ tiện nghi của từng căn phòng, được liệt kê theo thứ tự tăng nghiêm ngặt.

• Q dòng tiếp theo, mỗi dòng chứa hai giá trị $l, r (1 \le l \le r \le N)$ cho biết chi tiết câu hỏi của chính phủ dành cho Lilia.

Đầu ra: Trên Q dòng, mỗi dòng in ra một kết quả duy nhất là số cách xây dựng ngôi nhà "hoàn hảo" tương ứng với câu hỏi của chính phủ.

Vì số cách xây nhà có thể rất lớn, hãy in ra kết quả theo modulo $10^9 + 7$.

Giải thích: Xét đoạn [2, 4], ta có:

• Có 3 cách xây nhà cho các đoạn [2, 2], [3, 3], [4, 4]:

• Có 2 cách xây nhà cho đoạn [2, 3]:

• Có 1 cách xây nhà cho đoạn [2, 4]:

Ví dụ 1:

Đầu vào:

4 3
18 33 44 81
1 2
3 3
2 4

Đầu ra:

4
1
6