E. Сумма решений

Как классная задача E, но нужно не количество решений уравнения $a - (a \oplus x) - x = 0$, а их сумма.

Решения — это все подмаски $a$. Сумму подмасок можно получить, не перебирая их: каждый единичный бит $a$ встречается ровно в половине подмасок. Если у $a$ ровно $k$ единичных битов, то каждый из них входит в $2^{k-1}$ подмасок, и

При $a = 0$ формула неприменима — там единственная подмаска, ноль, и сумма нулевая. Этот случай стоит разобрать отдельно.

Ответ выводите по модулю $10^9 + 7$.

Первая строка содержит число $t$ ($1 \le t \le 1000$).

Далее идут $t$ строк со значениями $a$ ($0 \le a \le 2^{30} - 1$).

$t$ строк — сумма решений по модулю $10^9 + 7$.