Div = (1<<8) + (1<<4) + (1<<3) + 2 + 1
global sbox
sbox = [[0]*16 for x in range(16)]
def add(a,b):
    return a^b

def mult(a,b):
    out = 0
    while(b!=0):
        if((b&1)!=0):
            out=add(out,a)
        b=b>>1
        a=a<<1
    return out


def mod(a,b):
    abits = 0
    bbits = 0
    tmp = a
    while(tmp!=0):
        abits+=1
        tmp = tmp>>1
    tmp = b
    while(tmp!=0):
        bbits+=1
        tmp = tmp>>1
    div = b
    while(bbits<abits):
        bbits+=1
        div = div<<1


    while(div>=b):
        if(a & (1<<(bbits-1))):
            a = a^div
        div=div>>1
        bbits-=1
    return a

def inverseMod(a):
    for i in range(256):
        if(mod(mult(a,i),Div) == 1):
            return i

    return 0

def sboxByte(a):
    invA = inverseMod(a)
    b = []
    bp = []
    x = [1,1,0,0,0,1,1,0]
    for i in range(8):
        if(invA & (1<<i)):
            b.append(1)
        else:
            b.append(0)
    for i in range(8):
        bp.append(b[i] ^ b[(i+4)%8] ^ b[(i+5)%8] ^ b[(i+6)%8] ^ b[(i+7)%8] ^ x[i])
    sboxVal = 0
    for i in range(8):
        sboxVal = sboxVal<<1
        sboxVal += bp[7-i]
    sbox[a>>4][a%(1<<4)] = sboxVal

def fillSBox():
    for i in range(256):
        sboxByte(i)


fillSBox()
# print(sbox)