hieuhfgr là một người thích vẽ. Hiện tại hieuhfgr đang sở hữu ~n~ cây bút màu được đựng trong một hộp hàng ngang, cây bút thứ ~i~ có màu là ~a_i~. Bây giờ, hieuhfgr cần vẽ ~q~ bức tranh, bức tranh thứ ~i~ hieuhfgr sẽ lấy những cây bút màu từ vị trí ~l_i \to r_i~. Nhưng mà lấy hết mà vẽ thì chán quá!!!. hieuhfgr muốn hỏi bạn xem có bao cách chọn màu sắc khác nhau để vẽ được một bức tranh.

Định nghĩa: một bức tranh cần tối thiểu ~1~ màu sắc.

Input

Dòng 1: chứa số nguyên ~n, q~.

Dòng 2: chứa dãy số ~a~

~q~ dòng cuối mỗi dòng chứa ~l_i \to r_i~ yêu cầu nếu chọn các bút màu từ vị trí ~l_i \to r_i~ thì có bao nhiêu cách chọn màu sắc.

Output

Ghi ra ~q~ dòng là số cách chọn khi chia lấy dư cho ~10^9+7~

Contraints

~n, q \leq 10^5~

~a_i \leq 10^6~

~1 \leq l_i \leq r_i \leq n~

Sample Input 1

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

Sample Output 1

3
7
7

Sample Input 2

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

Sample Output 2

1
3
3

Note

• Sample Test 1:
• Truy vấn 1: chọn ~\{1\}, \{2\}, \{1, 2\}~

• Truy vấn 2: chọn ~\{1\}, \{2\}, \{3\}, \{1, 2\}, \{2, 3\}, \{1, 3\}, \{1, 2, 3\}~

• Sample Test 2:

• Truy vấn 1: chọn ~\{1\}~
• Truy vấn 2: chọn ~\{1\}, \{2\}, \{1, 2\}~
• Truy vấn 3: chọn ~\{1\}, \{2\}, \{1, 2\}~