Problem 344

Silver dollar game

One variant of N.G. de Bruijn's **silver dollar** game can be described as follows:

On a strip of squares a number of coins are placed, at most one coin per square. Only one coin, called the **silver dollar**, has any value. Two players take turns making moves. At each turn a player must make either a *regular* or a *special* move.

A *regular* move consists of selecting one coin and moving it
one or more squares to the left. The coin cannot move out of the strip
or jump on or over another coin.

Alternatively, the player can choose to make the *special* move
of pocketing the leftmost coin rather than making a regular move. If no
regular moves are possible, the player is forced to pocket the leftmost
coin.

The winner is the player who pockets the silver dollar.

A *winning configuration* is an arrangement of coins on the strip where the first player can force a win no matter what the second player does.

Let W(`n`,`c`) be the number of winning configurations for a strip of `n` squares, `c` worthless coins and one silver dollar.

You are given that W(10,2) = 324 and W(100,10) = 1514704946113500.

Find W(1 000 000, 100) modulo the semiprime 1000 036 000 099 (= 1 000 003 ยท 1 000 033).

**
These problems are part of
Project Euler
and are licensed under
CC BY-NC-SA 2.0 UK
**