F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:祝各位Oier新年快乐,Rp++!
Problem 5118. -- Fib数列2

5118: Fib数列2

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 58  Solved: 43
[Submit][Status][Discuss]

Description

Fib定义为Fib(0)=0,Fib(1)=1,对于n≥2,Fib(n)=Fib(n-1)+Fib(n-2)
现给出N,求Fib(2^n).

Input

本题有多组数据。第一行一个整数T,表示数据组数。
接下来T行每行一个整数N,含义如题目所示。
n≤10^15, T≤5

Output

输出共T行,每行一个整数为所求答案。
由于答案可能过大,请将答案mod 1125899839733759后输出

Sample Input

2
2
31

Sample Output

3
343812777493853

HINT

Source

[Submit][Status][Discuss]

HOME Back