CSES - Shared codeLink to this code:
https://cses.fi/paste/8bbdd92fdb6b677b679958/
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<bool>vis;
long long MOD=1e9+7;
int n;
int dfs(int p,vector<int>*graph,vector<long long>&wt){
vis[p]=true;
if(p==n)return wt[n]=1;
if(wt[p]!=0)return wt[p];
long long ans=0;
for(int aa:graph[p]){
if(vis[aa])ans=(ans+wt[aa])%MOD;
else ans=(ans+dfs(aa,graph,wt))%MOD;
}
return wt[p]=ans%MOD;
}
int main(){
int m,a,b,top;
cin>>n>>m;
vector<int>graph[n+1];
vector<long long>ways(n+1,0);
vis.resize(n+1,0);
for(int i=0;i<m;i++){
cin>>a>>b;
graph[a].push_back(b);
}
cout<<dfs(1,graph,ways);
return 0;
}