Chị Hiền là một người đam mê toán học. Một hôm nọ, chị gặp phải một bài toán như sau:

Cho mảng ~A~ gồm ~n~ phần tử ~A_1, A_2, \dots, A_n~. Chọn ra ~B~ là một dãy con không rỗng từ mảng ~A~ ~(~các phần tử của ~B~ không nhất thiết phải nằm liên tiếp~)~, đặt ~m~ ~(m > 0)~ là số phần tử của ~B~, lần lượt thực hiện các thao tác sau:

• Xét mặt phẳng ~Oxy~, một điểm được gọi là lattice point nếu nó có tọa độ là số nguyên dương. Chọn ra ~m~ điểm sao cho chúng đều là lattice point. Điểm thứ ~i~ phải nằm trên đường thẳng đi qua điểm ~(0, B_i)~ và ~(B_i, 0)~. Lưu ý rằng các điểm được chọn có thể ở cùng tọa độ.

• Tiếp theo, kẻ ~m~ đoạn thẳng, đoạn thứ ~i~ nối giữa gốc tọa độ ~(0, 0)~ và điểm thứ ~i~. Độ đẹp của ~1~ đoạn thẳng được tính bằng số lượng lattice point nằm trên đoạn thẳng đó.

Với mỗi đãy con ~B~ được chọn, gọi ~f(B)~ là số cách chọn ~m~ điểm sao cho tổng độ đẹp của ~m~ đoạn thẳng là tối đa, 2 cách chọn là khác nhau nếu tồn tại số nguyên dương ~i~ ~(i \le m)~ sao cho điểm thứ ~i~ trong cách chọn thứ 1 có tọa độ khác điểm thứ ~i~ trong cách chọn thứ 2. Gọi ~s(A)~ là tổng các ~f(B)~ với mọi dãy con ~B~ không rỗng của ~A~ (Có tổng cộng ~2^n - 1~ dãy con ~B~ không rỗng có thể chọn từ mảng ~A~ ban đầu).

Mặc dù ban đầu mảng ~A~ có ~n~ phần tử nhưng để tiết kiệm giấy một vài trong số chúng sẽ bị chị Hiền xóa đi. Cho ~q~ truy vấn, truy vấn thứ ~i~ gồm ~1~ cặp số ~l_i~ và ~r_i~ ~(1 \le l_i \le r_i \le n)~, hãy tính số giá trị khác nhau mà ~s(A)~ có thể nhận sau khi xóa nếu chị Hiền được phép giữ lại một số phần tử trong đoạn ~A_{l_i}, A_{l_i + 1}, \dots, A_{r_i}~ rồi xóa đi các phần tử còn lại của mảng ~A~ ~(~lưu ý rằng chị Hiền phải giữ ít nhất 1 phần tử để mảng ~A~ không rỗng sau khi xóa~)~. Do đáp án có thể rất lớn nên hãy lấy phần dư khi chia cho ~10^9 + 7~.

Hãy giúp chị Hiền trả lời ~q~ truy vấn trên.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~q~ ~(1 \le n,q \le 10^5)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(2 \le A_i \le 10^{12}~, ~max(A_1, \ldots, A_n) - min(A_1, \ldots, A_n) < 10^7)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên ~l_i~ và ~r_i~ ~(1 \le l_i \le r_i \le n)~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là số giá trị khác nhau mà ~s(A)~ có thể nhận tương ứng với truy vấn thứ ~i~. Do đáp án có thể rất lớn nên hãy lấy phần dư khi chia cho ~10^9 + 7~.

Subtask

• Subtask ~1~ (~10\%~ số điểm): ~A_i~ là các số nguyên dương chẵn.
• Subtask ~2~ (~30\%~ số điểm): ~1 \le q \le 100~.
• Subtask ~3~ (~60\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input

4 2
2 3 4 2
1 3
3 4

Sample Output

5
2

Note

• Truy vấn ~[1, 3]~ có tất cả ~5~ giá trị ~s(A)~ khác nhau :
  • ~A = [2]~: ~s(A) = 1~
  • ~A = [3]~: ~s(A) = 2~
  • ~A = [4]~: ~s(A) = 1~
  • ~A = [2, 3]~: ~s(A) = 5~
  • ~A = [2, 4]~: ~s(A) = 3~
  • ~A = [3, 4]~: ~s(A) = 5~
  • ~A = [2, 3, 4]~: ~s(A) = 11~