有一个 n+1n+1n+1 层的台阶，渡渡鸟现在正处于第 000 层。它一次可以跳一级台阶或两级台阶，问渡渡鸟到达第 nnn 层台阶一共有多少种不同的方案。由于方案数可能很大，你只需要输出其对 109+910^9+9109+9 取模的值即可。
本题有多组测试，首先是一个整数 TTT，代表测试数据的组数。（1≤T≤1000001\leq T \leq 1000001≤T≤100000）
之后 TTT 行，每行仅一个整数 nnn （0≤n≤10180\leq n \leq 10^{18}0≤n≤1018）。
输出 TTT 行，每行一个非负整数，代表这组测试方案数模 109+910^9+9109+9 的值。
样例输入
5 0 1 2 100 1000000000000000000
样例输出
1 1 2 486534406 680023062
欢迎用各种神奇方式过掉这道签到题。