Два игрока, Антон и Бернард, играют в следующую игру.
Есть одна кучка из n камней.
Первый игрок может убрать из нее любое положительное количество камней, но не всю кучу сразу.
Далее каждый игрок по очереди убирает не больше удвоенного количества камней, убранных противником в предыдущий ход.
Побеждает игрок, убравший последний камень.

К примеру, n=5.
Если первый игрок уберет больше, чем один камень, его противник сможет убрать все оставшиеся.
Если первый игрок уберет один камень, оставив четыре, его противник тоже уберет один, оставив три камня.
Первый игрок не может убрать все три, потому что он может убрать не более 2×1=2 камней. Предположим, он уберет еще один - останется 2. Второй игрок может убрать два оставшихся камня и выиграть.
Таким образом, 5 - проигрышная позиция для первого игрока
Для некоторых выигрышных позиций существует больше одного возможного хода первого игрока
Например, когда n=17, первый игрок может убрать один или четыре камня первым ходом.

Пусть M(n) будет максимальным числом камней, которое первый игрок может взять в выигрышной позиции первым ходом и M(n)=0 для любой другой позиции.

∑ M(n) для n ≤ 100 равно 728.

Найдите ∑ M(n) для n≤10¹⁸. В качестве ответа приведите остаток от деления полученного числа на 10⁸.