#include<bits/stdc++.h>

#define int long long
#define db double
#define st string
#define N 5001
#define M 500001
#define mod 80112002

using namespace std;
int n,m,a,b,mp[N][N],small[N],big[N],r[M],ans=0;
int dfs(int x){
	int sum=0;
	if(!big[x])return 1;
	if(r[x])return r[x];
	for(int i=1;i<=n;i++){
		if(mp[i][x]){
			sum=(sum+dfs(i))%mod;
		}
	}
	return r[x]=sum;
}
signed main(){
    //freopen("P4017_9.in", "r", stdin);
    //freopen(".out", "w", stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	cin>>a>>b;
    	mp[a][b]=1;
    	small[a]++;
    	big[b]++;
	}
	for(int i=1;i<=n;i++){
		if(!small[i])ans=(ans+dfs(i))%mod;
	}
	cout<<ans;
    return 0;
}
```![](https://cdn.luogu.com.cn/upload/image_hosting/o4lr17oy.png?x-oss-process=image/resize,m_lfit,h_170,w_225)