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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <bitset>
   
using namespace std;
   
 
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define rforeach(it, c) for (__typeof__((c).rbegin()) it=(c).rbegin(); it != (c).rend(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CL(arr, val) memset(arr, val, sizeof(arr))
#define COPY(dest, src) memcpy(dest, src, sizeof(dest))
#define ten(n) ((long long)(1e##n))
#define bin(n) (1LL << (n))
#define erep(i, n) for (int i = 0; i <= (int)(n); ++i)
#define revrep(i, n) for (int i = (n); i >= 0; --i)
#define pb push_back

template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }

template <class T> void uniq(T& c) { sort(c.begin(), c.end()); c.erase(unique(c.begin(), c.end()), c.end()); }
 
template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }

template <typename T> void print_container(ostream& os, const T& c) { const char* _s = " "; if (!c.empty()) { __typeof__(c.begin()) last = --c.end(); foreach (it, c) { os << *it; if (it != last) cout << _s; } } }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const set<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const multiset<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const deque<T>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }

template <class T> void print(T a, int n, const string& deli = " ", int br = 1) { for (int i = 0; i < n; ++i) { cout << a[i]; if (i + 1 != n) cout << deli; } while (br--) cout << endl; }
template <class T> void print2d(T a, int w, int h, int width = -1, int br = 1) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) {    if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }

template <class T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
template <class T> void input(T* a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }

void fix_pre(int n) { cout.setf(ios::fixed, ios::floatfield); cout.precision(10); }
void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }
#define trace(x) (cout << #x << ": " << (x) << endl)
 
bool in_rect(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }

typedef long long ll;
typedef pair<int, int> pint;

// y(v): v>^<  y(^): ^>v<
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

const double PI = acos(-1.0);
#define mp make_pair



class SCC
{
private:
    vector<int> vs;	// 帰りの順番, 後ろのほう要素は始点側
    vector<bool> used;

    void dfs(int v)
    {
        used[v] = true;
        for (int i = 0; i < (int)g[v].size(); ++i)
            if (!used[g[v][i]])
                dfs(g[v][i]);
        vs.push_back(v);
    }

    void rdfs(int v, int k)
    {
        used[v] = true;
        component[v] = k;
        for (int i = 0; i < (int)rg[v].size(); ++i)
            if (!used[rg[v][i]])
                rdfs(rg[v][i], k);
    }

public:
    int V;
    vector<vector<int> > g;
    vector<vector<int> > rg;
    vector<int> component;
    int num_components;

    SCC(int V)
        : vs(V), used(V), V(V), g(V), rg(V), component(V), num_components(-1) { }

    void add_edge(int from, int to)
    {
        g[from].push_back(to);
        rg[to].push_back(from);
    }

    // 強連結成分の数を返す
    // O(V + E)
    // グラフの始点側の値(component[v])は小さい
    // 末端は大きい値, 最末端(component[v] == scc() - 1)
    int scc()
    {
        vs.clear();
        fill(used.begin(), used.end(), false);
        for (int i = 0; i < V; ++i)
            if (!used[i])
                dfs(i);

        fill(used.begin(), used.end(), false);
        int k = 0;
        for (int i = vs.size() - 1; i >= 0; --i)
            if (!used[vs[i]])
                rdfs(vs[i], k++);
        return num_components = k;
    }

    // scc_g: graph by components, nodes: the numbers of original graph
    // scc_g can have self loops
    void build_graph(vector<vector<int> >& scc_g, vector<vector<int> >& original_nodes)
    {
        if (num_components == -1)
            scc();

        scc_g.clear();
        scc_g.resize(num_components);
        original_nodes.clear();
        original_nodes.resize(num_components);


        for (int i = 0; i < V; ++i)
            original_nodes[component[i]].push_back(i);

        for (int i = 0; i < V; ++i)
            for (int j = 0; j < (int)g[i].size(); ++j)
                if (component[i] != component[g[i][j]]) // remove self loop
                    scc_g[component[i]].push_back(component[g[i][j]]);

        // remove duplicated edges (O(ElogE)... decrease complexity???)
        for (int i = 0; i < num_components; ++i)
        {
            sort(scc_g[i].begin(), scc_g[i].end());
            scc_g[i].erase(unique(scc_g[i].begin(), scc_g[i].end()), scc_g[i].end());
        }
    }
};

const ll mod = ten(9) + 7;
vector<vector<int> > g, ori;
ll dfs(int cur, int par)
{
    ll bend = 1;
    if (g[cur].size() > 0)
    {
        rep(i, g[cur].size())
        {
            int to = g[cur][i];
            if (to != par)
                (bend *= dfs(to, cur) + 1) %= mod;
        }
    }
    return bend;
}
int main()
{
    int n, m;
    cin >> n >> m;

    SCC scc(n);
    rep(i, m)
    {
        int s, d;
        cin >> s >> d;
        --s, --d;
        scc.add_edge(d, s); // parent(s) = d
    }

    scc.build_graph(g, ori);
    
    bool root[1111];
    fill_n(root, g.size(), true);
    rep(i, g.size()) rep(j, g[i].size())
        root[g[i][j]] = false;

    ll res = 1;
    rep(i, g.size())
        if (root[i])
            (res *= dfs(i, -1) + 1) %= mod;

    cout << res << endl;
}