Sau khi thua cược nặng nề ở mùa Euro và quán bánh tráng trộn của NTHA, bồ của anh ta, thua lỗ nặng nề, zipdang04 đã không còn giàu có như trước nữa, giờ anh ta chỉ ở một ngôi nhà nhỏ và còn lại rất ít tiền để tiêu xài. Nhưng vì đang còn trong tuổi trai tráng, anh ta quyết định ra đi kiếm tiền để nuôi sống bản thân và ny của mình. Thương hoàn cảnh của anh ta, một ngày nọ có một vị tiên nhân xuất hiện và cho zipdang04 một kho báu có rất nhiều của cải quý giá. Vì muốn giàu nhanh nên anh ta đã lên đường đi đến nơi chôn giậu kho báu và định mang nó về. Nhưng khi đến nơi zipdang04 mới phát hiện ra kho báu bị khoá bởi 1 ổ khoá siêu hiện đại, và muốn mở nó thì phải biết dược mật khẩu của nó, nhưng vị tiên nhân kia quên nói cho anh ta.

Mật khẩu của kho báu là mỗi dãy số bao gồm các số từ \(1\) đến \(n\) và chưa biết trước độ dài, nên zipdang04 nghĩ rằng mình phải thử rất nhiều trường hợp mới mở được kho báu. Nhưng khi nhìn sang bên cạnh, anh ta thấy một bản đồ cho biết một số rằng buộc của mật khẩu. Bản đồ chứa \(m\) cặp số \((u, v)\). Một mật khẩu hợp lệ nếu mọi cặp kề nhau trong mật khẩu đều thuộc \(m\) cặp số trong bản đồ (có thứ tự).

Ví dụ: Nếu \(n = 3\) và bản đồ chứa các cặp \((1, 2), (2, 3)\) thì:

• \([1], [2], [3], [1, 2], [2, 3]\) là các mật khẩu hợp lệ
• \([1, 2, 3]\) hợp lệ vì \((1, 2)\) và \((2, 3)\) đều có trong bản đồ
• \([1, 3, 2]\) không hợp lệ vì cặp \((1, 3)\) không có trong bản đồ
• \([3, 2]\) không hợp lệ vì \((3, 2)\) không có trong bản đồ

Nhưng đời đâu như mơ, lúc nhập mật khẩu, khi nhấn nút \(i\) anh ta phải trả \(a_i\) đồng để có thể nhấn được nút đấy, zipdang04 tự hỏi rằng trong trường hợp tệ nhất anh ta có thể mở được kho báu không. Bạn hãy tính giúp anh ấy số tiền trong trường hợp tệ nhất anh ấy phải bỏ ra nhé, vì con số này quá lớn nên hãy đưa ra mod \(10^9 + 7\). Trường hợp tệ nhất là khi zipdang04 phải thử tất cả mật khẩu có thể. Nếu số lượng mật khẩu là vô hạn thì bạn hãy đưa ra \(-1\)

Input

• Dòng đầu tiên là hai số \(n\) và \(m\) là số nút bấm và số cặp số.

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\), \(a_i\) là số tiền phải trả khi bấm nút thứ \(i\)

• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\), \(v\) miêu tả một cặp số trong bản đồ.

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 1000, m \leq 3000\)
• Subtask \(2\) (\(60\%\) số điểm): không có điều kiện gì thêm

Example

3 3
1 2 3
1 2
2 3
1 3

24

+ $[1], [2], [3]$: tổng tiền là $1+2+3=6$
+ $[1, 2], [2, 3], [1, 3]$: tổng tiền là $12$
+ $[1, 2, 3]$: số tiền là $6$.
Như vậy tổng số tiền cần dùng là $6 + 12 + 6 = 24$.

3 2
10 20 30
1 2
2 3

200