Problem 1080 --妹妹与排队

1080: 妹妹与排队

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 65  Solved: 17
[Submit][Status][Web Board][Creator:]

Description

妹妹们每天都会因为排队的事情吵得不可开交,每个人都想排在最前面。你需要为妹妹们尽可能安排公平的排队方式。考虑现在一共有三个妹妹,合法的排队方式有{(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)}这6种。那么对你而言,公平的方式就是以6天为一个周期,每天选择其中的一种安排方式,并且6天中每天选择不同的排队方式。妹妹们基本认可了你的安排策略,不过还有一些细节问题。众所周知,在这个世界里有一些妹妹会具有相同的感受。一旦两个妹妹的感受变得完全相同,那么这两个妹妹将变得完全不可区分。例如,如果妹妹1与妹妹2的感受变得完全相同,那么排队方式(1, 2, 3)和排队方式(2, 1, 3)对她们而言将会是同一种排队方式。这种情况下,上述排队方式中,不同的方式其实只有3种。特别的,如果1号妹妹与2号妹妹感受相同,2号妹妹与3号妹妹感受相同,那么1号妹妹与3号妹妹的感受也是相同的,即上述所有方案都是等价的。

Input

第一行是两个整数N M。N表示妹妹的数量,妹妹们依次编号为1到N。 接下来有M行,每行两个整数1<=u,v<=N,表示妹妹u与妹妹v的感受完全相同。

1 <= N , M <= 1e6

Output

输出一个整数,表示不同的排队方案数 % 1000000007的结果。

Sample Input

3 1
1 2

Sample Output

3

HINT

输入中可能出现u==v的情况,如果曾经出现过1 2,不保证1 2不再出现。

Source

[Submit][Status]