Оскар и Эрик играют в игру: сначала, они договариваются о натуральном числе $n$ и начинают с записи на доске его представления в двоичной системе счисления. Затем они по очереди, начиная с Оскара, дописывают на доске число в двоичной форме, так чтобы сумма всех записанных чисел не превышала $2n$.

Игра заканчивается, когда больше не остается возможных ходов. Если на конец игры количество единиц на доске нечетное, то побеждает Оскар, а если четное - Эрик.

Пусть $S(N)$ будет суммой всех $n \le 2^N$, при которых Эрик может гарантировать свою победу при условии оптимальной игры.

Например, первые несколько значений $n$, при которых Эрик можут гаранитровано победить - $1,3,4,7,15,16$. Поэтому $S(4)=46$.
Также известно, что $S(12) = 54532$ и $S(1234) \equiv 690421393 \pmod{1\,000\,000\,007}$.

Найдите $S(12\,345\,678)$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$.