E. Генерация троек
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано целое число $$$n$$$. Найдите количество троек целых чисел $$$(a, b, c)$$$, для которых выполняются следующие условия:

  • $$$1 \le a \lt b \lt c \le n$$$;
  • $$$a$$$, $$$b$$$ и $$$c$$$ образуют арифметическую прогрессию (т. е. $$$b - a = c - b$$$);
  • $$$a \oplus b \oplus c = 0$$$, где $$$\oplus$$$ обозначает битовую операцию XOR.
Поскольку ответ может быть очень большим, вам нужно вывести только остаток от деления на $$$10^9+7$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Каждый набор входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 10^{18}$$$).

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

Для каждого набора входных данных выведите в отдельной строке одно целое число — количество допустимых троек $$$(a, b, c)$$$ по модулю $$$10^9 + 7$$$.

Пример
Входные данные
4
3
10
15
1000000000000000000
Выходные данные
1
2
5
353768760
Примечание

В первом наборе входных данных, когда $$$n = 3$$$, единственной допустимой тройкой является $$$(1, 2, 3)$$$. Она удовлетворяет условию арифметической прогрессии, поскольку $$$2 - 1 = 3 - 2 = 1$$$, и удовлетворяет условию XOR, поскольку $$$1 \oplus 2 \oplus 3 = 0$$$.

Для больших значений $$$n$$$ не забудьте вывести ответ по модулю $$$10^9 + 7$$$.