Solution

Answer: 253223948

Let

$$q = 2^n.$$

We are counting ordered $n$-tuples

$$(x_1,x_2,\dots,x_n)$$

such that:

each $x_i\in{1,2,\dots,q-1}$,
all $x_i$ are distinct,
the position is winning in nim, i.e.

$$x_1\oplus x_2\oplus \cdots \oplus x_n \ne 0.$$

Define:

$A_k$: number of ordered distinct nonzero $k$-tuples,
$L_k$: number of ordered distinct nonzero $k$-tuples with xor $0$,
$W_k=A_k-L_k$.

We ultimately need $W_n$ for $q=2^n$.

1. Mathematical analysis

Total number of tuples

The total number of ordered distinct nonzero $k$-tuples is simply

$$A_k=(q-1)(q-2)\cdots(q-k)$$

(using falling factorial notation $A_k=(q-1)_k$).

In particular,

$$A_n=(2^n-1)(2^n-2)\cdots(2^n-n).$$

Counting losing positions

We now derive a recurrence for $L_k$.

Consider a losing $k$-tuple:

$$x_1\oplus x_2\oplus\cdots\oplus x_k=0.$$

Then the last element is forced:

$$x_k=x_1\oplus x_2\oplus\cdots\oplus x_{k-1}.$$

So we begin with any ordered distinct nonzero $(k-1)$-tuple and ask when the forced value is valid.

There are $A_{k-1}$ possible $(k-1)$-tuples.

Two bad cases must be excluded.

Bad case 1: the xor is $0$

Then $x_k=0$, forbidden.

This happens exactly when the first $k-1$ entries already xor to $0$.

Count:

$$L_{k-1}.$$

Bad case 2: the xor equals an existing entry

Suppose

$$x_1\oplus\cdots\oplus x_{k-1}=x_i.$$

Then removing $x_i$ leaves a $(k-2)$-tuple whose xor is $0$.

Conversely:

choose a losing $(k-2)$-tuple,
choose the position $i$ ($k-1$ choices),
choose $x_i$ to be any nonzero value not already used.

The $(k-2)$-tuple already uses $k-2$ distinct nonzero values, so there are

$$(q-1)-(k-2)=q-k+1$$

choices for $x_i$.

Therefore the number of tuples in bad case 2 is

$$(k-1)(q-k+1)L_{k-2}.$$

Recurrence

Hence:

$$\boxed{ L_k = A_{k-1} - L_{k-1} - (k-1)(q-k+1)L_{k-2} }$$

with initial conditions

$$L_0=1,\qquad L_1=0.$$

Finally,

$$W_n=A_n-L_n.$$

This recurrence is linear-time and easily fast enough for $n=10^7$.

2. Python implementation

MOD = 1_000_000_007

def solve(n):
    q = pow(2, n, MOD)

    # n = 1 is trivial
    if n == 1:
        return 1

    # A1 = q - 1
    A_prev = (q - 1) % MOD

    # L0 = 1, L1 = 0
    L_prev2 = 1
    L_prev1 = 0

    # Build up to Ln
    for k in range(2, n + 1):

        # Recurrence:
        # Lk = A_{k-1}
        #      - L_{k-1}
        #      - (k-1)(q-k+1)L_{k-2}
        Lk = (
            A_prev
            - L_prev1
            - ((k - 1) * (q - k + 1) % MOD) * L_prev2
        ) % MOD

        # Update A_k from A_{k-1}
        A_curr = (A_prev * (q - k)) % MOD

        # Shift states
        A_prev = A_curr
        L_prev2, L_prev1 = L_prev1, Lk

    # Wn = An - Ln
    return (A_prev - L_prev1) % MOD

print(solve(5))      # 19764360
print(solve(100))    # 384777056
print(solve(10_000_000))

3. Code walkthrough

Step 1

q = pow(2, n, MOD)

Computes $2^n \bmod MOD$.

Step 2

A_prev = q - 1

Stores

$$A_1=q-1.$$

Step 3

L_prev2 = 1
L_prev1 = 0

Initializes:

$$L_0=1,\qquad L_1=0.$$

Step 4

Inside the loop:

Lk = (
    A_prev
    - L_prev1
    - ((k - 1) * (q - k + 1) % MOD) * L_prev2
) % MOD

implements

$$L_k=A_{k-1}-L_{k-1}-(k-1)(q-k+1)L_{k-2}.$$

Step 5

A_curr = (A_prev * (q - k)) % MOD

updates

$$A_k=A_{k-1}(q-k).$$

Step 6

At the end:

(A_prev - L_prev1) % MOD

returns