Generalized Convex Hull Volume

On Bei Street, it is said that the residents are as diverse in temperament as the set of answers they give to a series of n – 1 questions. Suppose there are n residents, and each resident’s answers can be represented as a 0–1 coordinate in an n – 1-dimensional space. These n points form a full-dimensional simplex whose volume (after a suitable scaling) represents the "HuaXia" portion. One day, visitor B from Tsinghua Road gives n+1 sets of answers (points in the same n – 1-dimensional space). In this case the convex hull (called the generalized convex hull) may have more than n vertices. Your task is to compute the (n – 1)-dimensional volume of the convex hull formed by these n+1 points. Since the volume might not be an integer, you are asked to output the value of (volume × (n – 1)! ) modulo 10⁹+7.

More formally, let the input points lie in a d-dimensional space with d = n – 1. When the points form a convex polytope, its d-dimensional volume V is defined in the standard way. It is known that if the vertices have integer coordinates then V × d! is always an integer. In this problem you are given exactly n+1 points in ℤ^n–1 and you must output (V × (n–1)!) mod (10⁹+7).

inputFormat

The first line contains an integer n (n ≥ 3). Then follow n+1 lines. Each of these lines contains n–1 space‐separated integers representing the coordinates of one point. It is guaranteed that all coordinates are integers.

Note: When n = 3, the points lie in 2D; when n = 4, the points lie in 3D; etc.

outputFormat

Output one integer: the value of (volume × (n–1)! ) modulo 10⁹+7.

sample

3
0 0
0 1
1 0
0 0

1