#!/usr/bin/env python3

import math, sys, copy

# xor two arrays
def gf2_add(x, y):
    #print (f"gf2_add {x=} {y=}")
    #print (y)
    assert type(x)==list
    assert type(y)==list
    rt=[]
    for i in x:
        if i not in y:
            rt.append(i)
    for i in y:
        if i not in x:
            rt.append(i)
    #print (f"gf2_add {rt=}")
    return rt

def add1(x):
    return x+1

def gf2_mul(x, y):
    assert type(x)==list
    assert type(y)==list
    x_hi=max(x)
    y_hi=max(y)
    #print (f"gf2_mul {x=} {y=}")
    print (f"gf2_mul {x_hi=} {y_hi=}")
    sys.stdout.flush()
    """
    ...xxxx
    ..xxxx.
    .xxxx..
    xxxx...
    """

    """
    # also works, but slow
    rt=[]
    x2=x
    for i in range(y_hi+1):
        if i in y:
            rt=gf2_add(rt, x2)
        x2=list(map(add1, x2))
    #print ("gf2_mul rt:", rt)
    return rt
    """

    rt=[]
    for xi in x:
        rt=gf2_add(rt, list(map(lambda z: z+xi, y)))
    return rt

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)

as_in_PE=8**12 * 12**8
# or 29548117155177824256
# or 68719476736 * 429981696

# bits in polynomial - 3, 1, 0
tmp=gf2_pow([3,1,0], 2)
assert 69==sum(list(map(lambda x: 2**x, tmp)))

tmp=sorted(gf2_pow([3,1,0], as_in_PE))
#print (tmp)
#print (len(tmp))
#print (sum(list(map(lambda x: 2**x, tmp)))) # print a (huge) number

# this is https://en.wikipedia.org/wiki/Freshman%27s_dream that is actually true here
# because modulo is prime
# https://proofwiki.org/wiki/Freshman%27s_Dream
# https://proofwiki.org/wiki/Power_of_Sum_Modulo_Prime
PRIME_MODULO_as_in_PE=10**9+7
print (sum([pow(2, x, PRIME_MODULO_as_in_PE) for x in tmp]) % PRIME_MODULO_as_in_PE)