PIPI今天刚刚学习了斐波拉契数列:
F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2) (n>1)
现在PIPI想知道斐波拉契数列的第 k 项，胖虎能够告诉PIPI吗?
由于结果很大，输出F(k)对p取模的结果即可~
p = 10⁹+7

输入包含多组测试用例。
每组测试用例包含一个正整数 k (1<=k<=10¹⁰)

对于每组样例，输出F(k)%p

中等 数学