30247번 - Travels 서브태스크다국어

문제

Martynas is a travel enthusiast and writes reviews on an Internet blog. Today he wants to evaluate trips offered by a travel agency called Rail Baitlandija.

In Baitlandija there are N cities, numbered from 1 to N. These cities are connected by one-way rails so that it is possible to get from city i to city j by train only when i < j.

However, not all possible train routes are offered by Rail Baitlandija agency. This means that there are M pairs of cities (a_i, b_i) (a_i < b_i) where it is not possible to buy train tickets from city a_i to city b_i.

Martynas defines a trip to be such a sequence of cities (a₁, a₂, ..., a_k) (k > 1) that for each city pair (a_i, a_i+1) (1 ≤ i ≤ k − 1) Rail Baitlandija offers train tickets from a_i to a_i+1. Today he decided to try each such trip exactly once.

Visiting city i brings him m_i amount of pleasure even if he has already visited this city during the previous trip. Therefore, each trip (a₁, a₂, ..., a_k) brings him (m_a1 + m_a2 + ... + m_ak) of pleasure and the pleasure experienced on all those trips is summed.

Having done all of the trips, Martynas became so happy that he forgot how much pleasure he had experienced in total. When writing the review, it is important to include this number, so he needs your help to calculate it.

Calculate the total pleasure experienced by Martynas. Output the answer modulo 10⁹ + 7.

입력

The first line of the input contains two intgers N and M. On the second line there are N integers m₁, m₂, . . . , m_N. They represent the amount of pleasure Martynas experiences in the ith city.

Further, there are M lines. Each of them contains two integers a_i and b_i, which mean that Rail Baitlandija does not sell tickets from city a_i to city b_i.

출력

Output one non-negative integer – the total amount of pleasure experienced by Martynas modulo 10⁹ + 7.

제한

• 1 ≤ N, M ≤ 200 000
• 0 ≤ m_i ≤ 1 000 000 for all 1 ≤ i ≤ N

서브태스크

힌트