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.

제한

힌트