#include <iostream>
using namespace std;
const int N = 5005;//一共有五千个数
const int mo = 80112002;
int f[N];
long long mem[N];

bool v[N][N] = {false};
bool vs[N];
long long maxl;
int n, m;

long long memdfs(int u) {
	if (mem[u])
		return mem[u] % mo ;
	for (int i = 1; i <= n; i++) {
		if (v[u][i]) {
			mem[u] += memdfs(i) % mo ;
			mem[u] %= mo;
		}
	}
	mem[u] %= mo;
	return mem[u];
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		v[b][a] = 1;
		vs[b] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if (!vs[i])
			mem[i] = 1;
	}
	for (int i = 1; i <= n; i++) {
		memdfs(i);
	}
	for (int i = 1; i <= n; i++)
		maxl = max(maxl, memdfs(i));
//	for (int i = 1; i <= n; i++)
//		cout << mem[i] << " ";
	cout << maxl % mo;
	return 0;
}