Codeforces Round 957 (Div. 3) |
---|
Закончено |
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$$$.
523499951
12 31 354226409 184 4
Название |
---|