By brute-forcing small values of \(n\) and \(k\), a rather rigid pattern begins to appear. In particular, odd triples occur only when \(n = 4i + 1\) for some non-negative integer \(i\). Moreover, the number of valid choices of \(k\) is determined by the binary structure of \(i\).
Therefore, the problem can be reduced to summing this contribution over all \(i\) such that \(4i + 1 \le 10^{12}\). However, this still leaves roughly \(10^{12}/4\) terms, so a direct iteration is not feasible.
The main optimization is to avoid processing each \(i\) individually. Since the contribution depends only on the binary digits of \(i\), we can process the upper bound bit by bit, and count whole blocks of free lower bits at once. This gives a logarithmic-time bit-DP over \({\lfloor (10^{12}-1)/4 \rfloor}\).