Counting Maximum Food Chains in a Food Web

Given a food web with N organisms and M directed edges representing predatory relationships, your task is to compute the number of longest food chains modulo \(80112002\).

An edge u → v indicates that organism u preys on organism v. A valid food chain is defined as a sequence of distinct organisms \(a_0, a_1, \ldots, a_k\) satisfying the following conditions:

• The leftmost organism \(a_0\) is a producer (it does not prey on any other organism in the food web, i.e. it has no outgoing edges in the original graph).
• The rightmost organism \(a_k\) is a consumer (it is not preyed upon by any other organism in the food web, i.e. it has no incoming edges in the original graph).
• For each \(1 \le i \le k\), organism \(a_i\) preys on \(a_{i-1}\) (i.e. there is a directed edge from \(a_i\) to \(a_{i-1}\)).

Your goal is to count how many valid food chains achieve the maximum possible length (in terms of number of organisms), and output this number modulo \(80112002\). You have only 1 second to process the input.

inputFormat

The first line contains two integers N and M, representing the number of organisms and the number of predatory relationships respectively.

Each of the next M lines contains two integers u and v, indicating that organism u preys on organism v.

It is guaranteed that the food web has no cycles.

outputFormat

Output a single integer: the number of longest valid food chains modulo \(80112002\).

sample

4 3
2 1
3 1
4 3

1