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 $ .

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.

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 $ .

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.