This was a very interesting problem. Took me a while to do this. The solution is pretty simple though. Here are the tricks:

1. There will be infinite number of paths only if one valid path from 1 to n touches a cycle. So do exactly that. Maintain two sets for path and cycle. As and when you detect a new path, add all those nodes to the set and when you detect a cycle add all cycle nodes to the set. After everything is over, see if these two sets intersect at all. if they do then there are infinite paths.
2. Since the answer should be mod 10^9, we can infer that there will be large answers. So we use a simple DP trick here. Maintain an array which holds an int for each node. that int represents the number of paths from that node till nth node. When we find a new path, increment this value for all nodes on that path. and MOST importantly, whenever we touch a new node during dfs for which the array value is greater than 0, we know we have explored all possible paths from that node to nth node so we grab its value and increment all nodes on current path with that value and not recurse in that direction.
3. when we exit the dfs recursion for any node and we see that we did not find any paths to nth node from this node, we set the DP array value for this node to -1. so next time we touch this node, we can see the -1 and not recurse in this direction cuz we wont find anything.

These tricks are enough to get you through! Here is a very efficient implementation of the above in C++. Feel free to suggest anything! Happy coding!

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>

#define pb push_back
#define range(i, x, y) for(int i = x; i < y; i++)

using namespace std;

typedef vector<int> v;
typedef vector<v> vv;

vv graph;
v visited;
int n, m;
set<int> cycle_nodes;
set<int> path_nodes;
v cur_path;
v memo;
int MOD = 1000000000;

void read_graph();

void dfs(int node);

void update_path_nodes(int inc);

void update_cycle_nodes(int cycle_start);

bool found_infinite_solution();

int main() {
    read_graph();
    dfs(0);
    if (found_infinite_solution())
        cout << "INFINITE PATHS";
    else
        cout << memo[0];
    return 0;
}

bool found_infinite_solution() {
    for(int cycle_node : cycle_nodes) {
        if (path_nodes.find(cycle_node) != path_nodes.end())
            return true;
    }

    return false;
}

void dfs(int node) {
    visited[node] = true;
    cur_path.pb(node);

    if (node == n - 1)
        update_path_nodes(1);
    else {
        for (int next : graph[node]) {
            if (visited[next])
                update_cycle_nodes(next);
            else {
                if (memo[next] > 0)
                    update_path_nodes(memo[next]);
                if (memo[next] == 0)
                    dfs(next);
            }
        }
    }

    if (memo[node] == 0)
        memo[node] = -1;

    visited[node] = false;
    cur_path.pop_back();
}

void update_cycle_nodes(int cycle_start) {
    auto rit = cur_path.rbegin();
    for(; *rit != cycle_start; rit++) {
        cycle_nodes.insert(*rit);
    }
    cycle_nodes.insert(cycle_start);
}

void update_path_nodes(int inc) {
    for (int cur : cur_path) {
        path_nodes.insert(cur);
        memo[cur] += inc;
        memo[cur] %= MOD;
    }
}

void read_graph() {
    cin >> n >> m;
    range(i, 0, n) {
        graph.pb(v());
        visited.pb(false);
        memo.pb(0);
    }

    int x, y;
    range(i, 0, m) {
        cin >> x >> y;
        graph[--x].pb(--y);
    }
}

Must the path terminate as soon as we've reached the warfare city? Or can we travel through the warfare city, if it is on a loop?

For example

4 4
1 2
2 3
3 4
4 2

Where there is a direct path 1->2->3->4, but also 1->2->3->4->2->3->4...

i'm having this doubt ...

once the person enters the loop then he cannot escape out since it is a directed graph and hence "Infinite paths",

but if he is able to choose a path other than the "looped path" and reaches the destination, then we are supposed to count that path as valid....

so according to the question is this what i have to do?

please help!!

for eg : consider the path

    1->2
    1->3
    2->3
    4->2
    3->4
    4->5

in this 2->3->4->2 forms a loop path

but 1->3->4->5 can lead to the destination

I am not getting a correct answer for test case 3 and test case 9 they have a value in their o/p though their is a cycle in the graph.

For test case 20 33 10 15 15 17 8 18 12 5 11 4 16 14 10 17 12 5 4 12 10 15 1 7 2 20 1 10 2 20 12 5 15 9 8 11 16 6 4 12 13 2 15 17 3 15 14 8 11 19 1 16 9 20 9 13 16 18 14 6 1 3 12 5 4 16 6 8 For this test case Output is 9 but here exists a path with cycle i.e 1->16->6->8->11->4->16... here 16 is visited again Correct me if I am wrong!!