391 : ホッピングゲーム (*)

$0$から$k$までの数を2進法で書き下したときの1の個数を$s_k$としよう。 例えば、$0$から$5$までを2進法で書くと$0, 1, 10, 11, 100, 101$となる。7つの1があるので$s_5 = 7$となる。 数列$S = \{s_k \, | \, k \geq 0\}$は$\{0, 1, 2, 4, 5, 7, 9, 12, \dots\}$で始まる数列となる。

2人で行うゲームがある。ゲーム開始前に、ある数$n$を選んでおく。カウンタ$c$があり、それは$0$から始まる。それぞれの局面で、対局者は$1$から$n$まで（$n$を含む）のある数を選び、その数だけ$c$を増やす。その結果得られる$c$の値は数列$S$の要素でなければならない。もしそのような有効な指し手を打てない場合、対局者は負けとなる。

例を示そう： $n = 5$とし、$c$は$0$から始まる。 先手は$4$を選び、$c$は$0 + 4 = 4$となる。 後手は$5$を選び、$c$は$4 + 5 = 9$となる。 先手は$3$を選び、$c$は$9 + 3 = 12$となる。 以下同様 留意すべき点として、$c$は常に$S$に属していなければならない、そしてそれぞれの対局者はたかだか$n$までの数で$c$を増加させていくことができる。

先手必勝となるように先手が最初の局面で選べる一番大きい数字を$M(n)$とし、そしてそのような指し手がない場合は$M(n) = 0$としよう。例えば$M(2) = 2, M(7) = 1, M(20) = 4$となる。

$1 \leq n \leq 20$に対する$\sum M(n)^3 = 8150$がすでに与えられている。

$1 \leq n \leq 1000$に対する$\sum M(n)^3$を求めよ。

(* 数列Sの表記法がどう見ても集合。)