ADAPANEL - Ada and Panels


Ada the Ladybug has proved successful in solving some hard problems, so a construction company has asked her to solve a problem for them. There are multiple cities in the country and each city owns exactly one panel-block. There are also unidirectional roads between some pairs of cities (note that circular self-roads and multi-roads with several traffic lines are allowed). A city can sell its panel-block to any city, to which they could transport the panel block, and from which they can bring back their reward for it (i.e. there must be a path from actual city to destination city and back). As long a city has K panel-blocks, it builds a prefab of height K which looks exactly same as each other prefab of height K.

The construction company notes all the heights down and puts them in an array. They are wondering how many distinct arrays are possible by moving the panel blocks between cities. However there is a catch. Consider a set of cities in which each city is reachable by every other city. Since we can easily shuffle the panel blocks between such a set of cities, we can create new permutations with the same set of heights. The construction company will NOT count any such cases. Hence they will only consider the distinct set of heights for such a set of cities.

You have proved successful in helping Ada with some hard problems, so she has asked you to help her. Your job is following - count the number of possible structures which could arise. Since this number might be pretty big, you have to output it modulo 109+7.

Input

The first line contains two integers 1 ≤ N, M ≤ 2*105, the number of cities an the number of unidireectional roads between them.

The next M lines contains two integers 0 ≤ a, b < N, the road from city a to city b

Output

Print a single line - the number of possible structures modulo 1000000007.

Example Input

7 9
0 1
1 2
2 3
3 1
2 0
4 5
5 4
6 4
5 6

Example Output

15

Example Input 2

7 7
0 1
1 2
2 3
3 4
4 5
5 6
6 0

Example Output 2

15

Example Input 3

6 3
0 1
3 2
4 5

Example Output 3

1

Example Input 4

8 7
0 1
1 0
2 3
3 2
4 5
5 6
6 4

Example Output 4

12

hide comments
Rafail Loizou: 2023-08-03 03:42:44

I solved this problem 2 years ago. A guy that I help train stumbled upon it randomly and saw that I solve it (and probably is reading this comment now) and asked for me to give an explanation on how I solved it. I'm reading my code for an hour now and I can't seem to understand the wicked combinatorics formulas I used to get the AC. It was all intuitive back then but now without any comments around other than me swearing on debug loops I guess I will have to re-solve the problem from scratch. SMH... At least anybody reading this comment: Learn from MY mistake so you don't REPEAT them and write comments even for math formulas to show how you derived them and explain your thinking step-by-step. It's in-efficient and a pity not to have that type of information in the future.

On a site note: This site used to be more lively back in the day what happened to it? Am I getting old? What is this? It was also dead-ish 2 years ago even. Should I make a re-run and try to break on the top 100 of this site finally? A site that is like a silent blissful graveyard of accounts of old giants. Nothing in this world is eternal. Forever young. Even this beautiful site I guess.

«Ματαιότης ματαιοτήτων τα πάντα ματαιότης» (Εκκλ. 1, 2)
«Vanity of Vanities all is Vanity» (Ecclesiastes 1, 2)

But I promise. If I get an answer to this comment I will be back for another run (or climb to be more precise).

Last edit: 2023-08-03 03:44:48
nadstratosfer: 2021-01-07 00:01:16

Interesting problem comprising 2 difficult and otherwise unrelated concepts. Reasonable TL allows AC in PyPy. Once again good job, Morass.

sanjitpd_777: 2020-09-15 10:27:31

Add some explanation.

kanishk779: 2019-03-24 15:15:36

What is the meaning of the distinct array in this problem?


Added by:Morass
Date:2017-07-31
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All