给你一个数组 $$$[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$$$ 为模报告答案。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 取模的答案。
示例
输入复制
351 2 1 2 333 2 141 1 1 1
输出复制
761
注意
对于第一个测试用例,
- 操作 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$$$。可以证明这是最小可能的总成本。