Cho hai số nguyên dương \(n\), \(m\) và mảng \(a\) gồm \(n\) số nguyên dương phân biệt \(a_1,a_2,\ldots,a_n\).

Yêu cầu: Với mỗi truy vấn \(l,r\), hãy tính tích của các số từ \(1\) đến \(m\) không xuất hiện trong đoạn \(a_l,a_{l+1},\ldots,a_r\). In kết quả modulo \(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,\ldots,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 dòng gồm hai số nguyên dương \(l,r\) \((1 \le l,r \le n)\).

Output

• Với mỗi truy vấn, in ra một dòng là đáp án của truy vấn sau khi chia lấy dư cho \(10^9+7\).

Example

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

36
2016

Scoring

• Subtask 1 (\(20\%\) điểm): \(n,q \le 2000\)
• Subtask 2 (\(30\%\) điểm): \(m \le 2000\)
• Subtask 3 (\(50\%\) điểm): Không có ràng buộc gì thêm.