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 <iostream>
#include <algorithm>

#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <cstring>
#include <string>
#include <utility>
#include <array>
#include <complex>
#include <valarray>

#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>


using namespace std;
#define int long long

typedef long long ll;
typedef unsigned long long ull;
//typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double,int> pdi;
typedef pair<long double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll INFLL = 1LL<<62;
const long double EPS = 1e-12;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const long double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod
#define inside(y, x, h, w) (0 <= (y) && (y) < (h) && 0 <= (x) && (x) < (w)) ? true : false

//debug
#define DEBUG

#define DUMPOUT cout

#ifdef DEBUG
#define dump(...) DUMPOUT<<#__VA_ARGS__<<" :["<<__FUNCTION__<<":"<<__LINE__<<"]"<<endl; DUMPOUT<<"    "; dump_func(__VA_ARGS__)
#else
#define dump(...)
#endif

void dump_func() {DUMPOUT << endl;};

template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) == 0) DUMPOUT << " ";
    else DUMPOUT << ", ";
    dump_func(std::move(tail)...);
}

//ostream
template<typename T> ostream& operator << (ostream& os, vector<T>& vec) {
    os << "["; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "]";
    return os;
}

template<typename T, typename U> ostream& operator << (ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

template<typename T, typename U> ostream& operator << (ostream& os, map<T, U>& map_var) {
    os << "[";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")"; itr++;  if(itr != map_var.end()) os << ", "; itr--;
    }
    os << "]";
    return os;
}

template<typename T> ostream& operator << (ostream& os, set<T>& set_var) {
    os << "[";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr; ++itr; if(itr != set_var.end()) os << ", "; itr--;
    }
    os << "]";
    return os;
}

int n, m;
int indeg[3005], outdeg[3005], s[1005], d[1005];
int dp[3005][2];
vector<int> vs;
vector<vector<int>> g(3000 + 3), rg(3000 + 3);
bool visited[3000 + 3];
int v[1000 + 5];
int cnt;

void dfs(int now, int &cv, int &loopv) {
  visited[now] = true;
  for (auto nx : g[now]) {
    if (v[nx] >= n) return;//nx in loop
    nx = v[nx];
    if (visited[nx]) {
      loopv = nx;
      cv = cnt;
      v[now] = cv;
      cnt++;
      return;
    }
    dfs(nx, cv, loopv);
    if (cv == -1) return;
    else {
      v[now] = cv;
      if (now == loopv) {
        cv = -1;
        loopv = -1;
        return;
      }
    }
  }
  return;
}

void dpdfs(int now) {
  for (auto nx : rg[now]) {
    dpdfs(nx);
    dp[now][1] = dp[now][1] * (dp[nx][0] + dp[nx][1]) % mod;
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  rep(i, n) v[i] = i;
  cnt = n;
  rep(i, m) {
    cin >> s[i] >> d[i];
    s[i]--; d[i]--;
    g[s[i]].push_back(d[i]);
    rg[d[i]].push_back(s[i]);
    indeg[d[i]]++;
    outdeg[s[i]]++;
  }
  rep(i, n) {
    int now = i;
    int cv = -1;
    int loopv = -1;
    dfs(now, cv, loopv);
    rep(j, n) visited[j] = false;
  }

  rep(i, n) {
    if (v[i] != i) {
      for (auto prev : rg[i]) {
        if (v[prev] == prev) {
          g[prev].erase(g[prev].begin());
          g[prev].push_back(v[i]);
          rg[v[i]].push_back(prev);
        }
      }
    }
  }
  rep(i, 3000 + 1)rep(j, 2) dp[i][j] = 1;
  //not loop (== line)
  rep(i, n) {
    if (outdeg[i] != 0) continue;
    if (i != v[i]) continue;//vertex_i in loop
    dpdfs(i);
    vs.push_back(i);
  }
  //loop
  rep2(i, n, cnt) {
    dpdfs(i);
    vs.push_back(i);
  }
  int ans = 1;
  sort(all(vs));
  vs.erase(unique(all(vs)),vs.end());
  for (auto i : vs) {
    ans = (ans * (dp[i][0] + dp[i][1])) % mod;
  }
  cout << ans << endl;
}

