P12833 [蓝桥杯 2025 国 B] 斐波那契字符串

斐波那契字符串 $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$ 取余后的结果。

**【样例说明】** 对于 $N = 3$，$S_3 = 01$，逆序对总数为 0。 对于 $N = 5$，$S_5 = 01101$，逆序对为 $(2, 4)$、$(3, 4)$，总数为 2。 **【评测用例规模与约定】** 对于 20% 的评测用例，$1 \leq T \leq 20$，$3 \leq N \leq 35$。 对于 100% 的评测用例，$1 \leq T \leq 10^5$，$3 \leq N \leq 10^5$。