时间限制:3 Sec 内存限制:64 MiB
提交
$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