P15910 [TOPC 2024] Fibonacci Lucky Numbers

欢迎来到 **幸运 777 老虎机游戏**！这款游戏以其复杂的数学挑战而闻名，只有最聪明的人才能赢得头奖。 这台老虎机由一个神秘的序列驱动——**斐波那契数列**。但这不是普通的斐波那契数列，它有一个受数字 $7$ 启发的变体，而 $7$ 是老虎机游戏中的幸运数字。 当你拉动 **幸运 777 老虎机** 的拉杆时，它会利用一个整数 $n$ 和 $7$ 的幂次生成一个巨大的数字：$7^{7^n}$。然而，这个数字如此庞大，以至于即使是最强大的计算机也无法直接处理它。 为了赢得头奖，你需要计算 $F_{7^{7^n}}$，即第 $7^{7^n}$ 个斐波那契数的最后 $10$ 位数字。 **注意** 斐波那契数列定义如下： - $F_0 = 0$ - $F_1 = 1$ - $F_k = F_{k-1} + F_{k-2}$，对于 $k \ge 2$

第一行包含一个整数 $t$，表示测试用例的数量。接下来的 $t$ 行，每行是一个测试用例，包含一个正整数 $n$。

对于每个测试用例，输出一行，包含 $F_{7^{7^n}}$ 的最后 $10$ 位数字。

- $1 \le t \le 20$ - $1 \le n \le 10^9$ 翻译由 DeepSeek V3.2 完成