Background

土拨鼠彦清 喜欢搭积木，他有若干块边长为 $2^i$的正方形积木。

彦清 满意积木拼成一个楼梯的形状，比如这样：

他想知道，如果右下角最大的正方形的边长为 $2^n$时，最少需要多少块正方形才能拼成他满意的形状（楼梯形）。由于块数可能很多，请对 $10^9 + 7$取模。

Format

Input

输入有多组数组。

第一行输入一个正整数 $T$，表示数据的组数。

接下来 $T$ 行，每行输入一个非负整数 $n$，表示每组数据中右下角最大的正方形的边长为 $2^n$。

Output

输出共 $T$ 行，每行输出一个整数，分别表示每组数据中需要正方形的块数。

Samples

3
0
1
2

1
3
7

样例解释

$2^0 = 1$, 放一块$1*1$的正方形积木

$2^1 = 2$, 最少需要$3$块正方形, 方法如图:

$2^2 = 4$, 需要7块正方形, 方法如图:

Limitation

对于 $20\%$ 的数据，$1\leq T \leq 10,0\leq n \leq 31$；

对于另外 $30\%$ 的数据，$1\leq T \leq 100,0\leq n \leq 63$；

对于另外 $20\%$ 的数据，$1\leq T \leq 10^5,0\leq n \leq 10^5$；

对于 $100\%$ 的数据，$1\leq T \leq 10^6,0\leq n \leq 10^6$；

注意

文件重定向, block.in, block.out