什么，这题是3000分！！！？（hard）

题目描述

注意：hard与medium主要不同是，hard含有t组且n的范围更大,不需要减去5768

现在是2025年的3月7号 LGjian正在参加爪哇部落算法组的机考，他把榜上过的题基本都过了，除了最后一道题，这个题过的人挺多，LGjian表示他肯定可以做出来。

题目是：三阶斐波那契数列，给你一个n，让你求三阶斐波那契数列的第n项，最后结果减5768后对1e9+7取模。LGjian竟然不知道取模是什么意思，他没有做这题，离开了机考，哈哈。

取模：就是对最终答案mod 1e9+7。

三阶斐波那契数列：第1项是1，第2项是1，第3项是2，第4项是4，就是 f(n) = f (n-1) + f (n-2) + f (n-3)

输入一个整数 $t$ （ $1 \leq t \leq 10^5$ ），表示组数。接下来输入 $t$ 行，每行一个整数 $n$ （ $1 \le n \le 10^{18}$ ）。

输出三阶斐波那契数列第 $n$ 项对 $10^9+7$ 取模后的答案（hard 版本不减去 $5768$ ）。

1
18