sequence
题目背景
Wolfycz很喜欢数列(雾
题目描述
Wolfycz非常喜欢研究数列,同时他也喜欢研究黄金分割率,有一天Wolfycz写下了一个数列,他令$A_i=\lceil(\dfrac{\sqrt{5}+1}{2})^i\rceil$,但是Wolfycz并不知道$A_n$的值,所以希望你来帮帮他
注:请注意常数因子对程序运行效率的影响
输入输出格式
输入格式
第一行读入$T$,表示有$T$组数据
之后每一行一个整数$n$
输出格式
输出共$T$行,每行一个整数,表示$\lceil(\dfrac{\sqrt{5}+1}{2})^n\rceil$的值,答案对998244353取模
输入输出样例
输入样例 #1
5
1
9
20
50
100
输出样例 #1
2
77
15127
192911239
996781931
说明
对于$5\%$的数据,$n\leqslant 20$
对于$40\%$的数据,$T\leqslant 5×10^4$
对于$100\%$的数据,$T\leqslant 10^5,n\leqslant 10^{18}$