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 <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

typedef int Weight; // int型におさまらないときはlong longに変更
struct Edge{
  int src, dst;
  Weight cost;
  Edge(int f, int t, Weight c) : src(f), dst(t), cost(c) {}
};
bool operator<(const Edge& a, const Edge& b){
  return a.cost < b.cost;
}


// 隣接リスト
typedef vector<Edge> Node;
typedef vector<Node> Graph;

// 隣接行列
typedef vector<Weight> Array;
typedef vector<Array> Matrix;


//Strongly Connected Components(強連結成分)

//Step1
void SCC_dfs(const Graph& G, vector<bool>& visit, vector<int>& order, int v){
  visit[v] = true;
  REP(i, G[v].size()){
    int dst = G[v][i].dst;
    if(!visit[dst]) SCC_dfs(G, visit, order, dst);
  }
  order.push_back(v);
}

//Step2
Graph reverse_graph(const Graph& G){
  Graph revG(G.size());
  REP(i, G.size()){
    REP(j, G[i].size()){
      const Edge &e = G[i][j];
      revG[e.dst].push_back(Edge(e.dst, e.src, e.cost));
    }
  }
  return revG;
}

//Step3
void SCC_rdfs(const Graph& G, vector<bool>& visit, vector<int>& comp, int v, int k){
  visit[v] = true;
  REP(i, G[v].size()){
    int dst = G[v][i].dst;
    if(!visit[dst]) SCC_rdfs(G, visit, comp, dst, k);
  }
  comp[v] = k;
}

//SCC分解
int SCC(const Graph& G, vector<int>& comp){
  Graph revG = reverse_graph(G);
  comp = vector<int>(G.size());
  vector<bool> visit(G.size());
  vector<int> order(G.size());
  int k = 0;
  REP(i, G.size()) if(!visit[i]) SCC_dfs(G, visit, order, i);
  reverse(order.begin(), order.end()); //(orderにはトポロジカル順序が入る)

  visit = vector<bool>(G.size());
  REP(i, order.size()){
    if(!visit[order[i]]) SCC_rdfs(revG, visit, comp, order[i], k++);
  }
  return k;
}

ll memo[1000][2];

ll dfs(const Graph& G, vector<bool>& used, int u, int k){
  if(memo[u][k] != -1) return memo[u][k];
  used[u] = true;
  ll c0 = 1;
  ll c1 = 1;
  for(int i = 0; i < G[u].size(); i++){
    int dst = G[u][i].dst;
    c0 *= dfs(G, used, dst, 0);
    c0 %= MOD;
    c1 *= dfs(G, used, dst, 1);
    c1 %= MOD;
  }
  if(k == 0) memo[u][k] = (c0 + c1) % MOD;
  else memo[u][k] = c1;
  return memo[u][k];
}
int main(){
  int N, M;
  while(cin>>N>>M && N){
    memset(memo, -1, sizeof(memo));
    Graph G(N);
    REP(i, M){
      int S, D;
      cin>>S>>D;
      S--; D--;
      G[S].push_back(Edge(S, D, 1));
    }
    vector<int> comp;
    int L = SCC(G, comp);
    Graph SG_rev(N);
    REP(i, N){
      REP(j, G[i].size()){
        Edge& e = G[i][j];
        int src = comp[e.src];
        int dst = comp[e.dst];
        if(src != dst){
          SG_rev[dst].push_back(Edge(dst, src, 1));
        }
      }
    }
    vector<bool> used(N);
    ll ans = 1;
    for(int i = L - 1; i >= 0; i--){
      if(!used[i]) ans = (ans * dfs(SG_rev, used, i, 0)) % MOD;
    }
    cout<<ans<<endl;
  }
  return 0;
}