代码如下：

//https://www.luogu.com.cn/problem/P4017
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static BufferedWriter writter = new BufferedWriter(new OutputStreamWriter(System.out));
	static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	static final int N = 5005;
	static int n, m;
	static int[] in = new int[N]; // 入度, 下标从1开始
	static int[] out = new int[N]; // 出度, 下标从1开始
	static long[] dp = new long[N]; // 以节点i结尾的食物链数量
	static boolean[][] graph = new boolean[N][N]; //有向图

	public static void main(String[] args) throws IOException {
		String[] readStrings = reader.readLine().split(" ");
		n = Integer.parseInt(readStrings[0]); m = Integer.parseInt(readStrings[1]);
		
		while(m-- > 0)
		{
			readStrings = reader.readLine().split(" ");
			int a = Integer.parseInt(readStrings[0]), b = Integer.parseInt(readStrings[1]);
			graph[a][b] = true;
			in[b]++; out[a]++;
		}
		
		for(int i=1; i<=n; i++)
		{
			if(out[i] == 0)
			{
				graph[i][n+1] = true; //出度为0表示终点，构造与n+1的超级汇点
				in[n+1] ++; out[i]++;
			}
		}
		
		Queue<Integer> queue = new LinkedList<>();
		for(int i=1; i<=n+1; i++)
			if(in[i] == 0)
			{
				queue.add(i);
				dp[i] = 1; 
			}
		
		while(!queue.isEmpty())
		{
			int node = queue.poll(); //以拓扑序取出节点
			for(int i=1; i<=n+1; i++)
			{
				if(graph[node][i])
				{
					dp[i] = (dp[i] + dp[node]) % 80112002; //转移方程：dp[j] = sum([dp[i] for i->j]), 即叠加入度的方案数
					if(--in[i] == 0)
						queue.add(i);
				}
			}
		}
		
		writter.write(dp[n+1]+"\n");
		
		writter.close();
		reader.close();
	}
}