13075번 - Fibonacci Sequence 다국어

Your job is to take an integer x as the input and compute f(x) mod 10⁹, where f(x) is the x-th value in the well-known Fibonacci sequence. 

Note that Fibonacci sequence is defined as follows:

f(1) = f(2) = 1
f(k) = f(k-1) + f(k-2) for any k > 2

The first line of the input includes the number of test cases, 1 ≤ t ≤ 1000. Each test case is a line containing an integer 1 ≤ x ≤ 2⁴⁸.

For each test case, print one line containing f(x) mod 10⁹