3543. 夜游 ECNU

单测试点时限: 2.0 秒

内存限制: 256 MB

ultmaster 男神带着小迷妹们夜游 ECNU 闵大荒校区,他从学校西南门即原点 出发前往 ECNU 各个景点。

由于 ultmaster 是个大懒虫,因此他们只会沿着最短路走(即只能往北或者东走,不一定沿着格线)。由于 ECNU 实在是太大太无聊,他们希望在路线是最短路的前提下,在路上还能途径一些景点。两条路线是不同的,当且仅当他们途径的景点不同。无聊的 ultmaster 想知道他们能走出多少条不同的路线。由于答案可能很大,故对 取模。

输入

第一行一个整数 表示不同的景点个数。

之后 行,每行两个整数 表示景点的坐标。

保证景点位置各不相同,且不为原点。

输出

一行 个整数 以空格隔开,表示以每个景点为终点不同的游览路线数。

样例

Input
2
1 1
2 2
Output
1 2
Input
3
1 2
2 1
3 3
Output
1 1 3

提示

样例二:到达 3 号景点可以直接从起点出发到达、经过 1 号景点或者经过 2 号景点三种方案。注意不能经过 1 再经过 2 再到 3,因为这不是最短路径。

36 人解决,49 已尝试。

44 份提交通过,共有 208 份提交。

7.8 EMB 奖励。

创建: 8 月,2 周前.

修改: 7 月,3 周前.

最后提交: 1 月,1 周前.

来源: EOJ Monthly 2018.4