G. Ультра-мяу
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

K1o0n подарил вам массив $$$a$$$ длины $$$n$$$, состоящий из чисел $$$1, 2, \ldots, n$$$. Принять? Конечно, да! Но что с ним делать? Конечно же посчитать $$$\text{MEOW}(a)$$$.

Пусть $$$\text{MEX}(S, k)$$$ — $$$k$$$-е целое положительное число в порядке возрастания, отсутствующее в множестве $$$S$$$. Обозначим за $$$\text{MEOW}(a)$$$ сумму $$$\text{MEX}(b, |b| + 1)$$$, по всем различным подмножествам $$$b$$$ массива $$$a$$$.

Примеры значений $$$\text{MEX}(S, k)$$$ для множеств:

  • $$$\text{MEX}(\{3,2\}, 1) = 1$$$, т. к. $$$1$$$ — первое целое положительное число, отсутствующее в множестве;
  • $$$\text{MEX}(\{4,2,1\}, 2) = 5$$$, т. к. первые два целые положительные числа, которых нет в множестве, это $$$3$$$ и $$$5$$$;
  • $$$\text{MEX}(\{\}, 4) = 4$$$, т. к. в пустом множестве нет никаких чисел, следовательно первые целые положительные $$$4$$$ числа, которых в нём нет, это $$$1, 2, 3, 4$$$.
Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В единственной строке каждого набора входных данных вводится целое число $$$n$$$ ($$$1 \le n \le 5000$$$), размер массива подаренных чисел.

Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$25 \cdot 10^6$$$

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

Для каждого набора входных данных выведите одно число — $$$\text{MEOW}(a)$$$. Поскольку оно может оказаться очень большим, выведите его по модулю $$$10^9 + 7$$$.

Пример
Входные данные
5
2
3
4999
5
1
Выходные данные
12
31
354226409
184
4