#include<bits/stdc++.h>

using namespace std;

const int maxn = 5005;

struct E{
	int to , next = -1;
}e[maxn];

int tot = 0 , H[maxn] , ct[maxn];
int n , m;

void add_(int v , int to){
	e[tot].next = H[v];
	H[v] = tot;
	e[tot].to = to;
	tot++;
}

int main(){
	memset(H , -1 , sizeof(H));
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++){
		int t , u;
		cin >> u >> t;
		add_(u , t);
		ct[t]++; //记录入度
	}
	int jl = 0;
	for(int i = 1 ; i <= n ; i++){
		if(ct[i] == 0) {  //遍历找到入度为0的点（食物链最低端）
			jl = i;
			break;
		}
	}
	queue <E> q;
	int ans = 1;
	for(int i = H[jl] ; i != -1 ; i = e[i].next){
		q.push(e[i]);
	}
	while(q.size()){                  //bfs
		int size = q.size();
		for(int j = 0 ; j < size ; j++){
			E tmp = q.front();
			q.pop();
			for(int i = H[tmp.to] ; i != -1 ; i = e[i].next){
				q.push(e[i]);
			}
		}
	ans = ((ans % 80112002) + (1 % 80112002)) % 80112002;   //记录bfs的层数
	}
	cout << ans << endl;
	return 0;
}