N.G. 的一种变体de Bruijn 的银元游戏可以描述如下：

在一条方格上放置了许多硬币，每个方格最多放置一枚硬币。只有一种硬币，称为银元，具有任何价值。两名玩家轮流走棋。每回合玩家必须进行常规或特殊移动。

常规移动包括选择一枚硬币并将其向左移动一个或多个方格。硬币不能移出条带或跳到另一枚硬币上或上方。

或者，玩家可以选择进行特殊动作，将最左边的硬币装进口袋，而不是进行常规动作。如果无法进行常规移动，玩家将被迫将最左边的硬币装进口袋。

获胜者是将银元收入囊中的玩家。

获胜配置是硬币在条带上的排列，其中第一个玩家可以强制获胜，无论第二个玩家做什么。

令 $W(n,c)$ 为一条 $n$ 方块、$c$ 毫无价值的硬币和一枚银元的获胜配置数。

已知 $W(10,2)=324$ 且 $W(100,10)=1514704946113500$。

求 $W(1000000,100)$ 对半质数 $1000036000099$ 取模 ($=1000003\cdot 1000033$)。