Cho hai số nguyên dương ~n~, ~m~ và mảng ~a~ gồm ~n~ số nguyên dương ~a_1,a_2,…,a_n~.

Yêu cầu: Cho ~q~ truy vấn, mỗi truy vấn, cho hai số nguyên dương ~l,r(1 \le l,r \le n)~ cần tính tích các số từ 1 đến ~m~ mà không thuộc mảng ~a_l,a_l+1,...,a_r~. Do kết quả có thể rất lớn, bạn cần đưa ra kết quả sau khi chia lấy phần dư cho ~10^9+7~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,m(n,m \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n(a_i \le m)~.
• Dòng thứ ba gồm số nguyên dương ~q(q \le 10^5)~.
• ~q~ dòng tiếp theo, mối truy vấn gồm hai số ~l,r~.

Output

• In ra theo yêu cầu của đề bài.

Scoring

Example input 1

5 8
1 4 5 7 8
2
2 5
1 3 

Example output 1

36
2016

Note 1

• Truy vấn ~1~: ~1 \times 2 \times 3 \times 6 = 36 ~. Các số: ~4, 5, 7, 8~ thuộc đoạn ~a_l,a_l+1,...,a_r~.