Game thiện xạ VNOI Shooter tổ chức sự kiện One shot mỗi năm một lần. Thể lệ sự kiện rất đơn giản như sau:

• Mỗi trận gồm ~n~ người chơi đứng trên một vòng tròn đủ lớn theo thứ tự tăng dần theo chiều kim đồng hồ. Tức người chơi ~i~ đứng tiếp sau người chơi ~i - 1~ và người tiếp theo của người chơi ~n~ chính là người chơi ~1~.

• Trước khi bắt đầu trận, họ sẽ đưa số coin mà họ cược. Người chơi ~i~ sẽ cược ~a_i~ coin.

• Sau khi tất cả cược xong, hệ thống sẽ phát cho mỗi người chơi một cây súng ngẫu nhiên. Người chơi thứ ~i~ sở hữu cây súng có tầm bắn từ ~l_i~ đến ~r_i~ theo chiều kim đồng hồ.

• Khi bắt đầu vòng chơi, hệ thống sẽ đếm ngược thời gian để các xạ thủ có thể nhắm vào một mục tiêu của mình. Khi đồng hồ đếm ngược kết thúc, các xạ thủ sẽ đồng thời bắn.

• Sau khi lượt bắn kết thúc, những ai còn sống sót là người chơi thắng, và họ sẽ được hệ thống thưởng đúng số tiền họ cược. Ngược lại, những người chơi thua sẽ bị mất tiền cược.

• Giả sử xác suất một người nhắm vào một trong các mục tiêu của họ là như nhau. Trong một trận cụ thể, sau khi biết hết số tiền người chơi cược và loại súng của họ, hãy tính xem giá trị kỳ vọng là số coin mà hệ thống nhận được sau trận này.

Input

Dữ liệu vào từ file văn bản oneshot.inp:

Dòng đầu tiên gồm một số nguyên dương ~n~ (~2 \le n \le 2 \cdot 10^5~) - số lượng người chơi.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^5~)- với ~a_i~ là số coin mà người chơi thứ ~i~ cược.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo có hai số nguyên dương ~l_i~ và ~r_i~ (~1 \le l_i, r_i \le n~) - tầm bắn của cây súng của người chơi thứ ~i~.

Output

In ra file văn bản oneshot.out. Đặt ~M = 10^9 + 7~. Giá trị kỳ vọng của số coin mà hệ thống nhận được sau trận có thể được biểu diễn dưới dạng một phân số tối giản ~\frac{P}{Q}~, với ~P~ và ~Q~ là hai số nguyên và ~Q \not\equiv 0 \pmod{M}~. Hãy in ra ~P \cdot Q^{-1} \pmod{M}~, hay nói cách khác, in ra một số nguyên ~X~ thỏa mãn ~0 \le X < M~ và ~X \cdot Q \equiv P \pmod{M}~.

Scoring

Sample Input 1

4
7 3 3 7
4 4
4 1
3 2
3 2

Sample Output 1

812500015

Sample Input 2

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

Sample Output 2

851428591

Note

Ở ví dụ thứ nhất:

• Người thứ nhất nằm trong tầm bắn của người thứ hai, thứ ba và thứ tư. Tỉ lệ người thứ nhất sống sót là ~\frac{9}{32}~.
• Người thứ hai nằm trong tầm bắn của người thứ ba và thứ tư. Tỉ lệ người thứ hai sống sót là ~\frac{9}{16}~.
• Người thứ ba nằm trong tầm bắn của người thứ ba và thứ tư. Tỉ lệ người thứ ba sống sót là ~\frac{9}{16}~.
• Người thứ tư nằm trong tầm bắn của người thứ nhất, thứ ba và thứ tư. Tỉ lệ người thứ tư sống sót là ~0~.

Giá trị kỳ vọng số coin mà hệ thống nhận được là: ~-7 \cdot \frac{9}{32}+ 7 \cdot(1-\frac{9}{32})-3\cdot \frac{9}{16}+ 3\cdot (1-\frac{9}{16})-3\cdot \frac{9}{16}+3 \cdot (1- \frac{9}{16})+ 7 = \frac{149}{16}~.

Vì ~16^{-1} \equiv 562500004 \pmod{M}~, in ra kết quả là ~(149 \cdot 562500004) \equiv 812500015 \pmod{M}~.