#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+10;
int n,m;
struct lin{
	int A,B;
}a[N];
vector<int>maps[N];
bool to[N];//有没有指向i的 
bool from[N];//有没有被i指向的
int mem[N];//从i到终点的数量 
int dfs(int start,int end){
	if(mem[start]) return mem[start];
	if(start==end) return mem[start]=1;
	for(int i=0;i<maps[start].size();++i){
		int y=maps[start][i];
		dfs(y,end);
		mem[start]=(mem[start]%80112002+mem[y]%80112002)%80112002;
	}
	return mem[start]%80112002;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>a[i].A>>a[i].B;
		from[a[i].A]=true;
		to[a[i].B]=true;
		maps[a[i].A].push_back(a[i].B);
	}
	int start,end;
	for(int i=1;i<=n;++i){
		if(!to[i]) start=i;
		if(!from[i]) end=i;
	}//找起点终点 
	cout<<dfs(start,end)%80112002;
	return 0;
}

只有第二个点对呃呃呃