Background

Special for beginners, ^_^

Description

在一次课上，徐老师和同学们讨论了一个“兔子繁殖”的小问题：

• 第 1 个月的时候，只有一对小兔子，它们刚出生，还不能繁殖。
• 到了第 2 个月，这对兔子长大了，可以开始生下一对新的小兔子。
• 从第 3 个月起，每一对兔子在长大之后，每个月都会再生下一对新兔子。

现在徐老师想知道：第 $n$ 个月的时候，总共有多少对兔子，将答案对 $10^9+7$ 取模后输出。

Format

输入：

• 第一行一个整数 $t$ $(1 \leq t \leq 10^5)$，表示测试组数。
• 接下来 $t$ 行，每行一个整数 $n$ $(1 \leq n \leq 10^6)$。

输出：

• 共 $t$ 行，每行一个整数，表示第 $n$ 个月的兔子对数 。

Sample

3
5
10
20

5
55
6765