#include<bits/stdc++.h>
using namespace std;

#define _for(i , a , b) for(int i = a ; i <= b ; i ++)
#define for_(i , a , b) for(int i = a ; i >= b ; i --)
#define ls k << 1
#define rs k << 1 | 1
#define inf 0x3f3f3f3f
const int maxn = 1e5 + 10;
const int mod = 1e9;
vector<int>v[maxn];
vector<int>v2[maxn];
vector<int>v3[maxn];
map<pair<int,int>,int>mp;
int n,m,num,cnt,tp;
int dfn[maxn],low[maxn],st[maxn],vis[maxn],rd1[maxn],rd2[maxn],id[maxn],vis1[maxn],vis2[maxn],sz[maxn],dist[maxn],tmp[maxn],tmp1[maxn],tmp2[maxn]; 
void tarjan(int u){
	st[++ tp] = u;
	vis[u] = 1;
	dfn[u] = low[u] = ++ cnt;
	for(auto itr:v[u]){
		if(!dfn[itr]) {
			tarjan(itr);
			low[u] = min(low[u],low[itr]);
		}
		else if(vis[itr]) low[u] = min(low[u],low[itr]);
	}
	if(dfn[u] == low[u]){
		++ num;
		while(st[tp] != u){
			vis[st[tp]] = 0;
			id[st[tp]] = num;
			sz[num] ++;
			-- tp;
		}
		vis[st[tp]] = 0;
		id[st[tp]] = num;
		sz[num] ++;
		-- tp;
	}
}
void bfs1(){
	queue<int>q;
	q.push(id[1]);
	while(!q.empty()){
		int u = q.front();
		tmp1[u] = 1;
		q.pop();
		for(auto itr:v2[u]) {
			vis1[itr] = 1;
			if(!tmp1[itr]) q.push(itr); 
			
		}
	}
}
void bfs2(){
	queue<int>q;
	q.push(id[2]);
	while(!q.empty()){
		int u = q.front();
		tmp2[u] = 1;
		q.pop();
		for(auto itr:v3[u]) {
			vis2[itr] = 1;
			if(!tmp2[itr]) q.push(itr);
		}
	}
}
void bfs3(){
	queue<int>q;
	q.push(1);
	dist[1] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto itr:v[u]) {
			if(mp[{u,itr}] == 0){
				q.push(itr);
				mp[{u,itr}] = 1;
				dist[itr] = (dist[itr] + dist[u]) % mod;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m;
	_for(i , 1 , m){
		int x,y;
		cin >> x >> y;
		v[x].push_back(y);
	}
	_for(i , 1 , n){
		if(!dfn[i]) tarjan(i);
	}
	_for(i , 1 , n){
		for(auto itr:v[i]){
			if(id[i] != id[itr]){
				v2[id[i]].push_back(id[itr]);
				v3[id[itr]].push_back(id[i]);
			}
		}
	}
	bfs1();
	bfs2();
	_for(i , 1 , num) {
		if(tmp1[i] && tmp2[i] && sz[i] > 1){
			cout << "inf";
			return 0;
		}
	}
	bfs3();
	//cout << endl << dist[1] << ' ' << dist[2] << ' ' << dist[3] << ' ' << dist[4];
	cout << dist[2];
	return 0;
}