Background

Special for beginners, ^_^

Description

MEX是博弈论里面一个常用的函数，表示一个集合中，最小的不出现在该集合中的非负整数。 例如集合{1, 2. 3. 4}的MEX是0。 集合{0, 1, 2}的MEX是3。 集合{1, 0, 2, 4}的MEX是3。 现在有一个长度为n的集合S，里面包含整数0到n-1。 请计算S的所有子集的MEX函数的和。

Format

Input

第一行一个整数T（不超过1万），表示有T组数据。 后面每行一个n（不超过100亿），如前面描述所述

Output

每行输出一个n对应的子集的MEX之和。由于和太大了，请对1e9+7取模后输出。

Samples

2
1
2

1
3

Limitation

1s, 1024KiB for each test case.