피보나치 수열

x가 최대 2^48까지 커질 수 있는 최대 1000개의 질의에 대해 x번째 피보나치 수를 10^9로 나눈 나머지를 구한다.

보통7수학행렬분할 정복정수론아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제3

정수 $x$ 를 입력받아 피보나치 수열의 $x$ 번째 값 $f(x)$ 를 $10^9$ 으로 나눈 나머지를 구한다.

피보나치 수열의 정의는 다음과 같다.

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

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

첫 줄에 테스트 케이스의 개수 $t$ 가 주어진다 ( $1 \le t \le 1000$ ).

이어지는 $t$ 개의 줄에는 각각 정수 $x$ 가 하나씩 주어진다 ( $1 \le x \le 2^{48}$ ).

각 테스트 케이스마다 $f(x)$ 를 $10^9$ 으로 나눈 나머지를 한 줄에 하나씩 출력한다.