Двійкові добутки
Є послідовність з 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.