Travels

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

Baitlandija has $N$ cities, numbered from 1 to $N$. The cities are connected by one-way rails, so a train can go from city $i$ to city $j$ only when $i < j$.

However, the agency does not sell every possible route. There are $M$ pairs $(a_i, b_i)$ with $a_i < b_i$ where tickets from city $a_i$ to city $b_i$ cannot be bought.

A trip is a sequence of cities $(a_1, a_2, ..., a_k)$ with $k > 1$, where tickets from $a_i$ to $a_{i+1}$ are sold for every $1 \le i \le k-1$. Martynas wants to take each such trip exactly once.

Visiting city $i$ gives him $m_i$ pleasure, even if he has visited that city on an earlier trip. So the trip $(a_1, ..., a_k)$ gives $m_{a_1} + m_{a_2} + ... + m_{a_k}$ pleasure, and the pleasure from all trips is summed.

After finishing all the trips, he forgot the total. He needs your help to calculate it for his review.

The first line contains integers $N$ and $M$.

The second line contains integers $m_1$, $m_2$, ..., $m_N$, where $m_i$ is the pleasure gained in city $i$.

Each of the next $M$ lines contains integers $a_i$ and $b_i$, meaning tickets from city $a_i$ to city $b_i$ are not sold.

Print one non-negative integer: the total pleasure modulo $10^9 + 7$.

$1 \le N, M \le 200000$

$0 \le m_i \le 1000000$ for all $1 \le i \le N$

Time limit: 1000 ms. Memory limit: 1024 MB.