Natsuki and her friends were taken to the space by an alien and made friends with a lot of aliens. During the space travel, she discovered that aliens’ hands were often very different from humans’. Generally speaking, in a kind of aliens, there are N fingers and M bend rules on a hand. Each bend rule describes that a finger A always bends when a finger B bends. However, this rule does not always imply that the finger B bends when the finger A bends.

When she were counting numbers with the fingers, she was anxious how many numbers her alien friends can count with the fingers. However, because some friends had too complicated rule sets, she could not calculate those. Would you write a program for her?



Input

N M
S1 D1
S2 D2
.
.
.
SM DM


The first line contains two integers N and M (1 ≤ N ≤ 1000, 0 ≤ M ≤ 1000) in this order. The following M lines mean bend rules. Each line contains two integers Si and Di in this order, which mean that the finger Di always bends when the finger Si bends. Any finger appears at most once in S.

Output

Calculate how many numbers her alien friends can count with the fingers. Print the answer modulo 1000000007 in a line.

Examples

Input

5 4
2 3
3 4
4 3
5 4


Output

10


Input

5 5
1 2
2 3
3 4
4 5
5 1


Output

2


Input

5 0


Output

32
#include<queue>
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const ll M=1000000007;

ll dfs(int u,const vector<int> *T){
	if(T[u].empty()) return 2;
	ll res=1;
	rep(i,T[u].size()){
		int v=T[u][i];
		res=res*dfs(v,T)%M;
	}
	return (res+1)%M;
}

// ツ出ツ篠淞青板つェツ債つ々 1 ツづ?つ「ツつ、ツ青ァツ姪アツつゥツづァ, ツ連ツ個仰青ャツ閉ェツづ債δ仰ーツプツづ可姪伉つェツつュツづ?づつつ「ツつスツ形ツづ可づ按づゥ
// ツつアツづ個連ツ個仰青ャツ閉ェツづ可づつつ「ツづ?づ個嘉ーツづーツ仰?づ淞づゥ
ll solve(int n,const int *G){
	vector<int> G2[1000]; // G ツづ個陛督づ個古シツつォツづーツ逆ツ転ツつオツつスツグツδ可フ
	rep(u,n) if(G[u]!=-1) G2[G[u]].push_back(u);

	// ツδ仰ーツプツ個淞出
	rep(u,n){
		int v=u;
		bool vis[1000]={};
		while(G[v]!=-1 && !vis[v]){
			vis[v]=true;
			v=G[v];
		}
		if(v==u){ // ツδ仰ーツプorツ債ェツつェツ個ゥツづつつゥツづ?つス
			ll res=1;
			int v=u;
			do{
				// ツδ仰ーツプツ湘」ツづ個各ツ陳クツ点ツづーツ債ェツづ?つキツづゥツ姪伉づ可づつつ「ツづ?督堋つヲツづーツ仰?づ淞づ? ツつサツづェツづァツづーツつゥツつッツつ?づュツつケツづゥ
				rep(i,G2[v].size()){
					int w=G2[v][i];
					if(!vis[w]) res=res*dfs(w,G2)%M;
				}
				v=G[v];
			}while(v!=u && v!=-1);
			return (res+1)%M; // ツづ?づェツづ?選ツづ篠づ按つ「ツづ?つ「ツつ、ツ嘉ーツつェツつ?づゥツづ個づ?+1
		}
	}
	for(;;);
}

int main(){
	int n,m; scanf("%d%d",&n,&m);
	int to[1000];
	rep(u,n) to[u]=-1;
	rep(i,m){
		int u,v; scanf("%d%d",&u,&v); u--; v--;
		to[u]=v;
	}
	vector<int> G[1000]; // ツ鳴ウツ古シツグツδ可フ
	rep(u,n) if(to[u]!=-1) {
		int v=to[u];
		G[u].push_back(v);
		G[v].push_back(u);
	}

	ll ans=1;
	bool vis[1000]={};
	rep(u,n) if(!vis[u]) {
		vis[u]=true;

		vector<int> cc;
		queue<int> Q; Q.push(u);
		while(!Q.empty()){ // ツ偲」ツ連ツ個仰青ャツ閉ェツつイツづ?づ可陳イツづ猟づゥ
			int u=Q.front(); Q.pop();
			cc.push_back(u);
			rep(i,G[u].size()){
				int v=G[u][i];
				if(!vis[v]) vis[v]=true, Q.push(v);
			}
		}

		int N=cc.size();
		int D[1000]; // ツ偲」ツ連ツ個仰づ按有ツ古シツグツδ可フ
		rep(i,N) D[i]=-1;
		rep(i,N) rep(j,N) {
			int u=cc[i],v=cc[j];
			if(to[u]==v) D[i]=j;
		}
		ans=ans*solve(N,D)%M;
	}

	printf("%lld\n",ans);

	return 0;
}