2303: 行子欲上无阶梯
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：45
解决：9
题目描述
小X最近喜欢上了搭积木，现在有若干块边长为 2i 的正方形积木。（只考虑平面，不用考虑立体情况）。
现在小X想要拼成一个每节楼梯长度为1的楼梯形状，如下图：
现在想知道如果右下角最大的正方形的边长为 2n 时，那么最少需要多少块正方形积木才能拼成这样的楼梯形。由于块数数量较大，将数量对109+7取模即可。（取模也就是求余数）
现在小X想要拼成一个每节楼梯长度为1的楼梯形状，如下图：
现在想知道如果右下角最大的正方形的边长为 2n 时，那么最少需要多少块正方形积木才能拼成这样的楼梯形。由于块数数量较大，将数量对109+7取模即可。（取模也就是求余数）
输入
输入一共有多组数据。
第一行为一个整数t，表示数据的组数。
接下来的t行，每行一个非负组数n，表示每组数据中右下角最大的正方形的边长为 2n。
第一行为一个整数t，表示数据的组数。
接下来的t行，每行一个非负组数n，表示每组数据中右下角最大的正方形的边长为 2n。
输出
输出一共n行，每行一个整数，表示每组数据最少需要的正方形块数。
样例输入 复制
3
0
1
2样例输出 复制
1
3
7提示
样例解释：
一共3组数据
当n为0时，放一块1*1的正方形即可。
当n为1时，最少需要3块正方形，1块2*2，2块1*1，如下图所示：
当n为2是，最少需要7块正方形，1块4*4，2块2*2，4块1*1，如下图所示：
数据范围
1≤t≤1e6，0≤n≤1e6
一共3组数据
当n为0时，放一块1*1的正方形即可。
当n为1时，最少需要3块正方形，1块2*2，2块1*1，如下图所示：
当n为2是，最少需要7块正方形，1块4*4，2块2*2，4块1*1，如下图所示：
数据范围
1≤t≤1e6，0≤n≤1e6