Hoành Sơn là một địa điểm du lịch nổi tiếng trên toàn thế giới bởi sự hùng vĩ cũng như sự đa dạng phong phú về các dãy núi và những cây cầu bắc qua. Địa điểm du lịch Hoành Sơn có các dịch vụ tham quan theo yêu cầu. Cụ thể là bạn chỉ việc đưa ra yêu cầu của lộ trình, sau đó dịch vụ sẽ tính toán và đưa bạn đi qua các cây cầu và ngọn núi theo đúng yêu cầu về lộ trình.

Địa điểm du lịch ở đây có \(N\) ngọn núi và \(M\) cây cầu, mỗi cây cầu nối hai ngọn núi nào đó với nhau. Giữa hai ngọn núi bất kì có thể có nhiều cây cầu nối hai ngọn núi đó với nhau. Cũng có thể có những ngọn núi có những cây cầu tự nối với chính nó tạo ra hình vòng cung để những khách du lịch có thể đứng xung quanh ngọn núi tham quan và chụp ảnh. Hiểu đơn giản thì mô hình của khu du lịch là một đa đồ thị vô hướng \(N\) đỉnh \(M\) cạnh.

Các ngọn núi được đánh số từ \(1\) đến \(N\) và ngọn núi thứ \(i\) có độ cao là \(A_i\). Về độ dốc của các cây cầu thì nó được tính theo chênh lệch chiều cao của hai ngọn núi ở hai đầu cây cầu. Nói cách khác, nếu cây cầu nối hai ngọn núi \(x\) và \(y\) thì độ dốc của nó là \(|A_x - A_y|\).

Sau khi đạt giải quốc gia, Tuấn muốn tự thưởng cho mình chuyến du lịch đến Hoành Sơn sau cả năm trời ôn luyện vất vả và chuẩn bị bước vào đại học. Đến Hoành Sơn, Tuấn muốn thiết kế một hành trình “lên đỉnh siêu dốc", xuất phát từ một ngọn núi nào đó, đi đến các ngọn núi khác với điều kiện ngọn núi sau cao hơn ngọn núi trước, không những thế, độ dốc của cây cầu sau cũng phải lớn hơn độ dốc của cây cầu trước đó. Nghĩa là, nếu như Tuấn quyết định chọn một hành trình đi qua các ngọn núi theo thứ tự \(P_1, P_2, ..., P_k\) thì hành trình đó sẽ phải thỏa mãn tính chất:

Yêu cầu: Hãy giúp hướng dẫn viên du lịch tìm cho Tuấn hành trình “lên đỉnh siêu dốc” qua nhiều đỉnh núi nhất và trả lời thắc mắc của Tuấn là có bao nhiêu hành trình khác nhau đạt được nhiều đỉnh núi nhất như vậy. Hai hành trình gọi là khác nhau nếu như tồn tại một cây cầu của hành trình này không có trong hành trình kia hoặc ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) (\(1 \leq N \leq 3 \cdot 10^5, 1 \leq M \leq 5 \cdot 10^5\)).
• Dòng thứ hai chứa độ cao của \(N\) ngọn núi là \(N\) số nguyên dương \(A_1, A_2, ..., A_n\) (\(1 \leq A_i \leq 10^9\)).
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa cặp số nguyên dương \((U_i, V_i)\) là chỉ số hai ngọn núi là hai đầu của cây cầu thứ \(i\) (\(1 \leq U_i, V_i \leq N\)).

Output

• Dòng đầu tiên ghi ra một số nguyên là số lượng đỉnh núi của hành trình tìm được.
• Dòng thứ hai ghi ra một số nguyên là phần dư trong phép chia số lượng lộ trình khác nhau tìm được cho \(10^9 + 7\).

Example

5 4
1 2 4 4 5
1 2
2 3
3 1
4 5

3
1

Scoring

• Có \(20\%\) số test ứng với \(N \leq 20\).
• Có \(20\%\) số test khác ứng với \(N \leq 500\).
• Có \(20\%\) số test khác ứng với các ngọn núi xếp thành một dãy núi thẳng hàng với nhau, nói cách khác đồ thị tương ứng là một mạch thẳng.
• Có \(20\%\) số test khác ứng với \(M = N - 1\), và các đỉnh trong đồ thị liên thông với nhau.
• \(20\%\) còn lại không có giới hạn gì thêm.