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\).
Выходные данные
Для каждого набора входных данных выведите одно число — \(\text{MEOW}(a)\). Поскольку оно может оказаться очень большим, выведите его по модулю \(10^9 + 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
3
4999
5
1
|
12
31
354226409
184
4
|