两名玩家，安东和伯恩哈德，正在玩以下游戏。
有一堆 $n$ 石头。
第一个玩家可以移除任意正数的石子，但不能移除整堆石子。
此后，每个玩家最多可以移除对手上一步所拿走的棋子数量的两倍。
移走最后一块石头的玩家获胜。

例如$n=5$。
如果第一个玩家拿走的石头超过一个，那么下一个玩家将能够拿走所有剩余的石头。
如果第一位玩家拿走一颗石子，留下四颗，那么他的对手也会拿走一颗石子，留下三颗石子。
第一个玩家不能拿走全部三颗棋子，因为他最多可以拿走 $2\times 1=2$ 棋子。假设他也拿走了一颗石头，留下 $2$。第二个玩家可以拿走剩下的两颗石子并获胜。
所以$5$对于第一个玩家来说是一个失败的位置。
对于某些获胜位置，第一名玩家有多个可能的动作。
例如当$n=17$时，第一个玩家可以移除一个或四个石头。

设 $M(n)$ 为第一位玩家在第一回合可以从获胜位置拿走的最大石子数量，$M(n)=0$ 为任何其他位置。

$\sum M(n)$ 对应 $n\le 100$ 为 $728$。

查找 $n\le {10}^{18}$ 的 $\sum M(n)$。 给出以 ${10}^8$ 为模的答案。