Recursive Sequence Summation

The sequence $a_{n}$ is defined by $a_{1} = 1$ , and then recursively for $n \geq 1$ : $\begin{aligned} a_{2 n} & = 2 a_{n} \\ a_{2 n + 1} & = a_{n} - 3 a_{n + 1} \end{aligned}$ The first ten terms are $1, 2, - 5, 4, 17, - 10, - 17, 8, - 47, 34$ .
Define $S (N) = \sum_{n = 1}^{N} a_{n}$ . You are given $S (10) = - 13$ .
Find $S (10^{12})$ .

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.