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)\) для множеств:
Первая строка содержит одно целое число \(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
2500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач