U448937 丘丘人

最近，层岩巨渊里来了很多丘丘人。受它们身上魔神残渣的污染，层岩巨渊的环境变得恶劣起来。璃月的仙人们想要处理此事，于是他们让你来调查污染情况。

你获得了一份由仙人们记录的丘丘人观察日志。你很快发现每个丘丘人身上的魔神残渣可以由序列 $f$ 表示，其中第一项 $f_1 = 1$，第二项 $f_2 = 1$，第 $i\ (i \ge 3)$ 项 $f_i = f_{i-1}+f_{i-2}$。 璃月的仙人们计算出了环境污染指数与魔神残渣点数的关系。对于第 $n$ 天，环境污染指数为: $$\sum_{i = 1}^{n} (2n-2i+1)f_i$$ 现在给定 $n$，求第 $n$ 天的环境污染指数？ 由于答案可能很大，请你输出答案对 $10^{14}+31$ 取余的结果。已知这是一个质数。 仙人们想要分析很多天的环境，所以他们给了你 $m$ 组数据。

第一行一个整数 $m$。 接下来 $m$ 行，一行一个整数 $n$。

共 $m$ 行，一行一个整数，表示答案。 由于答案可能很大，请你输出答案对 $10^{14}+31$ 取余的结果。

**请注意本题较为特殊的时空限制。** 本题开启捆绑测试。只有通过 Subtask 内的所有测试点，才能拿到对应 Subtask 的分数。 ~~不过在 ICPC 赛制的比赛中似乎并没有什么用？~~ |Sub.|Test Points Number|$n$|$m$| |:-:|:-:|:-:|:-:| |1|$1 \sim 10$|$n \le 10^5$|$m \le 100$| |2|$11 \sim 20$|$n \le 10^9$|$m \le 500$| |3|$21 \sim 50$|$n \le 10^{16}$|$m \le 1500$| 对于 $100 \%$ 的数据，$1 \le n \le 10^{16},1 \le m \le 1500$。