Trong vườn trái cây FreeContest có một hàng gồm ~n~ cây cam. Mỗi cây cam có độ "dẻo dai" là ~a_i~ nhất định.

Hôm nay, bạn được giao một nhiệm vụ gồm nhiều câu hỏi. Mỗi câu hỏi bao gồm các số ~u_i~, ~k_i~. Bạn cần tính toán xem tích độ "dẻo dai " của ~k_i~ cây liên tiếp, bắt đầu từ cây thứ ~u_i~ là bao nhiêu?

Đáp án cuối cùng sẽ được chia lấy dư cho ~10^9 + 7~.

Input Specification

• Dòng thứ nhất chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~ - Độ "dẻo dai" của cây cam thứ ~i~.
• Dòng thứ ba gồm một số ~t~ - Số câu hỏi của nhiệm vụ.
• ~t~ dòng tiếp theo, mỗi dòng gồm hai số ~u_i~, ~k_i~ ~(1 \le u_i, k_i \le n)~. Dữ liệu đảm bảo ~u_i + k_i - 1 \le n~.

Output Specification

• In ra ~t~ dòng, mỗi dòng là đáp án cho từng câu hỏi được ~\bmod 10^9 + 7~.

Subtasks

• Subtask 1 [50%]: ~n, t \le 10^3~.
• Subtask 2 [50%]: Không có giới hạn gì thêm.

Sample Cases

Input #1:

6
5 2 7 1 10 3
3
1 2
3 3
2 4

Output #1:

0
70
140

Explanation #1:

• Ba dãy cây cần tính lần lượt là ~[5, 2]~, ~[7, 1, 10]~, ~[2, 7, 1, 10]~.