HC10000  Hofstadter–Conway 10000 dollar sequence
Hofstadter–Conway $10,000 sequence is a famous sequence, which is defined as $$ a_1 = a_2 = 1,\, a_{n} = a_{a_{n1}} + a_{na_{n1}}\, (n \ge 3). $$
Your task is to find a summatory function $S(n) := \sum\limits_{i=1}^n a_i$ and compute $S(n)$ modulo $10^9$.
Input
The first line contains $T$ ($1 \le T \le 10000$), the number of test cases.
Each of the next $T$ lines contains a positive integer $n$ ($1 \le n \le 10^{18}$).
Output
For each test case, print $S(n)$ modulo $10^9$.
Example
Input: 10 1 2 3 4 5 10 100 1000 1000000 1000000000 Output: 1 2 4 6 9 32 2818 269446 334706485 137951847
Explanation
You can verify that $a_1 = a_2 = 1$, $a_3 = a_4 = 2$ and $a_5 = 3$. So, $S(5) = 9$.
$S(10^9) = 259987670137951847 \equiv 137951847 \pmod{10^9}$.
Information
There are 5 input files:
 #1: $n \le 10^{4}$, TL = 2s.
 #2: $n \le 10^{6}$, TL = 2s.
 #3: $n \le 10^{8}$, TL = 3s.
 #4: $n \le 10^{12}$, TL = 5s.
 #5: $n \le 10^{18}$, TL = 12s.
These time limits allow a (slow) Python2 solution to get accepted.
hide comments
Francky:
20160616 01:08:49
My kind of problem ! Many thanks for this task ;)


Min_25:
20160504 03:05:41
@Blue.Mary


[Rampage] Blue.Mary:
20160503 16:54:36
Thanks to min_25 for setting this beautiful and tough problem. Learned some new things. 
Added by:  Min_25 
Date:  20160503 
Time limit:  2s12s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 