"""Exact symbolic count, as a polynomial in p, of the glue subspaces W in F_p^I (Grant pt212u).
W must (i) contain no coordinate vector e_i, (ii) have every coordinate functional nonzero on it, (iii) be invariant
under the induced maps (matrices with entries 0, +-1, the same for every p).  W = W_A (+) W_B (the corners e, f act as
the coordinate projections).  Each W is written in reduced row echelon form (pivot set + free entries); the conditions
become polynomial equations / non-vanishing conditions in the free entries with integer coefficients, and the
solutions are counted by an exact zero/non-zero case split.  Every integer constant that the split needs to be
nonzero is checked to have no odd prime factor (list BAD stays empty), so the count holds for every odd prime p."""
import sympy as sp, itertools, collections
P=sp.Symbol('p')
BAD=[]
def unit_const(c):
    c=abs(int(c))
    if c==0: return False
    while c%2==0: c//=2
    return c==1
def is_unit_monomial(x,nz):
    if x.is_number: return unit_const(x)
    c,m=sp.factor(x).as_coeff_Mul()
    f=sp.factor(x)
    if not unit_const(c): return False
    base=f/c
    facs=sp.Mul.make_args(base)
    for g in facs:
        b=g.base if g.is_Pow else g
        if not (b.is_Symbol and b in nz): return False
    return True
def solve(eqs,ne,dis,free,nz):
    E2=[]
    for e in eqs:
        e=sp.expand(e)
        if e==0: continue
        if e.is_number:
            return sp.Integer(0)
        if is_unit_monomial(e,nz): return sp.Integer(0)
        E2.append(e)
    N2=[]
    for e in ne:
        e=sp.expand(e)
        if e==0: return sp.Integer(0)
        if is_unit_monomial(e,nz): continue
        if e.is_number: BAD.append(e); continue
        c,fs=sp.factor_list(e)
        if not unit_const(c): BAD.append(c)
        for g,_ in fs:
            if g.is_Symbol: nz=nz|{g}
            else: N2.append(g)
    N2=[g for g in N2 if not is_unit_monomial(g,nz)]
    D2=[]
    for L in dis:
        L=[sp.expand(x) for x in L]; L=[x for x in L if x!=0]
        if not L: return sp.Integer(0)
        if any(is_unit_monomial(x,nz) for x in L): continue
        if len(L)==1: N2.append(L[0]); continue
        D2.append(L)
    if any(len(L)==1 for L in D2): pass
    # re-run if new single nonzero conditions were added
    for e in E2:
        for y in sorted(e.free_symbols,key=str):
            if y not in free: continue
            pe=sp.Poly(e,y)
            if pe.degree()!=1: continue
            u=sp.expand(pe.coeff_monomial(y)); r=sp.expand(e-u*y)
            if u!=0 and is_unit_monomial(u,nz) and y not in r.free_symbols:
                sub={y:-r/u}
                def num(x):
                    n,d=sp.fraction(sp.together(sp.expand(x).subs(sub))); return sp.expand(n)
                eqs2=[num(x) for x in E2 if x is not e]
                ne2=[num(x) for x in N2]+([num(y)] if y in nz else [])
                dis2=[[num(x) for x in L] for L in D2]
                return solve(eqs2,ne2,dis2,free-{y},nz-{y})
    def pick():
        for e in E2+N2+[x for L in D2 for x in L]:
            for s in sorted(e.free_symbols,key=str):
                if s in free and s not in nz: return s
        return None
    s=pick()
    if s is None:
        if E2 or N2 or D2: raise RuntimeError(('stuck',E2,N2,D2,nz))
        k=len(free-nz); j=len(nz&free)
        return P**k*(P-1)**j
    z=solve([e.subs(s,0) for e in E2],[e.subs(s,0) for e in N2],[[x.subs(s,0) for x in L] for L in D2],free-{s},nz)
    n=solve(E2,N2,D2,free,nz|{s})
    return sp.expand(z+n)
def rref_cells(n,k,tag):
    for piv in itertools.combinations(range(n),k):
        rows=[];syms=[]
        for r,c in enumerate(piv):
            row=[sp.Integer(0)]*n; row[c]=sp.Integer(1)
            for j in range(c+1,n):
                if j in piv: continue
                t=sp.Symbol(f'{tag}{r}_{j}'); row[j]=t; syms.append(t)
            rows.append(row)
        yield piv,rows,syms
def count_glue(IA,IB,ops):
    I=list(IA)+list(IB); pos={c:t for t,c in enumerate(I)}; n=len(I); nA=len(IA)
    Ms=[]
    for o in ops:
        Mt=[[0]*n for _ in range(n)]
        for i,(j,sg) in o.items():
            if i in pos and j in pos: Mt[pos[i]][pos[j]]=sg
        if any(any(r) for r in Mt): Ms.append(Mt)
    tot=collections.Counter()
    for kA in range(nA+1):
        for kB in range(n-nA+1):
            for pa,ra,sa in rref_cells(nA,kA,'a'):
                for pb,rb,sb in rref_cells(n-nA,kB,'b'):
                    rows=[r+[sp.Integer(0)]*(n-nA) for r in ra]+[[sp.Integer(0)]*nA+r for r in rb]
                    piv=list(pa)+[nA+c for c in pb]
                    dis=[[x for c,x in enumerate(r) if c not in piv] for r in rows]
                    dis+=[[r[c] for r in rows] for c in range(n) if c not in piv]
                    if any(all(x==0 for x in L) for L in dis): continue
                    eqs=[]
                    for Mt in Ms:
                        for r in rows:
                            img=[sum(r[a]*Mt[a][b] for a in range(n) if Mt[a][b]) for b in range(n)]
                            res=[sp.expand(img[b]-sum(img[q]*rows[t][b] for t,q in enumerate(piv))) for b in range(n)]
                            eqs+=[x for x in res if x!=0]
                    val=solve(eqs,[],dis,set(sa)|set(sb),set())
                    if val!=0: tot[len(rows)]+=val
    return {k:sp.expand(v) for k,v in tot.items()}
