/*
 * Complete the 'countPaths' function below.
 *
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. 2D_INTEGER_ARRAY edges
 */

void countPaths(int n, vector<vector<int>> edges) {
    const int MOD = 1000000000;
    enum class Color {
        White,
        Gray, // visiting
        Black, // visited
    };

    vector<vector<int>> g(n+1);
    for (const auto& e : edges) {
        g[e.front()].push_back(e.back());
    }
    
    vector<Color> color(n+1, Color::White);
    
    using state_t = std::pair<int, bool>;
    vector<state_t> paths(n+1);
    
    std::function<state_t(int)> dfs;
    dfs = [&](int v) -> state_t {
        if (v == n) {
            return {1, true};
        }
        if (Color::Gray == color[v]) {
            return {-1, false};
        }
        if (Color::Black == color[v]) {
            return paths[v];
        }
        bool cycle = false, found = false;
        int ways = 0;
        color[v] = Color::Gray;
        for (int u : g[v]) {
            const auto state = dfs(u);
            found |= state.second;
            if (state.first < 0) {
                cycle = true;
            } else {
                ways = (ways + state.first) % MOD;
            }
        }
        ways = cycle && found ? -1 : ways;
        color[v] = Color::Black;
        paths[v] = {ways, found};
        return paths[v];
    };

    const auto res = dfs(1);
    if (res.first < 0) {
        std::cout << "INFINITE PATHS" << std::endl;
    } else {
        std::cout << res.first << std::endl;
    }
}

import java.util.*;

public class Solution{
    private static Set<Integer> path_set = new HashSet<>();
    private static Set<Integer> circle_set = new HashSet<>();
    private static long[] memo;
    private static boolean[] visited;
    private static final int mod = 1000_000_000;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0;i<m;i++){
            graph.get(scanner.nextInt()-1).add(scanner.nextInt()-1);
        }
        memo = new long[n];
        visited = new boolean[n];
        visited[0] = true;
        dfs(0, new ArrayList<Integer>(), graph, n);
        if(isInfintePath()) System.out.println("INFINITE PATHS");
        else System.out.println(memo[0]);
    }
    private static void addToPathSet(List<Integer> cur_path){
        for(int vertex: cur_path) path_set.add(vertex);
    }
    private static void addToCircleSet(List<Integer> cur_path){
        int index = cur_path.size()-1;
        int repeatedVertex = cur_path.get(index--);
        circle_set.add(repeatedVertex);
        while(index>=0 && cur_path.get(index)!=repeatedVertex){
            circle_set.add(cur_path.get(index--));
        }
    }
    private static boolean isInfintePath(){
        for(int circle_vertex: circle_set){
            if(path_set.contains(circle_vertex)) return true;
        }
        return false;
    }
    private static void updatePath(long ways, List<Integer> cur_path){
        for(int vertes: cur_path){
            memo[vertes] = (memo[vertes] + ways)%mod;
        } 
    }
    private static void dfs(int cur_vertex, List<Integer> cur_path,List<List<Integer>> graph, int n){
        cur_path.add(cur_vertex);
        for(int next_vertex: graph.get(cur_vertex)){
            if(next_vertex==n-1){
                updatePath(1L, cur_path);
                addToPathSet(cur_path);
                continue;
            }
            if(memo[next_vertex]!=0){
                if(memo[next_vertex]!=-1){
                    updatePath(memo[next_vertex], cur_path);
                }
            }
            else{
                if(visited[next_vertex]){
                    cur_path.add(next_vertex);
                    addToCircleSet(cur_path);
                    cur_path.remove(cur_path.size()-1);
                }
                else{
                    visited[next_vertex] = true;
                    dfs(next_vertex, cur_path, graph, n);
                }
            }
        }
        if(memo[cur_vertex]==0) memo[cur_vertex]=-1;
        cur_path.remove(cur_path.size()-1);
    }
}