Gautam Buddha University V.C. has planned a tour for GBU students. For the tour, V.C. decided to book cars. The students are ready to go on one condtition:
If two students are friends then they do not want to go in different cars.
Due to this condition, V.C. cannot decide that how many cars will be needed for the tour. And for each car he also needs one leader in the car.
As you are a programmer, so V.C. is giving you this task. Find the maximum number of cars he will need for the tour and the total number of ways of selecting leader in each car.
Input:
First line contains n, which denotes the number of students that will go for the tour.
Second line contains m, which denotes the number of friendship relation between students.
Next m lines will have two space separated integers a,b.
Consider mutual friendship(a is a friend of b and vice versa).
Output:
Output a single line containing two space separated integers - maximum number of cars he will be needed and the number of ways of selecting the leaders. Leaders will be modulo (106)+7.
Note: Assume Capacity of a Car is unlimited.
Constraints:
1<=n<=105
1<=m<=105
1<=a,b<=105
In this sample we need three cars in which students are (1,2) ,(3,4),(5,6) and total number ways of selecting leaders in cars will be 8.
