#include<iostream>
using namespace std;
int a[1000000];
int b[1000000];
int cnta[10000],cntb[10000];
int Mod=80112002;
long long ans;
int n,t;
void dfs(int cur,int end){
	if(cur==end) ans++;找到最强的动物就数量+1
	else{
	    for(int i=1;i<=t;i++){
	    	if(a[i]==cur) dfs(b[i],end);
      //一个被吃的动物对应一个捕食者
		}
	}
}
int main(){
	int start,end;
	cin>>n>>t;
	for(int i=1;i<=t;i++){
		cin>>a[i]>>b[i];
		cnta[a[i]]++;
		cntb[b[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(cnta[i]==0) end=i;
		if(cntb[i]==0) start=i;
      //找到生产者和最强的动物
	}
	dfs(start,end);
	//cout<<start<<" "<<end<<endl;//测试用
	cout<<ans%Mod<<endl;
	return 0;
}