ultimate-product

Richa's class has very friendly atmosphere. Here if two students have a common friend then they become friends to each other. It means that if students 2 and 3 are friends and 2 is friend to 4 as well then 2,3 and 4 all are friends.

Richa's teacher has ask the class to divide themselves in such groups of friends  (each group consists of the students who are friends to each other), and sit in a row. There will be one row for each group.

Richa noticed that there are various ways a group can make the row, that is by exchanging positions among themselves. For example {1,2,3} forms a group than total ways of making a row would be 6

[1,2,3] , [1,3,2] , [2,1,3] , [2,3,1] , [3,1,2] , [3,2,1] .

Now Richa calculates the total ways all groups can form a row and multiply them all, she calls it the ULTIMATE PRODUCT.

You have to calculate the ULTIMATE PRODUCT of a class.

INPUT

First line of input contains two integers N and K, where N is the number of students and K is the number of known friendships. Next K lines contains two integers which are the indices(0 based) of students who are friends to each other.

OUTPUT

Print a single integer which is the ULTIMATE PRODUCT of the class modulus (10^9 + 7)

Constraints:

1 ≤ N ≤ 100000

1 ≤ K ≤ 100000

SAMPLE INPUT
5 2
1 2
3 4

SAMPLE OUTPUT
4

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: