В рамках этой задачи $\oplus$ используется для обозначение побитного исключающего ИЛИ от двух чисел.
Начав с пустого листа бумаги, будем повторять следующие шаги:

1. Записать наименьшее положительное целое число $a$, которое еще не записано на бумаге;
2. Найти наименьшее положительное целое число $b$, такое что ни $b$, ни $(a \oplus b)$ в данный момент еще не записаны на бумаге. Затем записать $b$ и $(a \oplus b)$.

После первой итерации на бумаге будет записано $\{1,2,3\}$. Во второй итерации $a=4$ и, так как $(4 \oplus 5)$, $(4 \oplus 6)$ и $(4 \oplus 7)$ все уже записаны, $b$ должно быть равно $8$.

После $n$ итераций на бумаге будут записаны $3n$ чисел. Обозначим их сумму как $M(n)$.
Например, $M(10) = 642$ и $M(1000) = 5432148$.

Найдите $M(10^{18})$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$.