#!/usr/bin/env python

# The Expat License
#
# Copyright (c) 2018, Shlomi Fish
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.


# import re
import six
from six import print_
from six.moves import range
# import math
# import primesieve
# from subprocess import Popen, PIPE
# from fractions import gcd

# This:
# 1. Only works in py 3.x
# 2. Gives the wrong result
# from math import gcd


# from functools import reduce
# import functools
# import fractions
# from collections import defaultdict
# import heapq


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


class RandGen:
    """docstring for RandGen"""
    def __init__(self):
        self.seed = 290797

    def get_Tn(self):
        """docstring for get_Tn"""
        Sn = self.seed = ((self.seed * self.seed) % 50515093)
        return Sn % 2000

    def get_norm_point(self):
        """docstring for get_norm_point"""
        S0 = self.get_Tn()
        S1 = self.get_Tn()
        return [S0-1000, S1-1000]

    def get_point(self):
        """docstring for get_norm_point"""
        S0 = self.get_Tn()
        S1 = self.get_Tn()
        return (S0, S1)


def calc_M_and_S(n):
    rg = RandGen()
    points = []
    for _ in range(n):
        points.append(rg.get_point())
    lines = {}
    lines_y = set()
    for i in range(n):
        if i % 100 == 0:
            print_('Reached', i)
        x0, y0 = points[i]
        for j in range(i+1, n):
            x1, y1 = points[j]
            dx = x1 - x0
            dy = y1 - y0
            if dx:
                g = gcd(dy, dx)
                m = (dy // g, dx // g)
                if m not in lines:
                    lines[m] = set()
                den = m[1]
                num = y0*m[1]-x0*m[0]
                g = gcd(num, den)
                lines[m].add((num // g, den // g))
            else:
                if dy:
                    lines_y.add(x0)
    M = sum(len(y) for y in six.itervalues(lines)) + len(lines_y)
    s = [0]

    def _add(lines_set):
        len_ = len(lines_set)
        s[0] += len_ * (M - len_)

    for lin in six.itervalues(lines):
        _add(lin)
    _add(lines_y)
    return M, s[0]


def main():
    rg = RandGen()
    assert rg.get_norm_point() == [527, 144]
    assert rg.get_norm_point() == [-488, 732]
    assert rg.get_norm_point() == [-454, -947]
    ret = calc_M_and_S(100)
    assert ret == (4948, 24477690)
    ret = calc_M_and_S(2500)
    print_('result =', ret[1])


main()