Trong một đồ thị có hướng, hai đỉnh ~u~ và ~v~ được gọi là liên thông mạnh nếu tồn tại đường đi từ ~u~ đến ~v~ và đường đi từ ~v~ đến ~u~. Tính chất này có tính bắc cầu, nên các đỉnh được chia thành những tập gọi là thành phần liên thông mạnh (SCC). Một đỉnh trong SCC thì liên thông mạnh với tất cả các đỉnh trong cùng SCC (kể cả chính nó), và không liên thông mạnh với bất kỳ đỉnh nào ngoài SCC đó.

Trong giờ học đồ thị, An vẽ một đồ thị có hướng với ~n~ đỉnh và đánh dấu các SCC của nó. Trong giờ nghỉ, Bình nghịch ngợm xóa hướng của một số cạnh. Anh ta muốn An có thể khôi phục duy nhất hướng đã xóa dựa vào thông tin về các cạnh còn lại và phân hoạch các SCC sau giờ nghỉ.

Hãy giúp Bình xác định số cạnh tối đa có thể xóa hướng, và số cách chọn tập cạnh đó.

Cụ thể, cần tìm tập con ~A~ của các cạnh sao cho:

• Nếu xóa hướng các cạnh trong ~A~, thì dựa vào phân hoạch SCC ban đầu và các cạnh còn lại, ta có thể khôi phục duy nhất hướng của các cạnh trong ~A~ sao cho các SCC không đổi.

In ra kích thước lớn nhất của tập ~A~, và số tập như vậy. Do số tập có thể rất lớn, hãy in ra modulo ~10^9+7~.

Input

• Dòng ~1~: ba số nguyên ~n, m~ ~(2 \le n, m \le 2000; 1 \le m \le 2000)~;

• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~u_i, v_i~ ~(1 \le u_i, v_i \le n; u_i \ne v_i)~. Bảo đảm không có hai cạnh trùng nhau, giữa hai đỉnh có nhiều nhất một cạnh, không phân biệt hướng.

Output

• Dòng ~1~: số nguyên ~k~ là kích thước lớn nhất của tập cạnh có thể xóa hướng;

• Dòng ~2~: số nguyên ~c~ là số tập cạnh như vậy modulo ~10^9+7~.

Scoring

Sample Input 1

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

Sample Output 1

3
3