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
/*
 * Package: StandardCodeLibrary.Core
 * */
//蠑戊ソ帛クク逕ィ逧?、エ譁?サカ蟷カ菴ソ逕ィstd蜷榊ュ礼ゥコ髣エ
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <utility>
#include <vector>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <bitset>
#include <complex>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <climits>
using namespace std;

////蟶ク逕ィ謨ー謐ョ邀サ蝙?//typedef long long int lli;
//typedef vector<int> vi;
//typedef vector<vi> vvi;
//typedef pair<lli,lli> pll;
//typedef queue<int> qi;
typedef long T;

int MOD=1000000007;

//蟶ク逕ィ蜃ス謨ー:譛?、ァ譛?ー丞?譖エ譁ー;謨ー蟄ヲ逶ク蜈ウ蜃ス謨ー;霎灘?蜥瑚セ灘?;譬醍憾謨ー扈?蟷カ譟・髮?蜿ッ蜷亥ケカ蝣?
template<typename type>inline bool cmax(type& a,const type& b){return a<b?a=b,true:false;}
template<typename type>inline bool cmin(type& a,const type& b){return b<a?a=b,true:false;}

const int MAXV=1000;
const int MAXE=1000000;
typedef struct struct_edge* edge;
struct struct_edge{int v;edge n;}pool[MAXE];
edge top;
int V;
edge adj[MAXV];
void build_graph(int v)
{
	top=pool,memset(adj,0,sizeof adj);
	V=v;//轤ケ謨ー
	//add_edge(u,v);
}
void add_edge(int u,int v)
{
	top->v=v,top->n=adj[u],adj[u]=top++;
}
int ord;
int dfn[MAXV];
int low[MAXV];
int stks;
int stk[MAXV];
bool ins[MAXV];
int cnt;
int bl[MAXV];
void dfs(int u)
{
	dfn[u]=low[u]=++ord;
	ins[stk[stks++]=u]=true;
	for (edge i=adj[u];i;i=i->n)
		if (!dfn[i->v]) dfs(i->v),cmin(low[u],low[i->v]);
		else if (ins[i->v]) cmin(low[u],dfn[i->v]);
	if (dfn[u]==low[u])
	{
		int v;
		do ins[v=stk[--stks]]=false,bl[v]=cnt;
		while(v!=u);
		cnt++;
	}
}
void tarjan()
{
	ord=0,memset(dfn,0,sizeof dfn),cnt=0;
	for(int i=0;i<V;i++) if (!dfn[i]) dfs(i);
}

int main()
{
	int n,m;
	cin>>n>>m;
	build_graph(n);
	for(int i=0;i<m;i++)
	{
		int s,d;
		cin>>s>>d,--s,--d;
		add_edge(s,d);
	}
	tarjan();
	vector<vector<int> > adj(cnt);
	vector<vector<int> > radj(cnt);
	for(int i=0;i<V;i++) for (edge e=::adj[i];e;e=e->n) if (bl[i]!=bl[e->v]) adj[bl[i]].push_back(bl[e->v]);
	for(int i=0;i<cnt;i++) sort(adj[i].begin(),adj[i].end()),unique(adj[i].begin(),adj[i].end());
	vector<int> id(cnt);
	for(int i=0;i<cnt;i++) for (int j=0;j<adj[i].size();j++) id[adj[i][j]]++;
	queue<int> q;
	vector<pair<long long int,long long int> > f(n);
	for(int i=0;i<cnt;i++) if (id[i]==0) q.push(i),f[i]=make_pair(1,1);
	long long int ans=1;
	while(q.size())
	{
		int u=q.front();
		q.pop();
		if (!adj[u].size()) ans=(ans*(f[u].first+f[u].second))%MOD;
		for(int i=0;i<adj[u].size();i++)
		{
			int v=adj[u][i];
			radj[v].push_back(u);
			if ((--id[v])==0)
			{
				q.push(v);
				f[v]=make_pair(1,1);
				for (int j=0;j<radj[v].size();j++)
				{
					int w=radj[v][j];
					f[v].first*=f[w].first+f[w].second;
					f[v].second*=f[w].second;
					f[v].first%=MOD;
					f[v].second%=MOD;
				}
			}
		}
	}
	cout<<ans<<endl;
}