1512 : 斐波那契

时间限制:3 Sec 内存限制:64 MiB 提交:105 正确:30

$F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2}(n\ge 3)$, 求$F_n$。答案可能太大，输出对$10^9+9$取模后的结果。

第一行一个正整数$T$表示测试数据的组数.
以下$T$行，每行1个正整数$n$.
$1\le T \le 2*10^5$
$1 \le n \le 10^ {18}$

每组数据在一行内输出答案。

1
12345678987654321

274987527

二次剩余或矩阵快速幂
day5
如果使用```endl```, 你的代码可能会被卡爆

kcxz