hyy有鱼系列(17)
Description
【背景】咕咕咕……
【题意】
求斐波那契数列的第n项模1e9+9的值
f(1)=1 f(2)=1
多组数据
【输入格式】
第一行一个正整数T
下来T行每行一个正整数n
【输出格式】
输出T行，每行一个数，表示答案
【输入样例】
1
30569291125360
【输出样例】
166484489
【提示】
1<=T<=1000000
1<=n<=18446744073709551615
咕咕咕……
【题意】
求斐波那契数列的第n项模1e9+9的值
f(1)=1 f(2)=1
多组数据
【输入格式】
第一行一个正整数T
下来T行每行一个正整数n
【输出格式】
输出T行，每行一个数，表示答案
【输入样例】
1
30569291125360
【输出样例】
166484489
【提示】
1<=T<=1000000
1<=n<=18446744073709551615