#include <iostream>
#include <vector>

using namespace std;

#define blanco 1 ///NO VISITADO
#define gris 2 ///EN PROCESO
#define negro 3 ///PROCESADO
#define anulado -1 ///YA NO FORMA PARTE DEL GRAFO

int N, M;
vector <vector <int> > adj;
vector <int> colorNodo;

void DFS_KILLER(int n)
{
    colorNodo[n] = anulado;

    for(int i=0; i<adj[n].size(); i++)
        if(colorNodo[adj[n][i]] != anulado)
            DFS_KILLER(adj[n][i]);
}

void DFS(int n)
{
    colorNodo[n] = gris;

    for(int i=0; i<adj[n].size(); i++)
    {
        ///Si el nodo vecino está en color blanco, lo visito
        if(colorNodo[adj[n][i]] == blanco)
            DFS(adj[n][i]);
        else if(colorNodo[adj[n][i]] == gris) ///Hallé ciclo
            DFS_KILLER(adj[n][i]);
    }

    colorNodo[n] = negro;
}

vector <int> orden;
vector <bool> visitado;
void OrdenTopologico(int n)
{
    visitado[n] = true;
    for(int i=0; i<adj[n].size(); i++)
        if(visitado[adj[n][i]] == false && colorNodo[adj[n][i]] != anulado)
            OrdenTopologico(adj[n][i]);
    orden.push_back(n);
}

int main()
{
    cin >> N >> M;

    adj.resize(N+1);
    colorNodo = vector <int> (N+1, blanco);
    visitado = vector <bool> (N+1, false);

    for(int i=0; i<M; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
    }

    DFS(1);
    OrdenTopologico(1);

    ///Ahora que anulé nodos (si fuera necesario) puedo hacer la DP en grafos

    vector <int> cantCaminos(N+1, 0);
    cantCaminos[1] = 1;

    for(int j=orden.size()-1; j>=0; j--)
    {
        int n = orden[j];
        for(int i=0; i<adj[n].size(); i++)
        {
            if(colorNodo[adj[n][i]] != anulado)
            {
                cantCaminos[adj[n][i]] += cantCaminos[n];
                cantCaminos[adj[n][i]] %= 1000000000;
            }
        }
    }

    if(colorNodo[N] == anulado)
    {
        cout << "INFINITE PATHS" << endl;
    }
    else
    {
        cout << cantCaminos[N] << endl;
    }

    return 0;
}