题目描述

平面上有 $N$ 个互不相同的点，第 $i$ 个点的坐标为 $(x_i,y_i)$，保证任意三点不共线。

Roger 要选择一个 $0,1,\ldots,N-1$ 的排列，并按照排列中的顺序依次访问所有点，相邻两个访问点之间沿直线段移动。路径必须同时满足：

1. 路径不能严格自交，也就是说任意两条互不相邻的路径线段不能在各自内部相交；
2. Roger 不能右转。对于任意连续访问的三个点 $a,b,c$，有向三角形 $a\to b\to c$ 必须是严格逆时针方向。

令 $f(i)$ 表示以点 $i$ 作为第一个访问点的合法路径数量。

请输出所有 $f(i)$，答案对 $10^9+7$ 取模。

输入格式

第一行输入整数 $N$。

接下来 $N$ 行，第 $i+1$ 行输入两个整数 $x_i,y_i$。

输出格式

第一行输出整数 $N$。

第二行输出 $N$ 个整数 $f(0),f(1),\ldots,f(N-1)$，均对 $10^9+7$ 取模。

第一行再次输出 $N$ 是本题从 TopCoder 方法返回值转换为标准输入输出后的数据格式要求。

数据范围

• $3\le N\le100$；
• $-1000\le x_i,y_i\le1000$；
• 所有点两两不同；
• 任意三点不共线。

样例

3
-10 10
0 -10
10 10

3
1 1 1

说明

三个点构成三角形。合法路径分别为 $0\to1\to2$、$1\to2\to0$、$2\to0\to1$，因此三个起点的答案均为 $1$。