1043 - 数论:矩阵快速幂:矩阵加速
Time Limit : 1 秒
Memory Limit : 256 MB
已知一个数列 a,它满足:
求 a 数列的第 n 项对 10^9+7 取余的值。
Input
第一行一个整数 T,表示询问个数。
以下 T 行,每行一个正整数 n。
Output
每行输出一个非负整数表示答案。
Examples
Input
3 6 8 10
Output
4 9 19
Hint
- 对于 30\% 的数据 n \leq 100;
- 对于 60\% 的数据 n \leq2 \times 10^7;
- 对于 100\% 的数据 1 \leq T \leq 100,1 \leq n \leq 2 \times 10^9。