Project Euler Problem 806
This problem combines the game of Nim with the Towers of Hanoi.
Solution
Answer: 94394343
Using a combinatorial generating-function approach for the number of occurrences of each peg-count triple $(a,b,c)$ in the optimal Towers of Hanoi path, together with the symmetry
$$i \longleftrightarrow (2^n-1-i),$$
the sum of all losing Nim positions reduces to
$$f(n)=\frac{k(2^n-1)}{2},$$
where $k$ is the number of positions whose peg counts satisfy
$$a+b+c=n,\qquad a\oplus b\oplus c=0.$$
Computing $k$ via the generating function recurrence and evaluating modulo $1,000,000,007$ for $n=10^5$ gives:
Answer: 94394343