BZPRO
#5118. Fib数列2
内存限制：512 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
Fib定义为Fib(0)=0,Fib(1)=1,对于n≥2,Fib(n)=Fib(n-1)+Fib(n-2)
现给出N，求Fib(2^n).
输入格式
本题有多组数据。第一行一个整数T，表示数据组数。
接下来T行每行一个整数N，含义如题目所示。
n≤10^15, T≤5
输出格式
输出共T行，每行一个整数为所求答案。
由于答案可能过大，请将答案mod 1125899839733759后输出
样例
样例输入
2
2
31
样例输出
3
343812777493853
数据范围与提示
BZPRO