题目思路

本题难度较大，需要前置知识强连通分量。

考虑一个人u暗恋另外一个人v，则我们让v连一条有向边到u，表示u属于v的子节点，此时可以构成一个有向图。

然而有可能出现三角恋的情况，即成环，对于成环的情况，在环上只要请了任意一个人来，那环上其它所有点都必须来，所以这种情况我们可以将其缩点为一个人。

缩点需要采用强连通分量的tarjan算法，可以将环缩成一个点。

题目描述

小美有$n$个朋友，她准备请其中一些朋友来吃饭。 其中有一些朋友有暗恋关系：假设a暗恋b，那么小美带上b的时候a也必须去，否则a就会不开心。 小美想知道，一共有多少种不同的请客方案可以让每个人都开心？由于答案可能过大，请对$10^9+7$取模。

输入描述

第一行输入两个正整数$n,m$，代表小美的朋友数量、暗恋的关系数量。 接下来的m行，每行输入两个正整数$u,v$，代表第$u$个人暗恋第$v$个人。 $1\leq n,m \leq 10^5$ $1\leq u,v \leq n$ 保证每个人最多只会暗恋一个人。

输出描述

一个整数，代表小美的请客方案数。

样例1

输入

2 1
1 2

输出

2

说明

两个方案：只请 1 号，或者同时请 1 号和 2 号。
请注意，不能只请 2 号，否则 1 号会不开心。

样例2

输入

3 3
1 2
2 3
3 1

输出

1

说明

显然 3 个人必须全部请客，否则总有人会不开心。