CF2226A.Disturbing Distribution

You are given an array $[a_1, a_2, \ldots, a_n]$. You wish to make the array empty by performing the following operation any number of times:

• Select any sequence of indices $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le |a|$ (note that $|a|$ denotes the current length of the array $a$) such that $$a_{i_1} \le a_{i_2} \le \ldots \le a_{i_k}$$
• Remove the elements $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ from the array $a$.
• This operation incurs a cost equal to $a_{i_1} \times a_{i_2} \times \cdots \times a_{i_k}$.

Determine the minimum total cost required to remove all the elements from the array $a$. Note that the total cost is equal to the sum of costs incurred over all the operations performed.

As the answer can be very large, report the answer modulo $676\,767\,677$.

给你一个数组 $[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$ 中的元素 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ 删除；
• 此操作产生的代价为 $a_{i_1} \times a_{i_2} \times \cdots \times a_{i_k}$。

求将数组 $a$ 中所有元素全部删除所需的最小总代价。注意：总代价等于所有执行的操作所产生代价之和。

由于答案可能非常大，请将结果对 $676\,767\,677$ 取模后输出。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 100$) — the length of the array $a$.

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 100$) — the elements of the array.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$）—— 数组的元素。

For each testcase, output a single integer — the minimum total cost required to make the array $a$ empty.

As the answer may be large, output the answer modulo $676\,767\,677$.

对于每个测试用例，输出一个整数——使数组 $a$ 变为空所需的最小总成本。

由于答案可能很大，请对 $676\,767\,677$ 取模后输出答案。

For the first testcase,

• Operation 1: Choose $i_1 = 1$, $i_2 = 2$, and $i_3 = 4$. This incurs a cost of $1 \cdot 2 \cdot 2 = 4$. After deleting the elements at these indices, the array becomes $a = [1, 3]$.

• Operation 2: Choose $i_1 = 1$ and $i_2 = 2$. This incurs a cost of $1 \cdot 3 = 3$. After deleting the elements at these indices, the array becomes empty.

Thus, the total cost is equal to $4 + 3 = 7$. It can be shown that this is the minimum possible total cost.

对于第一个测试用例：

• 操作 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$。可以证明这是可能的最小总代价。