| 问题描述 |
|---|
已知一数列的前两项都为 1，从第三项开始，奇数项为前两项之和，偶数项为前两项之差。 那么我们很快可以算出数列的前几项：1、1、2、1、3、2 ... ... 现在，请你求数列的第 n 项。 |
| 输入描述 |
输入的第一行包含一个正整数 T，表示询问的次数。 接下来 T 行，每行包含一个正整数 n 表示询问的项数 。 对于 20% 的评测用例，1 ≤ n ≤ 50，1 ≤ T ≤ 50。 对于 40% 的评测用例，1 ≤ n ≤ 1,000，1 ≤ T ≤ 1,000。 对于 60% 的评测用例，1 ≤ n ≤ 1,000,000，1 ≤ T ≤ 10,000。 对于 100% 的评测用例，1 ≤ n ≤ 1,000,000,000，1 ≤ T ≤ 100,000。 |
| 输出描述 |
输出 T 行，每行包含一个整数表示本次询问的结果，然后换行。 由于答案可能很大，所以你只需要输出它对 1000000007 取余之后的结果。 |
| 样例输入复制样例 |
3 1 2 3 |
| 样例输出 |
1 1 2 |
| 相关 |