题目描述

Bogdan 正在玩一个一维游戏。水平线上有 $n$ 个平台。第 $i$ 个平台是线段 $[l_i,r_i]$，所有线段互不相同。

若 $l_i\le l_j$ 且 $r_j\le r_i$，则称平台 $j$ 在平台 $i$ 内部。

游戏开始时，Bogdan 可以选择任意一个平台作为起点。他只能从平台 $i$ 移动到平台 $j$，当且仅当：

• 平台 $j$ 在平台 $i$ 内部；
• 不存在另一个平台 $k$，使得 $j$ 在 $k$ 内部且 $k$ 在 $i$ 内部。

也就是说，只能沿“直接包含关系”向内移动。

对于每个平台，Bogdan 想知道从这个平台出发、以任意平台结束的不同路径数。两条路径不同，当且仅当存在某个平台出现在其中一条路径中而没有出现在另一条路径中。路径可以只包含起点本身。

答案可能很大，请对 $10^9+7$ 取模。

输入格式

第一行包含整数 $n$：

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i,r_i$：

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示从第 $i$ 个平台出发的不同路径数，对 $10^9+7$ 取模。

样例

5
1 5
1 4
1 3
1 2
1 1

5 4 3 2 1

4
3 3
1 4
1 5
2 5

1 2 5 2