Problem 37: Count Paths in DAG

Problem Statement: Given a directed acyclic graph (DAG) with n nodes and m edges, compute the number of distinct paths from node 1 to node n modulo 10^9+7.

Input

The first line contains two integers n and m. Each of the next m lines contains two integers u and v denoting an edge from u to v.

Output

Print the number of distinct paths from 1 to n modulo 10^9+7.

Examples


Input:
4 5
1 2
1 3
2 3
2 4
3 4

Output:
3

Solution Explanation

Method 1: Use dynamic programming and topological sorting to compute the number of paths from 1 to each node. Method 2: Use recursion with memoization on the DAG to count paths, ensuring each subproblem is solved only once.

Solution in C++


#include 
#include 
#include 
using namespace std;

const int MOD = 1000000007;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector> adj(n+1);
    vector indegree(n+1, 0);
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        indegree[v]++;
    }
    
    vector dp(n+1, 0);
    dp[1] = 1;
    
    queue q;
    for(int i = 1; i <= n; i++){
        if(indegree[i] == 0) q.push(i);
    }
    
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v : adj[u]){
            dp[v] = (dp[v] + dp[u]) % MOD;
            indegree[v]--;
            if(indegree[v] == 0) q.push(v);
        }
    }
    
    cout << dp[n] << "
";
    return 0;
}