import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; class Edge{ int src,dst,need; public Edge(int src,int dst,int cost) { this.src=src; this.dst=dst; this.need=cost; } } class Main { public static void main(String[] args) { new Main().run(); } void dfs(int cur,int par,ArrayList[] g,long[] dp) { if(dp[cur]>0)return; for(Edge e:g[cur]) { if(e.dst==par)continue; dfs(e.dst,cur,g,dp); dp[cur]+=(long)dp[e.dst]*e.need; } } void run() { Scanner sc=new Scanner(System.in); int N=sc.nextInt(); int M=sc.nextInt(); ArrayList[] g=new ArrayList[N]; for(int i=0;i(); long[] dp=new long[N]; int[] indeg=new int[N]; int[] outdeg=new int[N]; dp[N-1]=1; for(int i=0;i