Пусть s_k будет количеством единиц, использованных при записи чисел от 0 до k в двоичном виде.
Например, записывая числа от 0 до 5 в двоичном виде, мы получаем 0, 1, 10, 11, 100, 101. Всего использовано семь единиц, таким образом, s₅ = 7.
Последовательность S = {s_k : k ≥ 0} начинается следующим образом: {0, 1, 2, 4, 5, 7, 9, 12, ...}.

В игру играют двое игроков. Перед началом игры выбирается число n. Счетчик c начинается с 0. На каждый ход игрок выбирает число от 1 до n (включительно) и увеличивает c на это число. Полученное значение c должно быть элементом S. Если игрок больше не имеет возможных ходов, он проигрывает.

Например:
Пусть n = 5. c начинается с 0.
Игрок 1 выбирает 4, посему c принимает значение 0 + 4 = 4.
Игрок 2 выбирает 5, посему c принимает значение 4 + 5 = 9.
Игрок 1 выбирает 3, посему c принимает значение 9 + 3 = 12.
И т.д.
Заметьте, что c должно всегда принадлежать S, и каждый игрок может увеличить c не больше, чем на n.

Пусть M(n) будет наибольшим числом, которое первый игрок может выбрать и обеспечить себе победу, и M(n) = 0, если такого хода не существует. Например, M(2) = 2, M(7) = 1 и M(20) = 4.

Дано, что Σ(M(n))³ = 8150 для 1 ≤ n ≤ 20.

Найдите Σ(M(n))³ для 1 ≤ n ≤ 1000.