// >>> TEMPLATES #include using namespace std; using ll = long long; using ld = long double; using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; #define int ll #define double ld #define rep(i,n) for (int i = 0; i < (int)(n); i++) #define rep1(i,n) for (int i = 1; i <= (int)(n); i++) #define repR(i,n) for (int i = (int)(n)-1; i >= 0; i--) #define rep1R(i,n) for (int i = (int)(n); i >= 1; i--) #define loop(i,a,B) for (int i = a; i B; i++) #define loopR(i,a,B) for (int i = a; i B; i--) #define all(x) (x).begin(), (x).end() #define allR(x) (x).rbegin(), (x).rend() #define pb push_back #define eb emplace_back #define mp make_pair #define fst first #define snd second template auto constexpr inf = numeric_limits::max()/2-1; auto constexpr INF32 = inf; auto constexpr INF64 = inf; auto constexpr INF = inf; #ifdef LOCAL #include "debug.hpp" #else #define dump(...) (void)(0) #define say(x) (void)(0) #define debug if (0) #endif template using pque_max = priority_queue; template using pque_min = priority_queue, greater >; template ::value>::type> ostream& operator<<(ostream& os, T const& v) { bool f = true; for (auto const& x : v) os << (f ? "" : " ") << x, f = false; return os; } template ::value>::type> istream& operator>>(istream& is, T &v) { for (auto& x : v) is >> x; return is; } template ostream& operator<<(ostream& os, pair const& p) { return os << "(" << p.first << ", " << p.second << ")"; } template istream& operator>>(istream& is, pair& p) { return is >> p.first >> p.second; } struct IOSetup { IOSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } iosetup; template struct FixPoint : private F { constexpr FixPoint(F&& f) : F(forward(f)) {} template constexpr auto operator()(T&&... x) const { return F::operator()(*this, forward(x)...); } }; struct MakeFixPoint { template constexpr auto operator|(F&& f) const { return FixPoint(forward(f)); } }; #define MFP MakeFixPoint()| #define def(name, ...) auto name = MFP [&](auto &&name, __VA_ARGS__) template struct vec_impl { using type = vector::type>; template static type make_v(size_t n, U&&... x) { return type(n, vec_impl::make_v(forward(x)...)); } }; template struct vec_impl { using type = T; static type make_v(T const& x = {}) { return x; } }; template using vec = typename vec_impl::type; template auto make_v(Args&&... args) { return vec_impl::make_v(forward(args)...); } template void quit(T const& x) { cout << x << endl; exit(0); } template constexpr bool chmin(T& x, U const& y) { if (x > y) { x = y; return true; } return false; } template constexpr bool chmax(T& x, U const& y) { if (x < y) { x = y; return true; } return false; } template constexpr auto sumof(It b, It e) { return accumulate(b,e,typename iterator_traits::value_type{}); } template int sz(T const& x) { return x.size(); } template int lbd(C const& v, T const& x) { return lower_bound(v.begin(), v.end(), x)-v.begin(); } template int ubd(C const& v, T const& x) { return upper_bound(v.begin(), v.end(), x)-v.begin(); } const int dx[] = { 1,0,-1,0 }; const int dy[] = { 0,1,0,-1 }; constexpr int popcnt(ll x) { return __builtin_popcountll(x); } template struct Random { mt19937_64 mt{random_device{}()}; //mt19937_64 mt{(unsigned)time(0)}; Int a,b; // [a,b] Random(Int a, Int b) : a(a), b(b) {} Int operator()() { return uniform_int_distribution(a,b)(mt); } }; template Int rand(Int a, Int b) { // [a,b] static mt19937_64 mt{random_device{}()}; return uniform_int_distribution(a,b)(mt); } // <<< // >>> modint template class modint { static_assert(md < (1u<<31), ""); using M = modint; using i64 = int64_t; uint32_t x; public: static constexpr uint32_t mod = md; constexpr modint(i64 x = 0) : x((x%=md) < 0 ? x+md : x) { } constexpr i64 val() const { return x; } constexpr explicit operator i64() const { return x; } constexpr bool operator==(M r) const { return x == r.x; } constexpr bool operator!=(M r) const { return x != r.x; } constexpr M operator+() const { return *this; } constexpr M operator-() const { return M()-*this; } constexpr M& operator+=(M r) { x += r.x; x = (x < md ? x : x-md); return *this; } constexpr M& operator-=(M r) { x += md-r.x; x = (x < md ? x : x-md); return *this; } constexpr M& operator*=(M r) { x = (uint64_t(x)*r.x)%md; return *this; } constexpr M& operator/=(M r) { return *this *= r.inv(); } constexpr M operator+(M r) const { return M(*this) += r; } constexpr M operator-(M r) const { return M(*this) -= r; } constexpr M operator*(M r) const { return M(*this) *= r; } constexpr M operator/(M r) const { return M(*this) /= r; } friend constexpr M operator+(i64 x, M y) { return M(x)+y; } friend constexpr M operator-(i64 x, M y) { return M(x)-y; } friend constexpr M operator*(i64 x, M y) { return M(x)*y; } friend constexpr M operator/(i64 x, M y) { return M(x)/y; } constexpr M inv() const { assert(x > 0); return pow(md-2); } constexpr M pow(i64 n) const { assert(not (x == 0 && n == 0)); if (n < 0) return inv().pow(-n); M v = *this, r = 1; for (; n > 0; n >>= 1, v *= v) if (n&1) r *= v; return r; } #ifdef LOCAL friend string to_s(M r) { return to_s(r.val(), mod); } #endif friend ostream& operator<<(ostream& os, M r) { return os << r.val(); } friend istream& operator>>(istream& is, M &r) { i64 x; is >> x; r = x; return is; } }; // <<< //constexpr int64_t MOD = 998244353; constexpr int64_t MOD = 1e9+7; using mint = modint; // >>> Point template struct Point { T x,y; constexpr Point(T x = 0, T y = 0) : x(x), y(y) {} constexpr pair to_pair() const { return {x,y}; } constexpr Point inv() const { return {x/norm(),-y/norm()}; } constexpr Point conj() const { return {x,-y}; } constexpr T norm() const { return x*x + y*y; } constexpr Point rot90(int n = 1) const { n %= 4; if (n < 0) n += 4; if (n == 1) return *this * Point(0,1); if (n == 2) return *this * (-1); if (n == 3) return *this * Point(0,-1); return *this; } constexpr Point operator+() const { return *this; } constexpr Point operator-() const { return {-x,-y}; } constexpr Point operator+(Point const& p) const { return {x+p.x, y+p.y}; } constexpr Point operator-(Point const& p) const { return {x-p.x, y-p.y}; } constexpr Point operator*(Point const& p) const { return {x*p.x-y*p.y, x*p.y+y*p.x}; } constexpr Point operator/(Point const& p) const { return *this * p.inv(); } constexpr Point& operator+=(Point const& p) { return *this = *this + p; } constexpr Point& operator-=(Point const& p) { return *this = *this - p; } constexpr Point& operator*=(Point const& p) { return *this = *this * p; } constexpr Point& operator/=(Point const& p) { return *this = *this / p; } constexpr friend Point operator*(T const& a, Point const& p) { return Point(a)*p; } constexpr friend Point operator/(T const& a, Point const& p) { return Point(a)/p; } constexpr T dot(Point const& q) const { return x*q.x + y*q.y; } constexpr T cross(Point const& q) const { return x*q.y - y*q.x; } constexpr friend Point conj(Point const& p) { return p.conj(); } constexpr friend T norm(Point const& p) { return p.x*p.x + p.y*p.y; } constexpr friend T dot(Point const& p, Point const& q) { return p.dot(q); } constexpr friend T cross(Point const& p, Point const& q) { return p.cross(q); } #ifdef LOCAL friend string to_s(Point const& p) { return to_s(p.to_pair()); } #endif friend istream& operator>>(istream& is, Point& p) { return is >> p.x >> p.y; } }; // <<< constexpr bool operator==(Point const& p, Point const& q) { return p.x == q.x && p.y == q.y; } template constexpr bool operator!=(Point const& p, Point const& q) { return !(p == q); } template constexpr T sq(T const& x) { return x*x; } using P = Point; constexpr int orth(P p) { const int x = p.x, y = p.y; if (x == 0 && y == 0) return -1; return y >= 0 ? (x < 0 ? 1 : 0) : (x < 0 ? 2 : 3); }; auto arg_cmp = [](P p, P q) { return mp(orth(p),0LL) < mp(orth(q),p.cross(q)); }; int32_t main() { int n; cin >> n; vector

p(n); cin >> p; mint ans = 0; rep (i,n) { vector

q; rep (j,n) if (p[i] != p[j]) q.eb(p[j]-p[i]); sort(all(q), arg_cmp); int m = q.size(); rep (j,m) q.eb(q[j]); P sum = 0; int l = 0, r = 0; rep (j,m) { while (l <= j || (l < sz(q) && q[j].cross(q[l]) == 0)) { sum -= q[l]; l++; } while (r < l || (r < sz(q) && q[j].cross(q[r]) > 0)) { sum += q[r]; r++; } ans += q[j].cross(sum); } } cout << ans/3 << "\n"; }