Есть последовательность из \textbf{n} единиц. Рассмотрим все различные способы вставить между ними одну и более операций умножения так, чтобы получившееся выражение имело смысл (т. е. операции умножения не должны стоять подряд, в начале и в конце последовательности). Например, для \textbf{n = 4} есть \textbf{7} способов: \textbf{1}×\textbf{111}, \textbf{11}×\textbf{11}, \textbf{111}×\textbf{1},\textbf{1}×\textbf{1}×\textbf{11}, \textbf{1}×\textbf{11}×\textbf{1}, \textbf{11}×\textbf{1}×\textbf{1} и \textbf{1}×\textbf{1}×\textbf{1}×\textbf{1}. Посчитаем сумму получившихся произведений, считая, что числа записаны в двоичной системе счисления: \textbf{1_2}×\textbf{111_2}+\textbf{11_2}×\textbf{11_2}+\textbf{111_2}×\textbf{1_2}+\textbf{1_2}×\textbf{1_2}×\textbf{11_2}+\textbf{1_2}×\textbf{11_2}×\textbf{1_2}+\textbf{11_2}×\textbf{1_2}×\textbf{1_2}+\textbf{1_2}×\textbf{1_2}×\textbf{1_2}×\textbf{1_2} = \textbf{33}. Вы должны посчитать эту сумму для произвольного \textbf{n}. \InputFile Первая строка содержит \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{1000}) --- количество тестов. Следующие \textbf{T} строк содержат \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{10^9}). \OutputFile Для каждого \textbf{n} из исходных данных программа должна выдать искомую сумму по модулю \textbf{1000000007}.