题目描述

斐波那契字符串 $S$ 是由 $\tt 0$ 和 $\tt 1$ 所组成的字符串，其生成规则如下：

• $S_1 = \tt 0$。
• $S_2 = \tt 1$。
• 对于任意正整数 $n (n \geq 3)$，$S_n = S_{n-2} + S_{n-1}$（“+”表示字符串拼接）。

例如：$S_3 = 01$、$S_4 = 101$、$S_5 = 01101$。

在斐波那契字符串 $S$ 中，定义逆序对为满足以下条件的整数对 $(i, j)$:

• $1 \leq i < j \leq |S|$（其中 $|S|$ 表示 $S$ 的长度）。
• $S[i] = 1$（第 $i$ 个字符为 $\tt 1$）并且 $S[j] = 0$（第 $j$ 个字符为 $\tt 0$）。

现在，给定一个正整数 $N$，请你计算出 $S_N$ 中所有逆序对 $(i, j)$ 的总数。由于结果可能很大，请输出其对 $10^9 + 7$ 取余后的值。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

接下来的 $T$ 行，每行包含一个整数 $N$，表示要计算的斐波那契字符串的序号。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示 $S_N$ 中所有逆序对的总数对 $10^9 + 7$ 取余后的结果。

8
3
4
5
6
7
8
9
10

0
1
2
7
18
50
132
351

说明/提示

【样例说明】

• 对于 $N = 3$，$S_3 = 01$，逆序对总数为 $0$。
• 对于 $N = 4$，$S_4 = 101$，逆序对总数为 $1$。
• 对于 $N = 5$，$S_5 = 01101$，逆序对为 $(2, 4)$、$(3, 4)$，总数为 $2$。

【评测用例规模与约定】

• 对于 $50\%$ 的评测用例，$1 \leq T \leq 10$，$3 \leq N \leq 10^5$。
• 对于 $100\%$ 的评测用例，$1 \leq T \leq 10$，$3 \leq N \leq 10^{18}$。