Будем использовать обозначение $x\oplus y$ для побитового XOR от $x$ и $y$.
Определим XOR-произведение $x$ и $y$, обозначаемое $x \otimes y$, аналогично умножению в столбик в двоичной системе счисления, с единственным отличием в том, что промежуточные результаты подвергаются операции XOR вместо обычного целочисленного сложения.

Например, $7 \otimes 3 = 9$, или же, в двоичной системе счисления, $111_2 \otimes 11_2 = 1001_2$:

$$\begin{align*} \phantom{\otimes 111} 111_2 \\ \otimes \phantom{1111} 11_2 \\ \hline \phantom{\otimes 111} 111_2 \\ \oplus \phantom{11} 111_2 \phantom{9} \\ \hline \phantom{\otimes 11} 1001_2 \\ \end{align*}$$ Рассмотрим следующее уравнение: $$\begin{align} (a \otimes a) \oplus (2 \otimes a \otimes b) \oplus (b \otimes b) = k \end{align}$$ $(a, b) = (3, 6)$ является примером решения этого уравнения при $k=5$.

Пусть $G(N,m)$ будет количеством решений таких уравнений при $k \le m$ and $0 \le a \le b \le N$.

Известно, что $G(1000,100)=398$.

Найдите $G(10^{17},1\,000\,000).$