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<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"


typedef int Weight;
struct Edge {
	int src, dst;
	Weight weight;
	Edge(int src, int dst, Weight weight) :
		src(src), dst(dst), weight(weight) { }
};
struct Dscc {
public:

	//belongs,newedges
	pair<vector<vector<int>>, vector<vector<int>>>get(const vector<vector<int>>&edges) {
		nums.resize(edges.size());
		fill(nums.begin(), nums.end(), -1);
		vector<vector<int>>revedges(edges.size());
		for (int i = 0; i < edges.size(); ++i) {
			for (auto j : edges[i]) {
				revedges[j].push_back(i);
			}
		}
		int num = 0;
		for (int i = 0; i < edges.size(); ++i) {
			dfs(i, num, edges);
		}
		vector<int>big(nums.size());
		for (int i = 0; i < nums.size(); ++i) {
			big[nums[i]] = i;
		}
		reverse(big.begin(), big.end());
		unis.resize(edges.size());
		fill(unis.begin(), unis.end(), -1);
		num = 0;
		for (int i = 0; i < big.size(); ++i) {

			dfs2(big[i], num, revedges);
			num++;
		}
		vector<int>nums;
		for (int i = 0; i < unis.size(); ++i) {
			nums.push_back(unis[i]);
		}
		sort(nums.begin(), nums.end());
		nums.erase(unique(nums.begin(), nums.end()), nums.end());


		map<int, int>mp;
		for (int i = 0; i < nums.size(); ++i) {
			mp[nums[i]] = i;
		}
		for (int i = 0; i < unis.size(); ++i) {
			unis[i] = mp[unis[i]];
		}

		vector<vector<int>>belongs(nums.size());
		for (int i = 0; i < unis.size(); ++i) {
			belongs[unis[i]].push_back(i);
		}
		vector<vector<int>>newedges(nums.size());
		for (int i = 0; i < edges.size(); ++i) {
			for (auto j : edges[i]) {
				if (unis[i] != unis[j]) {
					newedges[unis[i]].push_back(unis[j]);
				}
			}
		}
		return make_pair(belongs, newedges);
	}

	//belongs,newedges
	pair<vector<vector<int>>, vector<vector<Edge>>>get(const vector<vector<Edge>>&edges) {
		const int old_node_size = edges.size();
		nums.resize(old_node_size);
		fill(nums.begin(), nums.end(), -1);
		vector<vector<Edge>>revedges(old_node_size);
		for (const auto& e : edges) {
			for (const auto& j : e) {
				revedges[j.dst].push_back(Edge(j.dst, j.src, j.weight));
			}
		}
		int num = 0;
		for (int i = 0; i < old_node_size; ++i) {
			dfs(i, num, edges);
		}
		vector<int>big(old_node_size);
		for (int i = 0; i < old_node_size; ++i) {
			big[nums[i]] = i;
		}
		reverse(big.begin(), big.end());

		unis.resize(old_node_size);
		fill(unis.begin(), unis.end(), -1);

		num = 0;
		for (int i = 0; i < old_node_size; ++i) {
			dfs2(big[i], num, revedges);
			num++;
		}
		vector<int>nums;
		for (int i = 0; i < old_node_size; ++i) {
			nums.push_back(unis[i]);
		}

		sort(nums.begin(), nums.end());
		nums.erase(unique(nums.begin(), nums.end()), nums.end());
		const int new_node_size = nums.size();

		map<int, int>mp;
		for (int i = 0; i < new_node_size; ++i) {
			mp[nums[i]] = i;
		}
		for (int i = 0; i < old_node_size; ++i) {
			unis[i] = mp[unis[i]];
		}

		vector<vector<int>>belongs(new_node_size);
		for (int i = 0; i < old_node_size; ++i) {
			belongs[unis[i]].push_back(i);
		}
		vector<vector<Edge>>newedges(new_node_size);
		for (const auto& e : edges) {
			for (const auto& j : e) {
				if (unis[j.src] != unis[j.dst]) {
					newedges[unis[j.src]].push_back(Edge(unis[j.src], unis[j.dst], j.weight));
				}
			}
		}
		return make_pair(belongs, newedges);
	}
private:
	vector<int>nums;
	vector<int>unis;

