Fibonacci Sequence

Read an integer $x$ and compute $f(x)$ modulo $10^9$, where $f(x)$ is the $x$-th value of the Fibonacci sequence.

The Fibonacci sequence is defined as follows.

$f(1) = f(2) = 1$

$f(k) = f(k-1) + f(k-2) \quad (k > 2)$

The first line contains the number of test cases $t$ ($1 \le t \le 1000$).

Each of the next $t$ lines contains one integer $x$ ($1 \le x \le 2^{48}$).

For each test case, print $f(x)$ modulo $10^9$ on its own line.