/*
 * 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;
    }
}