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 <bits/stdc++.h>
#include <iomanip>
 
using namespace std;
 
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;
typedef vector<int> VI;
typedef vector<char> VB;
 
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()
 
const LD eps=1e-5;
//const long long INF=(LL)(1e9)*(LL)(1e9);
const int INF=1e9;
 
template<class T>
void chmin(T& a, const T& b)
{
	if(a>b)
		a=b;
}
template<class T>
void chmax(T& a, const T& b)
{
	if(a<b)
		a=b;
}
 
const LL pow(const LL p, const LL q)
{
	LL t=1;
	REP(i,q)
		t*=p;
	return t;
}


struct Edge
{
    int to,from,cost;
    Edge(int to_,int from_,int weight_):to(to_),from(from_),cost(weight_)
    {}

};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

const Graph reverse_edge_Graph(const Graph& g)
{
    Graph rg(g.size());
    for(auto&& es : g)
        for(auto&& e : es)
            rg[e.to].push_back(Edge(e.from,e.to,e.cost));
    return rg;
}

const tuple<vector<int>,vector< vector<int>>> SCC(const Graph& g) //StronglyConnectedComponent
{
    const int n = g.size();
    Graph rg(reverse_edge_Graph(g));
    vector<int> vs;
    vector<char> reach(n);  //vector<bool>
    vector<vector<int> > scc;
    vector<int> scc_vectormap(n);

    function<void(const int)> dfs = [&](const int v)
    {
        reach[v]=1;
        for(auto&& e : g[v])
            if(!reach[e.to]) dfs(e.to);
        vs.push_back(v);
    };
    function<void(const int, const int)> rdfs = [&](const int v, const int k)
    {
        reach[v]=1;
        scc[k].push_back(v);
        scc_vectormap[v]=k;
        for(auto&& e : rg[v])
            if(!reach[e.to]) rdfs(e.to, k);
    };

    for(int i=0;i<n;i++)
        if(!reach[i]) dfs(i);
    fill(reach.begin(), reach.end(), 0);
    int k=0;
    for(int i=vs.size()-1;i>=0;i--)
        if(!reach[vs[i]]) 
        {
            scc.push_back(vector<int>());
            rdfs(vs[i], k++);
        }
    return tuple<vector<int>, vector<vector<int>> >(scc_vectormap, scc);
}

const Graph DAG_from_SCC(int DAG_size, Graph& g, vector<int>& scc_vectormap)
{
    Graph dag(DAG_size);
    for(auto&& es : g)
        for(auto&& e : es)
        {
            if(scc_vectormap[e.from]==scc_vectormap[e.to]) continue;
            dag[scc_vectormap[e.from]].push_back(Edge(scc_vectormap[e.to], scc_vectormap[e.from], 0));
        }
    return dag;
}


class Mod
{
    private:
        static const long long MODULO = 1e9+7;
        long long value;

        const void Normalize()
        {
            value=value<0?(value%MODULO+MODULO):(value%MODULO);
        }

    public:
        Mod():value(0){}
        Mod(const long long &val)
        {
            value=val;
            Normalize();
        }
        
        explicit operator long long () const
        {
            return value;
        }

        const Mod operator -() const
        {
            return Mod(MODULO - value);
        }
        const Mod operator +(const Mod &rhs) const
        {
            return Mod(value + rhs.value);
        }
        const Mod operator -(const Mod &rhs) const
        {
            return Mod(value + (-rhs).value);
        }
        const Mod operator *(const Mod &rhs) const
        {
            return Mod(value * rhs.value);
        }
        Mod &operator +=(const Mod &rhs)
        {
            return *this = *this + rhs;
        }
        Mod &operator -=(const Mod &rhs)
        {
            return *this = *this - rhs;
        }
        Mod &operator *=(const Mod &rhs)
        {
            return *this = *this * rhs;
        }


        Mod pow(long long p) const;

        Mod inv() const
        {
            return pow(MODULO-2);
        }

        const Mod operator /(const Mod &rhs) const
        {
            return *this * rhs.inv();
        }
        Mod &operator /=(const Mod &rhs)
        {
            return *this = *this / rhs;
        }  
        bool operator ==(const Mod &rhs)
        {
            return value == rhs.value;
        }
};

Mod Mod::pow(long long p) const
{
    Mod tmp=1, mult=*this;
    while(p)
    {
        if((p&1)>0) tmp*=mult;
        p>>=1;
        mult*=mult;
    }
    return tmp;
}

namespace std
{
    ostream& operator<<(ostream& os, const Mod mod)
    {
        os<<(long long)mod;
        return os;
    }
};

int main()
{
	//cin.tie(0);
	//ios::sync_with_stdio(false);
    
    int v,e;
    cin>>v>>e;
    Graph g(v);
    REP(i,e)
    {
        int s,t;
        cin>>s>>t;
        t--;
        s--;
        g[s].push_back(Edge(t,s,0));
    }
    VI mp;
    vector<VI> hoge;
    tie(mp,hoge) = SCC(g);

    Graph dag=DAG_from_SCC(hoge.size(),g, mp);
    Graph rdag=reverse_edge_Graph(dag);
    vector<char> nr(rdag.size());
    for(auto&& es:rdag)
    {
        for(auto&& e:es)
        {
            nr[e.to]=1;
        }
    }

    function<Mod(const int)> dfs = [&](const int v)
    {
        if(rdag[v].size()==0) return Mod(1);
        vector<Mod> ed;
        for(auto&& e:rdag[v])
        {
            ed.push_back(dfs(e.to)+1);
        }
        Mod s=1;
        REP(i,ed.size())
            s*=ed[i];
        //cout<<"hoge"<<v<<" "<<s<<endl;
        return s;
    };

    vector<Mod> s;
    for(int i=0;i<nr.size();i++)
    {
        if(nr[i]) continue;
        s.push_back(dfs(i)+1);
        //cout<<i<<" "<<s[s.size()-1]<<endl;
    }
    Mod ans=1;
    REP(i,s.size())
        ans*=s[i];
    cout<<ans<<endl;
}