暂无测试数据。

lyz 喜欢搭积木，他有若干块边长为 $2^i$ 的正方形积木。

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

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

输入格式

输入有多组数组。

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

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

输出格式

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

数据范围

对于 $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$；

3
0
1
2

1
3
7