#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5;
const int M=2e5+5;
const int mod=1e9;
int n,m;
vector<int> e[N],e1[N];
int vis[N],head[M],cnt,ru[N],ru1[N],dis[N];
bool op[N],flag,vis1[N];
struct node{int to,nxt;}ed[M];
void add(int u,int v){ed[++cnt].to=v;ed[cnt].nxt=head[u];head[u]=cnt;}
void dfs(int x){
	vis[x]=1;
	for(int i=0;i<e[x].size();i++){
		int v=e[x][i];
		if(!op[v])dfs(v);
		op[v]=1;
	}
}
void dfs1(int x){
	vis[x]+=2;
	for(int i=0;i<e1[x].size();i++){
		int v=e1[x][i];
		if(!op[v])dfs1(v);
		op[v]=1;
	}
}
void dfs2(int x){
	op[x]=1;
	for(int i=0;i<e[x].size();i++){
		int v=e[x][i];
		if(vis[v]==3){
			add(x,v);
			//cout<<x<<" "<<v<<endl;
			ru1[v]++;
			if(ru1[v]>ru[v]){
				flag=1;
				cout<<"inf";
			}
			if(!op[v])dfs2(v);
			op[v]=1;	
		}
	}
}
void dij(){
	dis[1]=1;queue<int> q;
	q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=ed[i].nxt){
				int v=ed[i].to;
				dis[v]=(dis[v]+dis[x])%mod;
				//cout<<x<<" "<<v<<" "<<dis[v]<<endl;
				ru1[v]--;
				if(!ru1[v])q.push(v);}
	
	}
	
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		ru[v]++;
		e[u].push_back(v);
		e1[v].push_back(u);
	}
	dfs(1);
	for(int i=1;i<=n;i++)op[i]=0;
	dfs1(2);
	if(vis[1]!=3){cout<<0;return 0;}
	for(int i=1;i<=n;i++)op[i]=0;
	dfs2(1);
	if(flag==1)return 0;
	dij();
	//for(int i=1;i<=n;i++)cout<<ru1[i]<<" ";
	cout<<dis[2];
	return 0;
}