Двоичные произведения

Есть последовательность из n единиц. Рассмотрим все различные способы вставить между ними одну и более операций умножения так, чтобы получившееся выражение имело смысл (т. е. операции умножения не должны стоять подряд, в начале и в конце последовательности). Например, для n = 4 есть 7 способов: 1×111, 11×11, 111×1,1×1×11, 1×11×1, 11×1×1 и 1×1×1×1. Посчитаем сумму получившихся произведений, считая, что числа записаны в двоичной системе счисления: 1_2×111_2+11_2×11_2+111_2×1_2+1_2×1_2×11_2+1_2×11_2×1_2+11_2×1_2×1_2+1_2×1_2×1_2×1_2 = 33.

Вы должны посчитать эту сумму для произвольного n.

Входные данные

Первая строка содержит T (1 ≤ T ≤ 1000) — количество тестов. Следующие T строк содержат n (2 ≤ n ≤ 10^9).

Выходные данные

Для каждого n из исходных данных программа должна выдать искомую сумму по модулю 1000000007.

Примеры