#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005,mod=80112002;
int n,m,x,y,head[N],tail[N],cnt1,cnt2,sl,jg;
vector<int>v[N],v2[N];
bool f[N];
void dfs(int he, int ta, int x){
	if(x==ta){
		sl++;
		return;
	} 
	for(int i=0;i<v[x].size();i++) if(f[v[x][i]]==0) f[v[x][i]]=1,dfs(he,ta,v[x][i]),f[v[x][i]]=0;
}
signed main(){
	cin>>n>>m;
	while(m--) cin>>x>>y,v2[y].push_back(x),v[x].push_back(y);
	for(int i=1;i<=n;i++) if(v[i].size()==0) tail[++cnt1]=i;
	for(int i=1;i<=n;i++) if(v2[i].size()==0) head[++cnt2]=i;
	for(int i=1;i<=cnt2;i++){
		for(int j=1;j<=cnt1;j++){
			sl=0;
			memset(f,0,sizeof(f));
			f[head[i]]=1,dfs(head[i],tail[j],head[i]),sl%=mod,jg+=sl,jg%=mod;
		}
	}
	cout<<jg%mod;
	return 0;
}