3006: 兔兔的纠纷

时间限制:1000 ms 内存限制:128 MB
上传者:
提交:2 通过:1

题目描述

彩虹岛历公元$0$年,岛上出现了一种名为兔兔的危险物种!兔兔的繁殖能力非常惊人,新生的兔兔只要$1$年的时间便达到成熟,并且一对成熟的兔兔在其成熟当年以及次年都会再产下一对兔兔。
从此,彩虹岛的生态发生了剧烈的变化。
在公元$0$年,彩虹岛上出现了一对新生兔兔($0$岁)。
到了公元$1$年,原来的一对兔兔达到了成熟($1$岁),并且又产下了一对兔兔($0$ 岁),岛上便有了$2$只$0$岁的兔兔与$2$只$1$岁的兔兔。
到了公元$2$年,原来的一对兔兔达到了$2$岁,而去年新出生的兔兔也达到了成熟($1$ 岁),这两对兔兔又各自产下了一对兔兔($0$岁),岛上便有了$4$只$0$岁的兔兔、$2$ 只$1$岁的兔兔以及$2$ 只$2$岁的兔兔。
$\cdots \cdots$
由于受到一股来自东方的神秘力量庇护,兔兔们得以长生不死,而它们的数目却在不断增加,造成了资源上的紧缺,因此兔兔之间经常会发生某些纠纷。
我们认为在公元$k$年的时候,对于任意两只不同的兔兔,如果它们的年龄之和恰好为$k$,那么它们之间会发生一次纠纷。
请问在第$k$年的时候所有的兔兔之间一共发生了多少次纠纷?
请注意,答案可能很大,请输出对$10^{9} + 7$取模后的结果。

输入格式

输入第一行为一个整数$T(T \leq 200000)$,表示一共有$T$组测试数据。
接下来有$T$行,每行有$1$个整数$k$,表示公元$k$年$(1 \leq k \leq 200000)$。

输出格式

对于每组测试数据,输出第$k$年所有兔兔之间总共发生的纠纷数对$10^{9} + 7$取模后的结果。

输入样例 复制

2
1
2

输出样例 复制

4
9

数据范围与提示