1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<cstring>
 5 #define LL long long
 6 using namespace std;
 7 const LL N=1e4;
 8 const LL MOD=1e9;
 9 LL n,m,f[N+10];
10 bool flag;
11 vector<LL>g[N+10];
12 LL dfs(LL u)
13 {
14     if(f[u]>=0) return f[u];
15     f[u]=0;
16     for(LL i=0;i<g[u].size();i++)
17     {
18         LL v=g[u][i];
19         f[u]+=dfs(v);
20         if(f[u]>=MOD) f[u]%=MOD,flag=1;
21     }
22     return f[u];
23 }
24 int main()
25 {
26     scanf("%lld%lld",&n,&m);
27     for(LL i=1,u,v;i<=m;i++) scanf("%lld%lld",&u,&v),g[v].push_back(u);
28     memset(f,-1,sizeof(f));
29     f[1]=1;
30     dfs(2);
31     if(!flag){printf("%lld",f[2]);return 0;}
32     LL x=1e8;
33     while(x)
34     {
35         printf("%lld",f[2]/x);
36         f[2]%=x;
37         x/=10;
38     }
39     return 0;
40 }