Description

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$.

Input Format

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 Format

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

5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4

5

Hint

Each test point satisfies the following constraints:

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