P4017 Maximal Food Chain Count

Do you know about food chains? During Delia's biology exam, she got all the questions about counting food chains wrong because she kept double-counting or missing some. So she came to ask you for help, but you don’t know either. Write a program to help her.

Given a food web, you are to compute the number of maximal food chains in this food web. (Here, a "maximal food chain" refers to a food chain in the biological sense: the leftmost end is a producer that does not prey on any other species, and the rightmost end is a consumer that is not preyed upon by any other species.) Delia is in a hurry, so you have only $1$ second. Since the result may be large, you only need to output the total modulo $80112002$.

The first line contains two positive integers $n$, $m$, denoting the number of species $n$ and the number of predator-prey relations $m$. Then $m$ lines follow. Each line contains two positive integers, denoting a species $A$ that is eaten and a species $B$ that eats $A$.

Output a single integer on one line: the number of maximal food chains modulo $80112002$.

Each test point satisfies the following constraints: | Test point ID | $n$ | $m$ | |:-:|:-:|:-:| | $1,2$ | $\le 40$ | $\le 400$ | | $3,4$ | $\le 100$ | $\le 2\times 10^3$ | | $5,6$ | $\le 10^3$ | $\le 6\times 10^4$ | | $7,8$ | $\le 2\times 10^3$ | $\le 2\times 10^5$ | | $9,10$ | $\le 5\times 10^3$ | $\le 5\times 10^5$ | For $100\%$ of the testdata, $1 \le n \le 5\times 10^3, 1 \le m \le 5\times 10^5$. Additional note: The data contains no cycles, in line with biological requirements. (Thanks to @AKEE.) Translated by ChatGPT 5