问题描述

在梦幻游乐园中，举办了一场卡牌搭建大赛。主办方提供了特制的卡牌，参赛者需要按照特定的规则搭建卡牌。卡牌塔的搭建规则如下图：

注意：最下面的不需要底部摆卡牌

现在，大赛设置了 $N$ 个关卡挑战，每个关卡会给出一个整数 $M$，表示需要搭建的层数。参赛者的任务是计算出按照规则搭建 $M$ 层的卡牌塔，一共需要多少张卡牌。由于最终结果可能非常大，为了方便统计和评判，要求计算结果对 $1,000,007$ 取模后输出。

快来帮助参赛者完成挑战，计算出每个关卡所需的卡牌总数吧！

输入格式

第一行输入一个整数 $N$，表示关卡的数量。

接下来 $N$ 行，每行输入一个整数 $M$，表示每个关卡要求搭建的卡牌塔层数。

输出格式

输出共 $N$ 行，每行对应一个关卡的答案，即搭建指定层数的卡牌塔所需的卡牌总数对 $1,000,007$ 取模后的结果。

输出格式

样例输入

2
1
3

样例输出

2
15

数据范围

对于 $30\%$ 的数据，$1 \le N \le 1000, 1 \le M \le 10^4$。

对于 $100\%$ 的数据，$1 \le N \le 100000, 1 \le M \le 10^6$。