#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=5001; 
int ru[MAXN],chu[MAXN],ans[MAXN],n,m;
bool f[MAXN][MAXN];
struct node{
	int z[MAXN],tail=0,head=1;
	void push(int x){
		tail++;
		z[tail]=x;
		ru[x]=-1;
	}
	void pop(){
		if(head>tail) return;
		for(int i=1;i<=n;i++)
		if(f[z[head]][i]){
			ru[i]--;
			ans[i]=(ans[i]+ans[z[head]])%80112002;
		}
		head++;
	}
};
node q;
int main(){
	int i,j,k,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		f[x][y]=1;
		chu[x]++;
		ru[y]++;
	}
	for(i=1;i<=n;i++) if(ru[i]==0){ q.push(i); ans[i]=1;}
	for(k=1;k<=n;k++)
	for(i=1;i<=n;i++){
		q.pop();
		if(ru[i]==0){
			if(chu[i]==0){
				printf("%d",ans[i]);
				return 0;
			}
			q.push(i);
		}
	}
	return 0;
}