Двійкові добутки#2947
Вам дано послідовність з одиниць. Розгляньте всі можливі способи вставити між ними один або більше знаків множення так, щоб утворений вираз був коректним (знаки множення не можуть стояти підряд, а також не можуть бути на початку чи в кінці послідовності). Наприклад, для n = 4 існує способів: 1\times111, 11\times11, 111\times1, 1\times1\times11, 1\times11\times1, 11\times1\times1 і 1\times1\times1\times1. Далі знайдіть суму отриманих добутків, вважаючи, що числа записані у двійковій системі: 1_2\times111_2 + 11_2\times11_2 + 111_2\times1_2 + 1_2\times1_2\times11_2 + 1_2\times11_2\times1_2 + 11_2\times1_2\times1_2 + 1_2\times1_2\times1_2\times1_2 = 33.
Вам потрібно обчислити цю суму для будь-якого .
Перший рядок містить (1 \le T \le 1000) — кількість тестів. У наступних рядках міститься по одному числу (2 \le n \le 10^9).
Для кожного з вхідних даних виведіть шукану суму за модулем .
Приклад 1