#include<iostream>
using namespace std;
int n,m,deg[5005],cnt[5005],js=0,ans=0;
bool a[5005][5005];
void ty(int x)
{
	bool flag=0,fla=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i][x]==1)
		{
			cnt[x]+=cnt[i];
			fla=1;
		}
		if(a[x][i]==1)
		{
			deg[i]--;
			flag=1;
		}
	}
	if(fla==0) cnt[x]=1;
	if(flag==0) ans+=cnt[x];
	ans=ans%80112002;
	return;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x][y]=1;
		deg[y]++;
	}
	while(js<n)
	{
		for(int i=1;i<=n;i++)
		{
			if(deg[i]==0)
			{
				js++;
				ty(i);
				deg[i]=-1;
			}
		}
	}
	cout<<ans;
	return 0;
}