19518번 - Math is Fun 다국어

Boy XYZ introduced a simple math function called $\mathit{GLL}$ for an array of integers $S = \{a_1, a_2, \ldots, a_n\}$:

$$\mathit{GLL}(S) = \mathit{GCD}(S) \cdot   \mathit{LCM}(S) \cdot \mathit{LCM}(S)\text{.}$$

Here, $\mathit{GCD}(S) = \mathit{GCD}(a_1, a_2, \ldots, a_n)$ is the greatest common divisor of integers $a_1, a_2, \ldots, a_n$, and $\mathit{LCM}(S) = \mathit{LCM}(a_1, a_2, \ldots, a_n)$ is the least common multiple of integers $a_1, a_2, \ldots, a_n$.

For an array consisting of one element, $\mathit{GCD}$ and $\mathit{LCM}$ are equal to that element. For example, $\mathit{GCD}$ of $S = \{x\}$ is $x$. Consider the $\mathit{LCM}$ and $\mathit{GCD}$ of an empty array as $0$.

Now, XYZ is interested in finding the sum of $\mathit{GLL}$ values of all subarrays for a given array $A$, but he finds the problem very hard. Help him calculate the following:

$$\mathit{Answer} = \sum_{S \subseteq A}\mathit{GLL}(S)\text{.}$$

Here, $S \subseteq A$ means that $S$ is a subarray of $A$, that is, the array $A$ with some (possibly zero, possibly all) elements removed.

As the answer can be very large, print it modulo $10^9 + 7$.

The first line of input contains $T$, the number of test cases ($1 \le T \le 50$). $T$ test cases follow.

The first line of each test case contains $N$, the number of elements in $A$ ($1 \le N \le 100$). The next line contains $N$ space-separated positive integers: the elements of $A$. The numbers in the array are in the range $[1, 1000]$.

For each test case, print the answer on a separate line.