题目描述

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

S1​=0。 S2​=1。 对于任意正整数 n(n≥3)，Sn​=Sn−2​+Sn−1​（“+”表示字符串拼接）。 例如：S3​=01、S4​=101、S5​=01101。

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

1≤i<j≤∣S∣（其中 ∣S∣ 表示 S 的长度）。 S[i]=1（第 i 个字符为 1）并且 S[j]=0（第 j 个字符为 0）。 现在，给定一个正整数 N，请你计算出 Sn 中所有逆序对 (i,j) 的总数。由于结果可能很大，请输出其对 109+7 取余后的值。

输入格式

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

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

输出格式

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

样例

2
3
5

0
2

说明/提示

【样例说明】

对于 N=3，S3​=01，逆序对总数为 0。

对于 N=5，S5​=01101，逆序对为 (2,4)、(3,4)，总数为 2。

【评测用例规模与约定】

对于 20% 的评测用例，$1≤T≤20$，$3≤N≤35$。

对于 100% 的评测用例，$1≤T≤10^5$，$3≤N≤10^5$。