A. Перераспределение распределения
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$[a_1, a_2, \ldots, a_n]$$$. Требуется сделать массив пустым, выполнив следующую операцию любое количество раз:

  • Выберите любую последовательность индексов $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le |a|$$$ (здесь $$$|a|$$$ обозначает текущую длину массива $$$a$$$), такую что $$$$$$a_{i_1} \le a_{i_2} \le \ldots \le a_{i_k}$$$$$$
  • Удалите элементы $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ из массива $$$a$$$.
  • Стоимость этой операции равна $$$a_{i_1} \times a_{i_2} \times \cdots \times a_{i_k}$$$.

Определите минимальную суммарную стоимость, необходимую для удаления всех элементов массива $$$a$$$. Обратите внимание, что суммарная стоимость равна сумме стоимостей всех выполненных операций.

Так как ответ может быть очень большим, выведите его по модулю $$$676\,767\,677$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — элементы массива.

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

Для каждого набора входных данных выведите одно целое число — минимальную суммарную стоимость, необходимую, чтобы сделать массив $$$a$$$ пустым.

Так как ответ может быть большим, выведите его по модулю $$$676\,767\,677$$$.

Пример
Входные данные
3
5
1 2 1 2 3
3
3 2 1
4
1 1 1 1
Выходные данные
7
6
1
Примечание

Для первого набора входных данных:

  • Операция 1: выберем $$$i_1 = 1$$$, $$$i_2 = 2$$$ и $$$i_3 = 4$$$. Стоимость этой операции равна $$$1 \cdot 2 \cdot 2 = 4$$$. После удаления элементов с этими индексами массив становится равным $$$a = [1, 3]$$$.

  • Операция 2: выберем $$$i_1 = 1$$$ и $$$i_2 = 2$$$. Стоимость этой операции равна $$$1 \cdot 3 = 3$$$. После удаления элементов с этими индексами массив становится пустым.

Таким образом, суммарная стоимость равна $$$4 + 3 = 7$$$. Можно показать, что это минимально возможное значение.