#include <bits/stdc++.h>
using namespace std;
struct lao{
    int A,B;
}l[500005];
int n,m,dn[5005],summ;
set<int> a[5005],xx,ss;
int dfs(int oo){
    if(dn[oo]!=0){
        return dn[oo];
        
    }else {
        int sum=0;
        for (set<int>::iterator it = a[oo].begin(); it != a[oo].end(); ++it){
            sum+=dfs(*it)%80112002;
        }dn[oo]=sum;
        return sum%80112002;
    }
    
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        xx.insert(i);
        ss.insert(i);
    }
    for(int i=1;i<=m;i++){
        cin>>l[i].A>>l[i].B;
        a[l[i].B].insert(l[i].A);
        if(xx.count(l[i].A)){
            xx.erase(l[i].A);
        }if(ss.count(l[i].B)){
            ss.erase(l[i].B);
        }a[l[i].B].insert(l[i].A);
    }for (set<int>::iterator it = ss.begin(); it != ss.end(); ++it) {
        dn[*it]=1;
    }for(set<int>::iterator it = xx.begin(); it != xx.end(); ++it){
        summ+=dfs(*it)%80112002;
    }cout<<summ%80112002;
}