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_{n-1}} + a_{n-a_{n-1}}\, (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.


Added by:Min_25
Date:2016-05-03
Time limit:2s-12s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2016-06-16 01:08:49 Francky
My kind of problem ! Many thanks for this task ;-)

(Re) Thanks !

=(Francky)=> I let a very small place to allow someone to take #1, it's possible but could be hard.
edit : no more place. Or using a slow language.

Last edit: 2017-02-10 17:50:55
2016-05-04 03:05:41 Min_25
@Blue.Mary
Thank you. I also like the amazing property of this sequence.
2016-05-03 16:54:36 [Rampage] Blue.Mary
Thanks to min_25 for setting this beautiful and tough problem. Learned some new things.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.