#!/usr/bin/env python3

import math, sys

def gf2_add(x, y):
    return x^y

def gf2_mul(x, y):
    print (f"gf2_mul {math.ceil(math.log(x,2))=} {math.ceil(math.log(y,2))=}")
    y_width=math.ceil(math.log(y, 2))
    z = 0
    for i in range(y_width+1):
        if (y >> i) & 1:
            z=gf2_add(z, x)
        x = x << 1

    return z

def gf2_pow_2(x):
    print (f"gf2_pow_2 {math.ceil(math.log(x,2))=}")
    return gf2_mul(x, x)

def is_odd(n):
    return n&1==1

# almost as in https://en.wikipedia.org/wiki/Exponentiation_by_squaring
def gf2_pow(x, n):
    print (f"gf2_pow   {math.ceil(math.log(x,2))=} {n=}")

    if n==1:
         return x
    if is_odd(n):
        return gf2_mul(x, gf2_pow(gf2_pow_2(x), (n-1)//2))
    else:
        return gf2_pow(gf2_pow_2(x), n//2)

#assert gf2_pow(11, 2)==69
#print (gf2_pow(11, 8))
#print (gf2_pow(11, 10))
#print (gf2_pow(11, 123))
#r=gf2_pow(11, 50000)
#print (r)
#print (hex(r))
#print (bin(r).count("1"))
#print (gf2_pow(11, as_in_PE) % (10**9+7))
for i in range(1, 200):
    print (hex(i), hex(gf2_pow(11, i)))