	void dfs(const int id, int &num, const vector<vector<int>>&edges) {
		if (nums[id] != -1)return;
		else {
			nums[id] = -2;
			for (auto i : edges[id]) {
				dfs(i, num, edges);
			}
		}
		nums[id] = num++;
		return;
	}
	void dfs2(const int id, const int &num, const vector<vector<int>>&edges) {
		if (unis[id] != -1)return;
		else {
			unis[id] = -2;
			for (auto i : edges[id])
				dfs2(i, num, edges);
		}
		unis[id] = num;
		return;
	}
	void dfs(const int id, int &num, const vector<vector<Edge>>&edges) {
		if (nums[id] != -1)return;
		else {
			nums[id] = -2;
			for (auto i : edges[id]) {
				dfs(i.dst, num, edges);
			}
		}
		nums[id] = num++;
		return;
	}
	void dfs2(const int id, const int &num, const vector<vector<Edge>>&edges) {
		if (unis[id] != -1)return;
		else {
			unis[id] = -2;
			for (auto i : edges[id]) {
				dfs2(i.dst, num, edges);
			}
		}
		unis[id] = num;
		return;
	}

}dscc;


const int mod = 1000000007;
struct Mod {
public:
	int num;
	Mod() : Mod(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) {
		static_assert(mod<INT_MAX / 2, "mod is too big, please make num 'long long int' from 'int'");
	}
	Mod(int n) : Mod(static_cast<long long int>(n)) { ; }
	operator int() { return num; }
};

Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int  b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b)*a; }
Mod operator*(const Mod a, const int b) { return Mod(b)*a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod& a, const long long int &b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod mod_pow(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = mod_pow((a * a), (n / 2));
	if (n % 2) res = res * a;
	return res;
}
Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
	assert(b.num != 0);
	return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) {
	assert(b.num != 0);
	return Mod(a) * inv(b);
}
Mod operator/=(Mod &a, const Mod b) {
	assert(b.num != 0);
	return a = a * inv(b);
}

#define MAX_MOD_N 1024000

Mod fact[MAX_MOD_N], factinv[MAX_MOD_N];
void init() {
	fact[0] = Mod(1); factinv[0] = 1;
	for (int i = 0; i < MAX_MOD_N - 1; ++i) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
}
Mod comb(const int a, const int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}

int main() {
	int N, M; cin >> N >> M;
	vector<vector<int>>edges(N);
	for (int i = 0; i < M; ++i) {
		int a, b; cin >> a >> b; a--; b--;
		edges[a].push_back(b);
	}
	auto p=dscc.get(edges);
	vector<vector<int>>newedges(p.second);
	vector<vector<int>>revedges(newedges.size());
	for (int i = 0; i < newedges.size();++i) {
		vector<int>es(newedges[i]);
		for (auto e : es) {
			revedges[e].push_back(i);
		}
	}
	vector<int>nums(newedges.size());

	for (auto es : newedges) {
		for (auto e : es) {
			nums[e]++;
		}
	}
	vector<pair<Mod, Mod>>ps(newedges.size());
	queue<int>que;
	for (int i = 0; i < nums.size();++i) {
		if (!nums[i])que.push(i);
	}
	vector<pair<Mod, Mod>>memo(newedges.size());
	Mod ans = 1;
	while (!que.empty()) {
		int atop(que.front());
		que.pop();
		pair<Mod, Mod>p(1, 1);
		for (auto e : revedges[atop]) {
			p.first *= memo[e].first + memo[e].second;
			p.second *= memo[e].second;
		}
		for (auto e : newedges[atop]) {

			nums[e]--;
			if (!nums[e])que.push(e);
		}
		if (newedges[atop].empty())ans *= (p.first + p.second);
		memo[atop] = p;
	}
	cout << ans << endl;
	return 0;
}