| 问题描述 |
|---|
有一个数列$$a$$，其中$$a_1=1, a_2=2$$，从第三项开始有$$a_i=3 * a_{i-1} - 2 * a_{i - 2}$$，求$$a_n$$。 |
| 输入描述 |
第一行是一个正整数$$T$$表示测试案例的数量。（$$1 \leq T \leq 1000$$） 每组案例包含一个正整数$$n$$表示要求的项数。（$$1 \leq n \leq 10^{18}$$） |
| 输出描述 |
针对每组案例，输出$$a_n$$的值，然后换行。 由于结果可能很大，你只需要输出它对$$100000000003$$取余之后的数字即可。 |
| 样例输入复制样例 |
2 1 2 |
| 样例输出 |
1 2 |
| 提示说明 |
矩阵快速幂 |
| 相关 |