"""
Define:
xn = (1248n mod 32323) - 16161
yn = (8421n mod 30103) - 15051
Pn = {(x1, y1), (x2, y2), ..., (xn, yn)}

For example, P8 = {(-14913, -6630), (-10161, 5625), (5226, 11896), (8340, -10778), (15852, -5203), (-15165, 11295), (-1427, -14495), (12407, 1060)}.

Let C(n) be the number of triangles whose vertices are in Pn which contain the origin in the interior.

Examples:
C(8) = 20
C(600) = 8950634
C(40 000) = 2666610948988

Find C(2 000 000).
"""


import itertools
import time
import math
from collections import Counter
from functools import partial, lru_cache

def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

def x(n):
    return pow(1248, n, 32323) - 16161

def y(n):
    return pow(8421, n, 30103) - 15051

def P(n):
    for k in range(1, n + 1):
        yield (x(k), y(k))

@lru_cache(maxsize=None)
def inverse_angle(a):
    return a + math.pi * (-1 if a > 0 else 1)

def between_angle(a, b, x, *, inverse=False):
    if inverse:
        a, b = inverse_angle(a), inverse_angle(b)
    if b < a:
        a, b = b, a
    if b - a <= math.pi:
        return a <= x <= b
    else:
        return b <= x or x <= a

def C(n):
    points = [math.atan2(p, q) for (p, q) in P(n)]
    counter = Counter(points)
    unique_angles = sorted(counter.keys())

    def points_between(a, b):
        angles = filter(partial(between_angle, a, b, inverse=True), unique_angles)
        return sum(counter[p] for p in angles)

    total = 0
    for a1, a2 in itertools.combinations(unique_angles, 2):
        total += counter[a1] * counter[a2] * points_between(a1, a2)
        print(total)
    return total


result = C(8) // 3
print('result is', result)