排列
题号:NC13332
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

n个二维点(a[i],b[i]), 其中1 ≤ i ≤ n,询问有多少种排列p(答案对1e9+7取模)使得执行以下伪代码后留下的点是k,即最后saved=k(其中1 ≤ k ≤ n):
saved=p[1]
for x from 2 to n
    if a[p[x]] >= a[saved] and b[p[x]] >= b[saved]
        saved=p[x]
保证a[i]和b[i]分别为一个排列。

输入描述:

第一行一个整数n(n ≤ 100000),接下来n行每行两个整数表示一个点。

输出描述:

n行每行一个整数表示留下的点为i的排列种数。
示例1

输入

复制
3
1 2
2 3
3 1

输出

复制
0
4
2