# Finite field F_{r**3}, the digit layout of Section 2 (k=1440), and coefficient extraction.
import random, itertools
class Field:
    def __init__(s,r,d,seed=1):
        s.r=r; s.d=d; rnd=random.Random(seed)
        while True:
            s.mod=[rnd.randrange(r) for _ in range(d)]+[1]
            if s.irred(): break
    def mulmod(s,a,b):
        r,d=s.r,s.d; res=[0]*(2*d-1)
        for i,x in enumerate(a):
            if x:
                for j,y in enumerate(b): res[i+j]=(res[i+j]+x*y)%r
        for i in range(len(res)-1,d-1,-1):
            c=res[i]
            if c:
                for j in range(d+1): res[i-d+j]=(res[i-d+j]-c*s.mod[j])%r
        return res[:d]
    def pw(s,a,e):
        res=[1]+[0]*(s.d-1); b=a[:]
        while e:
            if e&1: res=s.mulmod(res,b)
            b=s.mulmod(b,b); e>>=1
        return res
    def irred(s):
        x=[0,1]+[0]*(s.d-2) if s.d>1 else [0]
        y=x
        for i in range(1,s.d+1):
            y=s.pw(y,s.r)
            if i<s.d and y==x: return False
        return y==x
    def tr(s,a):
        t=[0]*s.d; y=a[:]
        for i in range(s.d):
            t=[(u+v)%s.r for u,v in zip(t,y)]; y=s.pw(y,s.r)
        assert all(v==0 for v in t[1:]); return t[0]
    def norm(s,a):
        p=[1]+[0]*(s.d-1); y=a[:]
        for i in range(s.d): p=s.mulmod(p,y); y=s.pw(y,s.r)
        assert all(v==0 for v in p[1:]); return p[0]
    def sub(s,a,b): return [(x-y)%s.r for x,y in zip(a,b)]
D6=[[(0,1,1),(0,3,1),(1,4,-1),(2,0,1)],[(0,1,1),(1,2,1),(2,0,-1)],[(0,3,-1),(0,1,1),(1,4,1),(2,0,1)]]
T7=[[(0,4,1),(1,1,-1),(2,0,1)],[(0,5,-1),(0,6,-1),(1,3,-1),(2,1,1)],[(0,5,-1),(0,4,1),(1,2,-1),(2,0,-1)]]
d=3; W=[5,30,180]; KAP=[5,5,7]; DES=[D6,D6,T7]
Xs=4+sum(KAP[t]*W[t] for t in range(3)); k=Xs+1
def rows(F,xi):
    r=F.r
    th=[0,1]+[0]*(d-2); thp=[F.pw(th,s) for s in range(2*d-1)]
    P=[{},{},{}]
    for row in range(3):
        for combo in itertools.product(*[DES[t][row] for t in range(3)]):
            w=1; pos=0; e=0
            for t,(x,u,f) in enumerate(combo): w*=f; pos+=u*W[t]; e+=x*r**t
            val=F.pw(xi,e)
            if row<2:
                for mu in range(d):
                    p=pos+mu; P[row][p]=(P[row].get(p,0)+w*val[mu])%r
            else:
                for s_ in range(2*d-1):
                    t_=F.tr(F.mulmod(thp[s_],val)); p=pos+(2*d-2-s_); P[2][p]=(P[2].get(p,0)+w*t_)%r
    assert 0 not in P[1]
    N=F.norm(xi); P[1][0]=(xi[0]*N*N)%r
    return P
def coef(G,target,r):
    tot=0
    for s,(a,b,c) in [(1,(0,1,2)),(1,(1,2,0)),(1,(2,0,1)),(-1,(0,2,1)),(-1,(2,1,0)),(-1,(1,0,2))]:
        A,Bq,C=G[a][0],G[b][1],G[c][2]
        for p1,v1 in A.items():
            for p2,v2 in Bq.items():
                p3=target-p1-p2
                if p3 in C: tot+=s*v1*v2*C[p3]
    return tot%r