#include <bits/stdc++.h>
using namespace std;
/*
给定一个n节点，m边的有向无环图，
请你求出从入度为0的点~出度为0的点的所有连线。得数%80112002。
n<5000 m<500000
思路：拓扑排序+图上dp。
*/
int m,n;
struct dot{
    int r,c;
    vector <int> ljb;//邻接表
}dots[5003];
int dfs(int id);
int x,y;
long long answer;
int main(){
    cin>>n>>m;
    //吃-》被吃
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        dots[x].c++,dots[y].r++;
        dots[x].ljb.push_back(y);
    }
    answer=dfs(1);
    cout<<answer%80112002;
}
int dfs(int id){
    if(dots[id].c==0) return 1;
    else {
        int ans=0;
        for(int i=0;i<dots[id].c;i++) ans+=dfs(dots[id].ljb[i]);
        return ans;
    }
}