問題文

2 次元平面上に N 個のバス停があり、i 番目のバス停の座標は (x_i, y_i) です。ただし、x_i, y_i はいずれも整数です。

すぬけ君は、N 個のうち 3 個以上のバス停を選び、凸包 (選ばれた点の集合を全て包含する中で面積が最小の凸多角形) の面積を計算する、ということを全ての選び方について行ったときの総和を知りたいです。 あなたはすぬけ君の代わりにこの値を求めることになりました。

ただし、この面積の総和を a/2 とすると a は必ず整数になることが証明できるので、a を 10^9+7 で割った余りを答えてください。

制約

• 3 ≤ N ≤ 2000
• |x_i|, |y_i| ≤ 10000
• (x_i, y_i) ≠ (x_j, y_j) (1 ≤ i < j ≤ N)
• 与えられる点のうちいずれの 3 点も同一直線上にない
• 入力で与えられる値は全て整数

入力例 1

4
0 0
1 0
-1 1
-1 -1

出力例 1

12

• 1 番目の点、2 番目の点、3 番目の点を選んだ時、凸包の面積は 1/2 です。
• 1 番目の点、2 番目の点、4 番目の点を選んだ時、凸包の面積は 1/2 です。
• 1 番目の点、3 番目の点、4 番目の点を選んだ時、凸包の面積は 1 です。
• 2 番目の点、3 番目の点、4 番目の点を選んだ時、凸包の面積は 2 です。
• 1 番目の点、2 番目の点、3 番目の点、4 番目の点を選んだ時、凸包の面積は 2 です。

よって、面積の総和は 1/2+1/2+1+2+2=6 です。面積の総和の 2 倍を 10^9+7 で割った余りである 12 を出力します。

入力例 2

10
-3 1
2 3
-2 0
-3 2
-5 -5
1 -5
2 4
5 4
5 -3
-2 5

出力例 2

75282