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>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}
class UnionFind {
    vector<int> par, h;
public:
    UnionFind(int size) {
        par.assign(size, 0);
        h.assign(size, 0);
        REP(i, size) par[i] = i;
    }
    void unite(int u, int v) {
        u = root(u), v = root(v);
        if (u == v) return;
        if (h[u] > h[v]) {
            par[v] = u;
        }
        else if (h[u] < h[v]) {
            par[u] = v;
        }
        else {
            ++h[u];
            par[v] = u;
        }
    }
    bool isUnited(int u, int v) {
        return root(u) == root(v);
    }
    int root(int v) {
        if (par[v] == v) return v;
        return par[v] = root(par[v]);
    }
};
void scc_dfs(ll v, vector<bool>& used, vector<ll>& vs, const vector< vector<ll> >& G) {
    used[v] = true;
    each(to, G[v]) {
        if (!used[to]) scc_dfs(to, used, vs, G);
    }
    vs.pb(v);
}
void scc_rdfs(ll v, ll k, vector<bool>& used, vector<ll>& cmp, const vector< vector<ll> >& rG) {
    used[v] = true;
    cmp[v] = k;
    each(to, rG[v]) {
        if (!used[to]) scc_rdfs(to, k, used, cmp, rG);
    }
}
// cmpが返る
// 同じcmpは強連結成分
// cmp[i] < cmp[j] なら j から i に行けない
vector<ll> scc(const vector< vector<ll> >& G) {
    const ll n = G.size();
    vector<bool> used(n, false);
    vector<ll> vs;
    rep(i, n) {
        if (!used[i]) scc_dfs(i, used, vs, G);
    }
    used.assign(n, false);
    vector< vector<ll> > rG(n);
    rep(i, n) {
        each(to, G[i]) {
            rG[to].pb(i);
        }
    }
    vector<ll> res(n);
    ll k = 0;
    rrep(i, vs.size()) {
        if (!used[vs[i]]) scc_rdfs(vs[i], k++, used, res, rG);
    }
    return res;
}
vector< vector<ll> > get_scc_graph(const vector<ll>& cmp, const vector< vector<ll> >& G) {
    vector< vector<ll> > res(*max_element(all(cmp))+1);
    rep(i, G.size()) {
        each(to, G[i]) {
            if (cmp[i] != cmp[to]) {
                res[cmp[i]].pb(cmp[to]);
            }
        }
    }
    rep(i, res.size()) {
        sort(all(res[i]));
        res[i].erase(unique(all(res[i])), res[i].end());
    }
    return res;
}
const ll mod = 1000000007;
ll mul(ll a, ll b) {
    return a * b % mod;
}
ll mul(initializer_list<ll> t) {
    ll res = 1;
    each(v, t) res = mul(res, v);
    return res;
}
ll add(ll a, ll b) {
    return (a + b) % mod;
}
ll add(initializer_list<ll> t) {
    ll res = 0;
    each(v, t) res = add(res, v);
    return res;
}
ll sub(ll a, ll b) {
    return (a - b + mod) % mod;
}
ll sub(initializer_list<ll> t) {
    auto it = t.begin();
    ll res = *(it++);
    while (it != t.end()) {
        res = sub(res, *(it++));
    }
    return res;
}
ll power(ll x, ll n) {
    ll res = 1;
    for (ll i = 1; i <= n; i <<= 1) {
        if (i & n) res = mul(res, x);
        x = mul(x, x);
    }
    return res;
}
ll inv(ll n) {
    return power(n, mod-2);
}
ll divi(ll a, ll b) {
    return mul(a, inv(b));
}
ll divi(initializer_list<ll> t) {
    auto it = t.begin();
    ll res = *(it++);
    while (it != t.end()) {
        res = divi(res, *(it++));
    }
    return res;
}
vector<ll> fact;
void init_fact(ll n) {
    fact.assign(n+1, 1);
    FOR(i, 1, fact.size()) {
        fact[i] = mul(fact[i-1], i);
    }
}

ll comb(ll n, ll r) {
    if (r < 0) return 0;
    if (r > n) return 0;
    return divi(fact[n], mul(fact[r], fact[n-r]));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, m; cin >> n >> m;
    vector<vector<ll>> G(n);
    rep(i, m) {
        ll a, b; cin >> a >> b; --a, --b;
        G[a].pb(b);
    }
    vector<ll> cmp = scc(G);
    G = get_scc_graph(cmp, G);
    n = G.size();
    vector<vector<ll>> rG(n);
    rep(from, n) each(to, G[from]) {
        rG[to].pb(from);
    }
    function<ll(ll)> dfs = [&](ll v) {
        // True
        ll res = 1;
        each(from, rG[v]) {
            res = mul(res, dfs(from));
        }
        // All False
        res = add(res, 1);
        return res;
    };
    ll ans = 1;
    rep(i, n) if (G[i].size() == 0) {
        ll ptn = 1;
        each(j, rG[i]) {
            ptn = mul(ptn, dfs(j));
        }
        ptn = add(ptn, 1);
        ans = mul(ans, ptn);
    }
    cout << ans << endl;
}