#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int A = 5005;
vector <long long> p[5005];
long long in[5005], out[5005];
long long num[5005];
const long long MOD = 80112002;
int main()
{
	int n, m;
	cin>>n>>m;
	for(int i = 1; i <= m; i++)
	{
		int a, b;
		cin>>a>>b;
		p[a].push_back(b);//b吃a 
		in[b]++;
		out[a]++;
	}
	int mark;
	for(int i = 1; i <= n; i++)
	{
		if(in[i] == 0)
		{
			mark = i;
			break;
		}
	}
	queue <int> q;
	q.push(mark);
	num[mark] = 1;
	while(!q.empty())
	{
		cout<<q.front()<<endl;
		int x = q.front();
//		ans = max(ans, q.front().cnt);
		for(int i = 0; i < out[x]; i++)
		{
			num[p[x][i]] += num[x];
			num[p[x][i]] %= MOD;
			in[p[x][i]]--;	
			if(in[p[x][i]] == 0){
				q.push(p[x][i]);
			}
		}
		q.pop();
	}
	long long ans = -1;
	for(int i = 1; i <= n; i++)
	{
		ans = max(ans, num[i]);
	}
	cout<<ans%MOD<<endl;
	return 0;
}