P5979 [PA 2014] Teams

In a PE class, $n$ children stand in a line (numbered from $1$ to $n$). The teacher wants to divide them into several groups. Each group must contain a consecutive segment of children, and each child belongs to exactly one group. The $i$-th child wants the size of their group to be no more than $d_i$ and no less than $c_i$, otherwise they will be unhappy. Assuming all children are satisfied, find the maximum possible number of groups, and how many grouping plans can achieve this maximum.

The first line contains an integer $n$, which is the number of children. The next $n$ lines each contain two integers $c_i, d_i$, representing the minimum and maximum allowed group size for the group containing child $i$.

If no such plan exists, output only one line: `NIE`. Otherwise, output one line containing two integers: the maximum number of groups and the number of plans. (The number of plans should be taken modulo $10^9+7$.)

For $100\%$ of the testdata, $1 \le n \le 10^6$, and $1 \le c_i \le d_i \le n$. Translated by ChatGPT 5