Với mỗi submission AC trong thời gian chính thức của contest LQDOJ Cup 2024 - Round #1, các bạn đã đóng góp 12.500 VNĐ vào quỹ ủng hộ đồng bào khắc phục sự cố cơn bão Yagi. Số tiền này sẽ được tổng hợp và chuyển tới Mặt trận Tổ quốc Việt Nam sau khi việc kiểm tra được hoàn tất.

Thành phố Hà Nội có thể được chia thành \(n\) khu vực, các khu vực được đánh số từ \(1\) đến \(n\), khu vực thứ \(i ~ (1 \leq i \leq n)\) có \(a_i\) người sinh sống.

Việc di chuyển giữa hai khu vực bất kì trong thành phố đều phải thông qua các con đường. Có tất cả \(m\) con đường, con đường thứ \(i ~ (1 \leq i \leq m)\) kết nối hai khu vực \(u_i\) và \(v_i\). Đảm bảo rằng mọi con đường đều kết nối hai khu vực khác nhau và không có hai con đường nào kết nối cùng một cặp khu vực. Từ một khu vực bất kì có thể đi đến tất cả các khu vực còn lại thông qua các con đường.

Siêu bão YAGI đã đi qua các tỉnh miền Bắc, gây ra rất nhiều thiệt hại cho người dân. Chưa kịp khắc phục hoàn toàn hậu quả của cơn bão thì bây giờ người dân lại nghe "tin dữ" về lũ sông Hồng.

Cục quản lý đê điều và phòng, chống thiên tai dự đoán rằng trong trường hợp xấu nhất, tất cả các khu vực của thành phố sẽ lần lượt bị ngập nhưng không có hai khu vực nào bị ngập cùng một lúc, do đó thứ tự bị ngập của các khu vực có thể được biểu diễn bởi một hoán vị \(p_1, p_2, \ldots, p_n ~ (1 \leq p_i \leq n)\) của các số nguyên từ \(1\) đến \(n\), trong đó \(p_i\) là số hiệu của khu vực bị ngập thứ \(i\).

Để dự đoán mức thiệt hại mà lũ sông Hồng gây ra cho thành phố Hà Nội, cục quyết định khảo sát các tình huống có thể xảy ra. Mỗi tình huống tương ứng với một hoán vị \(p_1, p_2, \ldots, p_n\) là thứ tự bị ngập lụt của các khu vực. Với mỗi tình huống \(p_1, p_2, \ldots, p_n\), mức thiệt hại của tình huống đó được tính như sau:

• Các khu vực lần lượt bị ngập, khu vực bị ngập thứ \(i\) có số hiệu là \(p_i\). Ta gọi mức ảnh hưởng của khu vực \(p_i\) trong tình huống này là tổng số người sinh sống trong các khu vực chưa bị ngập (tại thời điểm ngay sau khi khu vực \(p_i\) bị ngập) và được kết nối trực tiếp với \(p_i\).
• Mức thiệt hại của tình huống này là tổng các mức ảnh hưởng của tất cả \(n\) khu vực.

Yêu cầu: Hãy tính tổng mức thiệt hại của tất cả các tình huống có thể xảy ra.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, m\) \((2 \leq n \leq 2 \times {10}^5\), \(1 \leq m \leq \min(5 \times {10}^5, \frac{n(n-1)}{2}))\) lần lượt là là số khu vực và số con đường giữa các khu vực.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n ~ (1 \leq a_i \leq {10}^9)\).
• \(m\) dòng tiếp theo, dòng thứ \(i ~ (1 \leq i \leq m)\) gồm hai số nguyên dương \(u_i, v_i ~ (1 \leq u_i, v_i \leq n)\) thể hiện rằng con đường thứ \(i\) kết nối hai khu vực \(u_i\) và \(v_i\).

Output

• Một số nguyên duy nhất là tổng mức thiệt hại trong tất cả mọi tình huống, vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của kết quả khi chia cho \(({10}^9 + 7)\).

Scoring

• Subtask 1 (\(29\%\) số điểm): \(n \leq 10\).
• Subtask 2 (\(23\%\) số điểm): \(n \leq 20\).
• Subtask 3 (\(19\%\) số điểm): \(n \leq 1000\).
• Subtask 4 (\(17\%\) số điểm): \(m = n - 1\).
• Subtask 5 (\(12\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 2
1 2 3
1 3
2 3

27