#include<stdio.h>
#include<stdlib.h>

 int ind[5005];
 int d[5005];
 int edge[5005][5005];
 int queue[5005];
 int front,rear=-1;
 int get[5005][5005];
 int top[5005];
 int out[5005];
 int top2;
 int res;
///
int main() {
int n,m,i,j,l,r,t,tar;
	scanf("%d%d",&n,&m);

	for(i=1; i<=m; i++) {
		scanf("%d%d",&l,&r);
		edge[l][r]++;
		if(edge[l][r]>1) {
			edge[l][r]--;
			continue;
		}
		get[l][top[l]++]=r;
		ind[r]++;
	}
	for(i=1; i<=n; i++) {
		if(ind[i]==0) {
			queue[++rear]=i;
			d[i]=1;
		}
		if(top[i]==0){
			out[top2++]=i;
		}
	}
	while(front<=rear) {
		t=queue[front];
		for(i=0; i<top[t]; i++) {
			ind[get[t][i]]--;
			d[get[t][i]]%=80112002;
			d[t]%=80112002;
			d[get[t][i]]=(d[get[t][i]]+d[t])%80112002;
			if(ind[get[t][i]]==0) {
				queue[++rear]=get[t][i];
			}
		}
		front++;
	}
	for(i=0;i<top2;i++){
		res+=d[out[i]];
		res%=80112002;
	}
	
	printf("%d",res);
	return 0;
}