시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 13 13 92.857%

문제

Your job is to take an integer x as the input and compute f(x) mod 109, 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 ≤ 248.

출력

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

예제 입력

11
1
2
8
20
46
60
3749999998
3749999999
3750000000
3750000001
281474976710656

예제 출력

1
1
21
6765
836311903
8755920
499999999
500000001
0
500000001
309764667

힌트