Solution

Answer: 14063639

Let

$$a \otimes b$$

denote the XOR-product.

The crucial observation is that XOR-product is exactly multiplication of binary polynomials over the field $\mathbb F_2$.

1. Mathematical analysis

Write an integer in binary:

$$n=\sum n_i2^i,\qquad n_i\in{0,1}$$

and associate to it the polynomial

$$f_n(x)=\sum n_i x^i$$

over $\mathbb F_2$.

Then ordinary long multiplication in base $2$, with XOR replacing addition, is precisely polynomial multiplication modulo $2$. Therefore:

$$f_{a\otimes b}(x)=f_a(x)f_b(x).$$

Step 1: Polynomial corresponding to $11$

$$11_{10}=1011_2$$

$$f(x)=x^3+x+1.$$

Thus

$$P(n)=11^{\otimes n}$$

corresponds to

$$f(x)^n.$$

2. Exploiting the exponent structure

We need

$$P(8^{12}\cdot 12^8).$$

Factor the exponent:

$$8^{12}\cdot 12^8 =(2^3)^{12}(2^2\cdot 3)^8 =2^{36} \cdot 2^{16}\cdot 3^8 =2^{52}3^8.$$

Hence

$$P(8^{12}12^8) =f(x)^{2^{52}3^8}.$$

Step 2: Frobenius map in $\mathbb F_2$

In characteristic $2$,

$$(a+b)^2=a^2+b^2.$$

Therefore for any polynomial $g(x)$,

$$g(x)^{2^k}=g(x^{2^k}).$$

So:

$$f(x)^{2^{52}3^8} = \left(f(x)^{3^8}\right)^{2^{52}} = f(x^{2^{52}})^{3^8}.$$

Let

$$f(x)^{3^8}=\sum_i c_i x^i, \qquad c_i\in{0,1}.$$

Then

$$f(x)^{2^{52}3^8} = \sum_i c_i x^{i2^{52}}.$$

Finally, converting back to an integer means evaluating at $x=2$:

$$P(8^{12}12^8) = \sum_i c_i 2^{i2^{52}}.$$

Modulo $M=10^9+7$, define

$$r=2^{2^{52}} \pmod M.$$

Then

$$P(8^{12}12^8)\equiv \sum_i c_i r^i \pmod M.$$

So the task reduces to:

Compute $f(x)^{6561}$ over $\mathbb F_2$,
Evaluate it at $r$.

3. Python implementation

MOD = 10**9 + 7

# Polynomial for 11 = 1011_2 = x^3 + x + 1
# Bit i = coefficient of x^i
f = (1 << 0) | (1 << 1) | (1 << 3)

# XOR-polynomial multiplication over GF(2)
def mul(a, b):
    res = 0
    shift = 0

    while b:
        if b & 1:
            res ^= (a << shift)
        shift += 1
        b >>= 1

    return res

# Fast exponentiation of polynomials over GF(2)
def poly_pow(a, n):
    res = 1

    while n:
        if n & 1:
            res = mul(res, a)

        a = mul(a, a)
        n >>= 1

    return res

# Compute f(x)^(3^8)
g = poly_pow(f, 3**8)

# r = 2^(2^52) mod MOD
r = pow(2, 2**52, MOD)

# Evaluate polynomial g at r modulo MOD
ans = 0
power = 1

while g:
    if g & 1:
        ans = (ans + power) % MOD

    power = (power * r) % MOD
    g >>= 1

print(ans)

4. Code walkthrough

Polynomial encoding

f = (1 << 0) | (1 << 1) | (1 << 3)

encodes

$$x^3+x+1.$$

The integer bitmask stores polynomial coefficients.

Multiplication

res ^= (a << shift)

implements polynomial multiplication over $\mathbb F_2$:

shifting corresponds to multiplying by $x^{\text{shift}}$,
XOR corresponds to addition modulo $2$.

Exponentiation

g = poly_pow(f, 3**8)

computes

$$(x^3+x+1)^{6561}.$$

Frobenius substitution

Instead of directly handling exponent $2^{52}3^8$, we use

$$g(x^{2^{52}})$$

which becomes evaluation at

$$r=2^{2^{52}} \pmod{10^9+7}.$$

5. Small example verification

For $n=2$:

$$P(2)=11\otimes 11.$$

Polynomially:

$$(x^3+x+1)^2=x^6+x^2+1.$$

Evaluating at $x=2$:

$$2^6+2^2+1=64+4+1=69,$$

matching the statement.

6. Final verification

Degree of $f^{6561}$ is $3\cdot6561=19683$, perfectly manageable.
Only XOR arithmetic is used, exactly matching the definition.
The Frobenius identity is valid because coefficients are in characteristic $2$.

The computation gives:

$$14063639.$$

Answer: 14063639

Project Euler Problem 813