"""Fibre counts of the Hecke operator T = 1_{K t^{alpha^vee} K} applied to phi_0 = 1_{X(O)},
for two F_q-forms of SL_2/SO_2 over F = F_q((t)), q odd:

  SO_2-model : X = {A symmetric, det A = 1},  base point I        (theta(g) = g^{-T})
  split model: X = {A symmetric, det A = -1}, base point H = [[0,1],[1,0]]  (G^theta = T diagonal)

G = SL_2 acts by g.A = g A g^T, K = SL_2(O).
(T phi_0)(A) = #{ L in K t K / K : g^{-1} A g^{-T} in X(O) }.
K t K / K <-> lattices L = t^{-1} M, M subset O^2 with O^2/M = O/t^2 (q^2+q of them).
Condition: B = A^{-1} has Gram matrix on L in Sym_2(O), i.e. B(m,m') in t^2 O for m,m' in M.

Laurent polynomials over F_q are dicts {exponent: coefficient mod q}.
"""
import sys

def lp_mul(a, b, q):
    c = {}
    for i, u in a.items():
        for j, v in b.items():
            c[i + j] = (c.get(i + j, 0) + u * v) % q
    return {k: v for k, v in c.items() if v}

def lp_add(a, b, q):
    c = dict(a)
    for k, v in b.items():
        c[k] = (c.get(k, 0) + v) % q
    return {k: v for k, v in c.items() if v}

def minval(a):
    return min(a) if a else 10**9

def gram(B, v, w, q):
    # v^T B w for column vectors v, w (lists of 2 Laurent polys), B 2x2 of Laurent polys
    s = {}
    for i in range(2):
        for j in range(2):
            s = lp_add(s, lp_mul(lp_mul(v[i], B[i][j], q), w[j], q), q)
    return s

def sublattices(q):
    """Bases of M subset O^2 with O^2/M cyclic of length 2: M = ker(f), f primitive mod t^2."""
    out = []
    for a0 in range(q):
        for a1 in range(q):
            a = {k: v for k, v in ((0, a0), (1, a1)) if v}
            neg_a = {k: (-v) % q for k, v in a.items()}
            # f = (1, a): x + a y = 0 mod t^2 ; basis (t^2, 0), (-a, 1)
            out.append(([{2: 1}, {}], [neg_a, {0: 1}]))
    for b1 in range(q):
        b = {1: b1} if b1 else {}
        neg_b = {k: (-v) % q for k, v in b.items()}
        # f = (b, 1), b in tO: b x + y = 0 mod t^2 ; basis (1, -b), (0, t^2)
        out.append(([{0: 1}, neg_b], [{}, {2: 1}]))
    return out

def inverse_sym(A, q, det):
    # inverse of symmetric 2x2 with det = +-1 (constant): A^{-1} = det^{-1} [[d,-b],[-b,a]]
    di = pow(det % q, q - 2, q)
    sc = lambda p: {k: (v * di) % q for k, v in p.items()}
    neg = lambda p: {k: (-v) % q for k, v in p.items()}
    return [[sc(A[1][1]), sc(neg(A[0][1]))], [sc(neg(A[1][0])), sc(A[0][0])]]

def count(A, q, det):
    B = inverse_sym(A, q, det)
    n = 0
    for (v, w) in sublattices(q):
        ok = all(minval(gram(B, x, y, q)) >= 2 for x, y in ((v, v), (v, w), (w, w)))
        n += ok
    return n

def nonsquare(q):
    sq = {(x * x) % q for x in range(1, q)}
    return next(u for u in range(2, q) if u not in sq)

def points_SO2(m, u, q):
    # x_m = diag(u t^m, u^{-1} t^{-m}); u = 1 gives x_m, u nonsquare gives the other K-orbit
    ui = pow(u, q - 2, q)
    return [[{m: u % q}, {}], [{}, {-m: ui}]]

def points_split(m, u, q):
    # m = 0: H; m >= 1: [[u t^{-m}, 1], [1, 0]] (leading rank-one coefficient u e1 e1^T)
    if m == 0:
        return [[{}, {0: 1}], [{0: 1}, {}]]
    return [[{-m: u % q}, {0: 1}], [{0: 1}, {}]]

if __name__ == "__main__":
    print("q | model | x0 | x1 (u=1) | x1 (u nonsq) | x2 (u=1) | x2 (u nonsq) | x3 (u=1)")
    for q in (3, 5, 7, 11, 13):
        u = nonsquare(q)
        r = [count(points_SO2(0, 1, q), q, 1)]
        for m in (1, 2):
            r += [count(points_SO2(m, 1, q), q, 1), count(points_SO2(m, u, q), q, 1)]
        r += [count(points_SO2(3, 1, q), q, 1)]
        print(q, "| SO2  |", " | ".join(map(str, r)), "   q mod 4 =", q % 4)
        r = [count(points_split(0, 1, q), q, -1)]
        for m in (1, 2):
            r += [count(points_split(m, 1, q), q, -1), count(points_split(m, u, q), q, -1)]
        r += [count(points_split(3, 1, q), q, -1)]
        print(q, "| split|", " | ".join(map(str, r)))
    sys.stdout.flush()