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" ~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 chia lấy dư cho ~10^9 + 7~.

Dữ liệu

• 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_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^9)~ — độ "dẻo dai" của các cây cam.

• 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 2 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~.

Kết quả

In ra ~T~ dòng, mỗi dòng là đáp án cho từng câu hỏi modulo ~10^9 + 7~

Ví dụ

Sample Input

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

Sample Output

10
70
140

Giải thích

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

Chấm điểm

• Subtask 1 (50% số test): ~n, T \le 10^3~.

• Subtask 2 (50% số test): Giới hạn như đề bài.